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
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 
@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
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

Cité par Sources :