2023/11/30 by Cyriac Antony, Antony, Cyriac, M. A. Shalu +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2312.00086
openalex publication_date 2023/11/30 · openalex created_date 2023/12/05 · openalex updated_date 2026/07/28
We relate star colouring of even-degree regular graphs to the notions of locally constrained graph homomorphisms to the oriented line graph L(Kq) of the complete graph Kq and to its underlying undirected graph L^*(Kq) . Our results have consequences for locally constrained graph homomorphisms and oriented line graphs in addition to star colouring. We show that L^*(H) is a 2-lift of the line graph L(H) for every graph H . Dvořák, Mohar and Šámal (J. Graph Theory, 2013) proved that for every 3-regular graph G , the line graph of G is 4-star colourable if and only if G admits a locally bijective homomorphism to the cube Q3 . We generalise this result as follows: for p≥ 2 , a K1,p+1 -free 2p -regular graph G admits a (p+2) -star colouring if and only if G admits a locally bijective homomorphism to L^*(Kp+2) . As a result, if a Kp+1 -free 2p -regular graph G with p≥ 2 is (p+2) -star colourable, then -2 and p-2 are eigenvalues of G . We also prove the following: (i) for p≥ 2 , a 2p -regular graph G admits a (p+2) -star colouring if and only if G has an orientation that admits an out-neighbourhood bijective homomorphism to L(Kp+2) ; (ii) the line graph of a 3-regular graph G is 4-star colourable if and only if G is bipartite and distance-two 4-colourable; and (iii) it is NP-complete to check whether a planar 4-regular 3-connected graph is 4-star colourable.