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 4 |V(G)| / 5 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)
Loading...