Wheel-free planar graphs

Pierre Aboulker, Maria Chudnovsky, Paul Seymour, Nicolas Trotignon

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)57-67
Number of pages11
JournalEuropean Journal of Combinatorics
Volume49
DOIs
StatePublished - Oct 1 2015

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Wheel-free planar graphs'. Together they form a unique fingerprint.

  • Cite this