Graphs without a 3-connected subgraph are 4-colorable

2024/02/09 by Édouard Bonnet, Bonnet, Édouard, Carl Feghali +6
Computer Science · #05C15 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2402.06338

openalex publication_date 2024/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable. We show that the number 5 of colors can be replaced by 4, which is best possible.

Related

• A formal proof of the four color theorem
• A certifying algorithm for 3-colorability of P5-free graphs
• On a conjecture concerning 4-coloring of graphs with one crossing
• Coloring graphs with crossings
• A comment to: On 3-colorable planar graphs without short cycles