Optimal acyclic edge‐coloring of cubic graphs |
| |
| Authors: | Lars Døvling Andersen Edita Máčajová Ján Mazák |
| |
| Affiliation: | 1. Department of Mathematical Sciences, Aalborg University, , Aalborg S?, Denmark;2. Department of Computer Science, Faculty of Mathematics, Physics and Informatics Comenius University, , Bratislava, Slovakia |
| |
| Abstract: | An acyclic edge‐coloring of a graph is a proper edge‐coloring such that the subgraph induced by the edges of any two colors is acyclic. The acyclic chromatic index of a graph G is the smallest number of colors in an acyclic edge‐coloring of G. We prove that the acyclic chromatic index of a connected cubic graph G is 4, unless G is K4 or K3,3; the acyclic chromatic index of K4 and K3,3 is 5. This result has previously been published by Fiam?ík, but his published proof was erroneous. |
| |
| Keywords: | acyclic edge‐coloring cubic graphs |
|
|
