{
  "id": "0801.1744",
  "version": "v1",
  "published": "2008-01-11T10:17:27.000Z",
  "updated": "2008-01-11T10:17:27.000Z",
  "title": "Acyclic Edge Coloring of Graphs with Maximum Degree 4",
  "authors": [
    "Manu Basavaraju",
    "L. Sunil Chandran"
  ],
  "comment": "13 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "An $acyclic$ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycle s. The \\emph{acyclic chromatic index} of a graph is the minimum number k such that there is an acyclic e dge coloring using k colors and is denoted by $a'(G)$. It was conjectured by Alon, Sudakov and Zaks that for any simple and finite graph $G$, $a'(G)\\le \\Delta+2$, where $\\Delta =\\Delta(G)$ denotes the maximum degree of $G$. We prove the conjecture for connected graphs with $\\Delta(G) \\le 4$, with the additional restriction that $m \\le 2n-1$, where $n$ is the number of vertices and $m$ is the number of edges in $G $. Note that for any graph $G$, $m \\le 2n$, when $\\Delta(G) \\le 4$. It follows that for any graph $G$ if $\\Delta(G) \\le 4$, then $a'(G) \\le 7$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2008-01-11T10:17:27.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "maximum degree",
      "acyclic edge coloring",
      "chromatic index",
      "additional restriction",
      "minimum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}