Star Colouring of Regular Graphs Meets Weaving and Line Graphs

For \( q\in \mathbb {N} \) , a \( q \) -star colouring of a graph \( G \) is a proper \( q \) -colouring \( f \) of \( G \) such that there is no path \( u,v,w,x \) in \( G \) with \( f(u)=f(w) \) and \( f(v)=f(x) \) (the violating path need not be induced). For \( p\ge 2 \) , Shalu and Antony (Discrete Math., 2022) proved that at least \( p+2 \) colours are required to star colour a \( 2p \) -regular graph \( G \) , and characterised the class \( \mathcal {G} \) of graphs \( G \) for which \( p+2 \) colours suffices in terms of graph orientations. In the second author’s thesis (2023), we provided a characterisation of the class \( \mathcal {G} \) in terms of locally constrained graph homomorphisms. In this paper, we characterise \( \mathcal {G} \) in terms of weaving patterns of edge decompositions. We also show that the study of class \( \mathcal {G} \) is tied to the theory of line graphs and line digraphs of complete graphs. We prove that if a \( K_{1,p+1} \) -free \( 2p \) -regular graph \( G \) with \( p\ge 2 \) is \( (p+2) \) -star colourable, then \( {-2} \) and \( p-2 \) are eigenvalues of the adjacency matrix of \( G \) .