Wheel-free planar graphs

Pierre Aboulker (1) , Maria Chudnovsky (2) , Paul Seymour (3) , Nicolas Trotignon (4, 5)

1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
2 Department of Computer Science [New York]
3 Princeton University
4 LIP - Laboratoire de l'Informatique du Parallélisme
5 MC2 - Modèles de calcul, Complexité, Combinatoire

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.

Domaines: Mathématique discrète [cs.DM]

Pierre Aboulker, Maria Chudnovsky, Paul Seymour, Nicolas Trotignon. Wheel-free planar graphs. European Journal of Combinatorics, 2015, 49, ⟨10.1016/j.ejc.2015.02.027⟩. ⟨hal-01230782⟩