{
  "id": "math/0601623",
  "version": "v1",
  "published": "2006-01-25T19:59:29.000Z",
  "updated": "2006-01-25T19:59:29.000Z",
  "title": "A Strong Edge-Coloring of Graphs with Maximum Degree 4 Using 22 Colors",
  "authors": [
    "Daniel Cranston"
  ],
  "comment": "9 pages, 4 figures",
  "journal": "Discrete Math. Vol. 306, no. 21, November 2006, pp. 2772-2778",
  "categories": [
    "math.CO"
  ],
  "abstract": "In 1985, Erd\\H{o}s and Ne\\'{s}etril conjectured that the strong edge-coloring number of a graph is bounded above by ${5/4}\\Delta^2$ when $\\Delta$ is even and ${1/4}(5\\Delta^2-2\\Delta+1)$ when $\\Delta$ is odd. They gave a simple construction which requires this many colors. The conjecture has been verified for $\\Delta\\leq 3$. For $\\Delta=4$, the conjectured bound is 20. Previously, the best known upper bound was 23 due to Horak. In this paper we give an algorithm that uses at most 22 colors.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-01-25T19:59:29.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "maximum degree",
      "upper bound",
      "simple construction",
      "strong edge-coloring number",
      "conjectured bound"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......1623C"
    }
  }
}