On the existence of graphs which can colour every regular graph

Abstract

Let H and G be graphs. An H-colouring of G is a proper edge-colouring f : E(G) → E(H) such that for any vertex u ∈ V(G) there exists a vertex v ∈ V(H) with f (∂Gu) = ∂H v, where ∂Gu and ∂H v respectively denote the sets of edges in G and H incident to the vertices u and v. If G admits an H-colouring we say that H colours G. The question whether there exists a graph H that colours every bridgeless cubic graph is addressed directly by the Petersen Colouring Conjecture, which states that the Petersen graph colours every bridgeless cubic graph. In 2012, Mkrtchyan showed that if this conjecture is true, the Petersen graph is the unique connected bridgeless cubic graph H which can colour all bridgeless cubic graphs. In this paper we extend this and show that if we were to remove all degree conditions on H, every bridgeless cubic graph G can be coloured substantially only by a unique other graph: the subcubic multigraph S4 on four vertices. A few similar results are provided also under weaker assumptions on the graph G. In the second part of the paper, we also consider H-colourings of regular graphs having degree strictly greater than 3 and show that: (i) for any r > 3, there does not exist a connected graph H (possibly containing parallel edges) that colours every r-regular multigraph, and (ii) for every r > 1, there does not exist a connected graph H (possibly containing parallel edges) that colours every 2r-regular simple graph.