{
  "id": "1408.6046",
  "version": "v1",
  "published": "2014-08-26T08:21:58.000Z",
  "updated": "2014-08-26T08:21:58.000Z",
  "title": "Equitable Coloring of Graphs with Intermediate Maximum Degree",
  "authors": [
    "Bor-Liang Chen",
    "Kuo-Ching Huang",
    "Ko-Wei Lih"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "If the vertices of a graph $G$ are colored with $k$ colors such that no adjacent vertices receive the same color and the sizes of any two color classes differ by at most one, then $G$ is said to be equitably $k$-colorable. Let $|G|$ denote the number of vertices of $G$ and $\\Delta=\\Delta(G)$ the maximum degree of a vertex in $G$. We prove that a graph $G$ of order at least 6 is equitably $\\Delta$-colorable if $G$ satisfies $(|G|+1)/3 \\leq \\Delta < |G|/2$ and none of its components is a $K_{\\Delta +1}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-08-26T08:21:58.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "intermediate maximum degree",
      "equitable coloring",
      "color classes differ",
      "adjacent vertices receive"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1408.6046C"
    }
  }
}