2013/09/30 by Pierre Aboulker, Maria Chudnovsky, Paul Seymour +1 · 7 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Computational Geometry and Mesh Generation #Discrete mathematics #Distance-hereditary graph #Graph #Graph power #Induced subgraph #Limits and Structures in Graph Theory #Line graph #Mathematics #Outerplanar graph #Pathwidth #Planar graph #Vertex (graph theory) #Wheel graph #math.CO #msc:05C75
paper · pdf · doi:10.1016/j.ejc.2015.02.027
published in European Journal of Combinatorics 49, 57-67 (Elsevier BV)
arxiv created 2014/08/18 · openalex publication_date 2015/03/20 · arxiv updated 2015/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
A wheel is a graph formed by a chordless cycle C and a vertex u not in C that has at least three neighbors in C. We prove that every 3-connected planar graph that does not contain a wheel as an induced subgraph is either a line graph or has a clique cutset. We prove that every planar graph that does not contain a wheel as an induced subgraph is 3-colorable.