Acyclic 4-edge colouring of non-regular subcubic graphs in linear time
An acyclic   k k -edge-colouring  is an assignment of colours from {1,2,,k} { 1 , 2 ,  , k } to the edges of a simple graph G G such that adjacent edges have different colours and each circuit of G 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.
subcubic graphs acyclic edge colouring