{
  "id": "1302.2405",
  "version": "v4",
  "published": "2013-02-11T06:43:09.000Z",
  "updated": "2014-04-05T03:06:22.000Z",
  "title": "Acyclic edge coloring of graphs",
  "authors": [
    "Tao Wang",
    "Yaqiong Zhang"
  ],
  "comment": "19 pages",
  "journal": "Discrete Appl. Math., 167 (2014) 290--303",
  "doi": "10.1016/j.dam.2013.12.001",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "An {\\em acyclic edge coloring} of a graph $G$ is a proper edge coloring such that the subgraph induced by any two color classes is a linear forest (an acyclic graph with maximum degree at most two). The {\\em acyclic chromatic index} $\\chiup_{a}'(G)$ of a graph $G$ is the least number of colors needed in an acyclic edge coloring of $G$. Fiam\\v{c}\\'{i}k (1978) conjectured that $\\chiup_{a}'(G) \\leq \\Delta(G) + 2$, where $\\Delta(G)$ is the maximum degree of $G$. This conjecture is well known as Acyclic Edge Coloring Conjecture (AECC). A graph $G$ with maximum degree at most $\\kappa$ is {\\em $\\kappa$-deletion-minimal} if $\\chiup_{a}'(G) > \\kappa$ and $\\chiup_{a}'(H) \\leq \\kappa$ for every proper subgraph $H$ of $G$. The purpose of this paper is to provide many structural lemmas on $\\kappa$-deletion-minimal graphs. By using the structural lemmas, we firstly prove that AECC is true for the graphs with maximum average degree less than four (\\autoref{NMAD4}). We secondly prove that AECC is true for the planar graphs without triangles adjacent to cycles of length at most four, with an additional condition that every $5$-cycle has at most three edges contained in triangles (\\autoref{NoAdjacent}), from which we can conclude some known results as corollaries. We thirdly prove that every planar graph $G$ without intersecting triangles satisfies $\\chiup_{a}'(G) \\leq \\Delta(G) + 3$ (\\autoref{NoIntersect}). Finally, we consider one extreme case and prove it: if $G$ is a graph with $\\Delta(G) \\geq 3$ and all the $3^{+}$-vertices are independent, then $\\chiup_{a}'(G) = \\Delta(G)$. We hope the structural lemmas will shed some light on the acyclic edge coloring problems.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2014-04-05T03:06:22.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "maximum degree",
      "structural lemmas",
      "planar graph",
      "acyclic chromatic index",
      "maximum average degree"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1302.2405W"
    }
  }
}