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 E V(G) there exists a vertex v E V(H) with f (8Gu) = 8Hv, where 8Gu and 8Hv 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.(c) 2023 Elsevier B.V. All rights reserved.
On the existence of graphs which can colour every regular graph / Mazzuoccolo, G.; Tabarelli, G.; Zerafa, J. P.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 337:(2023), pp. 246-256. [10.1016/j.dam.2023.05.006]
On the existence of graphs which can colour every regular graph
Mazzuoccolo G.
;Tabarelli G.;Zerafa J. P.
2023
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 E V(G) there exists a vertex v E V(H) with f (8Gu) = 8Hv, where 8Gu and 8Hv 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.(c) 2023 Elsevier B.V. All rights reserved.File | Dimensione | Formato | |
---|---|---|---|
2110.13684.pdf
Open Access dal 16/10/2024
Tipologia:
Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione
377.98 kB
Formato
Adobe PDF
|
377.98 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris