2013/09/09 by Pierre Aboulker, Aboulker, Pierre, Frédéric Havet +3 · 1 citation
Computer Science · Mathematics · #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C75
paper · pdf · doi:10.48550/arxiv.1309.2113
Unpublished
arxiv created 2013/09/09 · openalex publication_date 2013/09/09 · arxiv updated 2013/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A wheel is a graph formed by a chordless cycle and a vertex that has at least three neighbors in the cycle. We prove that every 3-connected graph that does not contain a wheel as a subgraph is in fact minimally 3-connected. We give a new proof of a theorem of Thomassen and Toft: every graph that does not contain a wheel as a subgraph is 3-colorable.