Acyclic 4-edge colouring of non-regular subcubic graphs in linear time

摘要

An acyclic k-edge-colouring is an assignment of colours from {1, 2, . . ., k} to the edges of a simple graph G such that adjacent edges have different colours and each circuit of G contains edges of at least three colours. We describe a linear time algorithm to construct an acyclic 4-edge-colouring of a connected subcubic graph that is not cubic.