Graphs without a 3-connected subgraph are 4-colorable

Autor:	Bonnet, Édouard, Feghali, Carl, Nguyen, Tung, Scott, Alex, Seymour, Paul, Thomassé, Stéphan, Trotignon, Nicolas
Rok vydání:	2024
Předmět:	Mathematics - Combinatorics Computer Science - Discrete Mathematics 05C15 05C40 G.2.2
Druh dokumentu:	Working Paper
Popis:	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. Comment: 13 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2402.06338 Zobrazit plný text záznamu View this record from Arxiv