Wheel-free planar graphs
Author(s): Aboulker, Pierre; Chudnovsky, Maria; Seymour, Paul D.; Trotignon, Nicolas
DownloadTo 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.