Variations on the Petersen colouring conjecture
Variations sur la conjecture de coloration par le graphe de Petersen
Résumé
The Petersen colouring conjecture states that every bridgeless cubic graph admits an edge-colouring with 5 colours such that for every edge e, the
set of colours assigned to the edges adjacent to e has cardinality either 2 or 4 but not 3. We prove that every bridgeless cubic graph G admits an edge-colouring with 4 such that at most 8 |E(G)| / 15 edges do not satisfy the above condition. This bound is tight and the Petersen graph is the only connected graph for which the bound cannot be decreased. We obtain such a 4-edge-colouring by using a carefully chosen subset of edges of a perfect matching, and the analysis relies on a simple discharging procedure with essentially no reductions and very few rules.
Domaines
Combinatoire [math.CO]
Origine : Fichiers produits par l'(les) auteur(s)