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: https://doi.org/10.37236/13181

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.

Published
2025-02-28
How to Cite
Bonnet, Édouard, Feghali, C., Nguyen, T., Scott, A., Seymour, P., Thomassé, S., & Trotignon, N. (2025). Graphs without a 3-Connected Subgraph are 4-Colourable. The Electronic Journal of Combinatorics, 32(1), P1.26. https://doi.org/10.37236/13181
Issue
Volume 32, Issue 1 (2025)
Article Number
P1.26