Skip to main content
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1v60m
Abstract: A wheel is a graph formed by a chordless cycle CC and a vertex uu not in CC that has at least three neighbors in CC. 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.
Publication Date: Oct-2015
Electronic Publication Date: 20-Mar-2015
Citation: Aboulker, Pierre, Chudnovsky, Maria, Seymour, Paul, Trotignon, Nicolas. (2015). Wheel-free planar graphs. European Journal of Combinatorics, 49 (57 - 67). doi:10.1016/j.ejc.2015.02.027
DOI: doi:10.1016/j.ejc.2015.02.027
ISSN: 0195-6698
Pages: 57 - 67
Type of Material: Journal Article
Journal/Proceeding Title: European Journal of Combinatorics
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.