Geodesic
Graphs without a 3-connected subgraph are 4-colourable
Édouard Bonnet1 ; Carl Feghali1 ; Tung Nguyen2 ; Alex Scott3 ; Paul Seymour2 ; Stéphan Thomassé4 ; Nicolas Trotignon
1CNRS - ENS de Lyon - LIP
2Princeton University
3Mathematical Institute, University of Oxford
4ENS de Lyon - LIP
The electronic journal of combinatorics, Tome 32 (2025) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colourable. We show that the number 5 of colours can be replaced by 4, which is best possible.
DOI : 10.37236/13181
Classification : 05C15, 05C40
Mots-clés : 4-degenerate subgraphs

Édouard Bonnet  1   ; Carl Feghali  1   ; Tung Nguyen  2   ; Alex Scott  3   ; Paul Seymour  2   ; Stéphan Thomassé  4   ; Nicolas Trotignon 

1 CNRS - ENS de Lyon - LIP
2 Princeton University
3 Mathematical Institute, University of Oxford
4 ENS de Lyon - LIP 
@article{10_37236_13181,
     author = {\'Edouard Bonnet and Carl Feghali and Tung Nguyen and Alex Scott and Paul Seymour and St\'ephan Thomass\'e and Nicolas Trotignon},
     title = {Graphs without a 3-connected subgraph are 4-colourable},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {1},
     doi = {10.37236/13181},
     zbl = {1559.05048},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/13181/}
}
TY  - JOUR
AU  - Édouard Bonnet
AU  - Carl Feghali
AU  - Tung Nguyen
AU  - Alex Scott
AU  - Paul Seymour
AU  - Stéphan Thomassé
AU  - Nicolas Trotignon
TI  - Graphs without a 3-connected subgraph are 4-colourable
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/13181/
DO  - 10.37236/13181
ID  - 10_37236_13181
ER  - 
%0 Journal Article
%A Édouard Bonnet
%A Carl Feghali
%A Tung Nguyen
%A Alex Scott
%A Paul Seymour
%A Stéphan Thomassé
%A Nicolas Trotignon
%T Graphs without a 3-connected subgraph are 4-colourable
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/13181/
%R 10.37236/13181
%F 10_37236_13181
Édouard Bonnet; Carl Feghali; Tung Nguyen; Alex Scott; Paul Seymour; Stéphan Thomassé; Nicolas Trotignon. Graphs without a 3-connected subgraph are 4-colourable. The electronic journal of combinatorics, Tome 32 (2025) no. 1. doi: 10.37236/13181

Cité par Sources :