Wheel-free planar graphs

Abstract

A \emph{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.

References in corpus (6)

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• On graphs with no induced subdivision of $K_4$
• Edge-colouring and total-colouring chordless graphs
• Graphs that do not contain a cycle with a node that has at least two neighbors on it
• Detecting wheels
• On wheel-free graphs

Cited by in corpus (4)

• The (theta, wheel)-free graphs Part I: only-prism and only-pyramid graphs
• Isometric path complexity of graphs
• Stable sets in {ISK4,wheel}-free graphs
• Wheels in planar graphs and Hajós graphs