Geodesic
Variations on the Petersen colouring conjecture
François Pirot ; Jean-Sébastien Sereni1 ; Riste Škrekovski
1Centre National de la Recherche Scientifique
The electronic journal of combinatorics, Tome 27 (2020) no. 1

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl DOI arXiv
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 colours such that at most $8/15\cdot|E(G)|$ 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.
DOI : 10.37236/8515
Classification : 05C15, 05C40
Mots-clés : Petersen graph, bridgeless cubic graph

François Pirot    ; Jean-Sébastien Sereni  1   ; Riste Škrekovski 

1 Centre National de la Recherche Scientifique 
François Pirot; Jean-Sébastien Sereni; Riste Škrekovski. Variations on the Petersen colouring conjecture. The electronic journal of combinatorics, Tome 27 (2020) no. 1. doi: 10.37236/8515
@article{10_37236_8515,
     author = {Fran\c{c}ois Pirot and Jean-S\'ebastien Sereni and Riste \v{S}krekovski},
     title = {Variations on the {Petersen} colouring conjecture},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {1},
     doi = {10.37236/8515},
     zbl = {1431.05074},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8515/}
}
TY  - JOUR
AU  - François Pirot
AU  - Jean-Sébastien Sereni
AU  - Riste Škrekovski
TI  - Variations on the Petersen colouring conjecture
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8515/
DO  - 10.37236/8515
ID  - 10_37236_8515
ER  - 
%0 Journal Article
%A François Pirot
%A Jean-Sébastien Sereni
%A Riste Škrekovski
%T Variations on the Petersen colouring conjecture
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8515/
%R 10.37236/8515
%F 10_37236_8515

Cité par Sources :