{
  "id": "1912.01546",
  "version": "v1",
  "published": "2019-12-03T17:48:50.000Z",
  "updated": "2019-12-03T17:48:50.000Z",
  "title": "On the deficiency of complete multipartite graphs",
  "authors": [
    "Armen R. Davtyan",
    "Gevorg M. Minasyan",
    "Petros A. Petrosyan"
  ],
  "comment": "18 pages, 3 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-12-03T17:48:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "complete multipartite graphs",
      "deficiency",
      "tight upper bound",
      "edges incident",
      "minimum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}