Back to Search
Start Over
Acyclic edge-coloring of planar graphs: $\Delta$ colors suffice when $\Delta$ is large
- Source :
- SIAM Journal on Discrete Math. Vol. 33(2), 2019, pp. 614-628
- Publication Year :
- 2017
-
Abstract
- An \emph{acyclic edge-coloring} of a graph $G$ is a proper edge-coloring of $G$ such that the subgraph induced by any two color classes is acyclic. The \emph{acyclic chromatic index}, $\chi'_a(G)$, is the smallest number of colors allowing an acyclic edge-coloring of $G$. Clearly $\chi'_a(G)\ge \Delta(G)$ for every graph $G$. Cohen, Havet, and M\"{u}ller conjectured that there exists a constant $M$ such that every planar graph with $\Delta(G)\ge M$ has $\chi'_a(G)=\Delta(G)$. We prove this conjecture.<br />Comment: 15 pages, 8 figures; minor revisions to incorporate reviewer feedback; to appear in SIAM J. Discrete Math
- Subjects :
- Mathematics - Combinatorics
05C15, 05C10
Subjects
Details
- Database :
- arXiv
- Journal :
- SIAM Journal on Discrete Math. Vol. 33(2), 2019, pp. 614-628
- Publication Type :
- Report
- Accession number :
- edsarx.1705.05023
- Document Type :
- Working Paper