Wheel-free planar graphs

Pierre Aboulker; Maria Chudnovsky; Paul Seymour; Nicolas Trotignon

doi:10.1016/j.ejc.2015.02.027

Wheel-free planar graphs

Pierre Aboulker, Maria Chudnovsky, Paul Seymour, Nicolas Trotignon

Mathematics

Research output: Contribution to journal › Article › peer-review

4 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 language	English (US)
Pages (from-to)	57-67
Number of pages	11
Journal	European Journal of Combinatorics
Volume	49
DOIs	https://doi.org/10.1016/j.ejc.2015.02.027
State	Published - Oct 1 2015

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2015.02.027

Cite this

@article{adfb5deadea84e0e81ff090b2d46149f,

title = "Wheel-free planar graphs",

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.",

author = "Pierre Aboulker and Maria Chudnovsky and Paul Seymour and Nicolas Trotignon",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier Ltd.",

year = "2015",

month = oct,

day = "1",

doi = "10.1016/j.ejc.2015.02.027",

language = "English (US)",

volume = "49",

pages = "57--67",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Wheel-free planar graphs

AU - Aboulker, Pierre

AU - Chudnovsky, Maria

AU - Seymour, Paul

AU - Trotignon, Nicolas

PY - 2015/10/1

Y1 - 2015/10/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84924944070&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84924944070&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2015.02.027

DO - 10.1016/j.ejc.2015.02.027

M3 - Article

AN - SCOPUS:84924944070

SN - 0195-6698

VL - 49

SP - 57

EP - 67

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -

Wheel-free planar graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this