Wheel-free planar graphs
arXiv:1309.7120 · doi:10.1016/j.ejc.2015.02.027
Abstract
A \emph{wheel} is a graph formed by a chordless cycle and a vertex not in that has at least three neighbors in . 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 (7)
- A structure theorem for graphs with no cycle with a unique chord and its consequences
- On graphs with no induced subdivision of
- Vertex elimination orderings for hereditary graph classes
- 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