Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On the deficiency of complete multipartite graphs   An edge-coloring of a graph $G$ with colors $1,\ldots,t$ is an \emph{interval
$t$-coloring} if all colors are used, and the colors of edges incident to each
vertex of $G$ are distinct and form an integer interval. It is well-known that
there are graphs that do not have interval colorings. The \emph{deficiency} of
a graph $G$, denoted by $\mathrm{def}(G)$, is the minimum number of pendant
edges whose attachment to $G$ leads to a graph admitting an interval coloring.
In this paper we investigate the problem of determining or bounding of the
deficiency of complete multipartite graphs. In particular, we obtain a tight
upper bound for the deficiency of complete multipartite graphs. We also
determine or bound the deficiency for some classes of complete multipartite
graphs.

30
The categories of this paper are: q-alg
14
The categories of this paper are: math-ph
27
The categories of this paper are: comp-gas
17
The categories of this paper are: q-fin
35
The categories of this paper are: mtrl-th
34
The categories of this paper are: chem-ph
32
The categories of this paper are: atom-ph
13
The categories of this paper are: quant-ph
24
The categories of this paper are: dg-ga
5
The categories of this paper are: gr-qc
12
The categories of this paper are: nucl-th
15
The categories of this paper are: nucl-ex
18
The categories of this paper are: econ
11
The categories of this paper are: hep-lat
9
The categories of this paper are: nlin
3
The categories of this paper are: physics