An Algorithm for Optimal Acyclic Edge-Colouring of Cubic Graphs

摘要

An acyclic edge-colouring of a graph is a proper edge-colouring such that the subgraph induced by the edges of any two colours is acyclic. The acyclic chromatic index of a graph G is the smallest possible number of colours in an acyclic edge-colouring of G. In [12], we have shown that the acyclic chromatic index of a connected subcubic graph G is at most 4 with the exception of K_4 and K_(3,3), for which five colors are optimal. Here we give a quadratic-time algorithm that finds an acyclic 4-edge-colouring of a given connected subcubic graph different from K_4 and K_(3,3).