Graphs without a 3-Connected Subgraph are 4-Colourable

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

doi:10.37236/13181

Graphs without a 3-Connected Subgraph are 4-Colourable

Édouard Bonnet, Carl Feghali, Tung Nguyen, Alex Scott, Paul Seymour, Stéphan Thomassé, Nicolas Trotignon

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English (US)
Article number	#P1.26
Journal	Electronic Journal of Combinatorics
Volume	32
Issue number	1
DOIs	https://doi.org/10.37236/13181
State	Published - 2025

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.37236/13181

Cite this

@article{2f2bf2583aa245a3b422f0397f05196e,

title = "Graphs without a 3-Connected Subgraph are 4-Colourable",

abstract = "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.",

author = "{\'E}douard Bonnet and Carl Feghali and Tung Nguyen and Alex Scott and Paul Seymour and St{\'e}phan Thomass{\'e} and Nicolas Trotignon",

note = "Publisher Copyright: {\textcopyright} The authors.",

year = "2025",

doi = "10.37236/13181",

language = "English (US)",

volume = "32",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

T1 - Graphs without a 3-Connected Subgraph are 4-Colourable

AU - Bonnet, Édouard

AU - Feghali, Carl

AU - Nguyen, Tung

AU - Scott, Alex

AU - Seymour, Paul

AU - Thomassé, Stéphan

AU - Trotignon, Nicolas

PY - 2025

Y1 - 2025

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=86000520379&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=86000520379&partnerID=8YFLogxK

U2 - 10.37236/13181

DO - 10.37236/13181

M3 - Article

AN - SCOPUS:86000520379

SN - 1077-8926

VL - 32

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

M1 - #P1.26

ER -

Graphs without a 3-Connected Subgraph are 4-Colourable

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this