Wheel-free planar graphs

Pierre Aboulker, Maria Chudnovsky, Paul Seymour, Nicolas Trotignon

Resultado de la investigación: Article

1 Cita (Scopus)

Resumen

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.

Idioma originalEnglish
Páginas (desde-hasta)57-67
Número de páginas11
PublicaciónEuropean Journal of Combinatorics
Volumen49
DOI
EstadoPublished - 1 oct 2015
Publicado de forma externa

Huella dactilar

Planar graph
Wheel
Induced Subgraph
Cutset
Line Graph
Clique
Connected graph
Cycle
Graph in graph theory
Vertex of a graph

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Citar esto

Aboulker, P., Chudnovsky, M., Seymour, P., & Trotignon, N. (2015). Wheel-free planar graphs. European Journal of Combinatorics, 49, 57-67. https://doi.org/10.1016/j.ejc.2015.02.027
Aboulker, Pierre ; Chudnovsky, Maria ; Seymour, Paul ; Trotignon, Nicolas. / Wheel-free planar graphs. En: European Journal of Combinatorics. 2015 ; Vol. 49. pp. 57-67.
@article{f3974bbdca38449bb9d1914542a1ee99,
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",
year = "2015",
month = "10",
day = "1",
doi = "10.1016/j.ejc.2015.02.027",
language = "English",
volume = "49",
pages = "57--67",
journal = "European Journal of Combinatorics",
issn = "0195-6698",
publisher = "Academic Press Inc.",

}

Aboulker, P, Chudnovsky, M, Seymour, P & Trotignon, N 2015, 'Wheel-free planar graphs', European Journal of Combinatorics, vol. 49, pp. 57-67. https://doi.org/10.1016/j.ejc.2015.02.027

Wheel-free planar graphs. / Aboulker, Pierre; Chudnovsky, Maria; Seymour, Paul; Trotignon, Nicolas.

En: European Journal of Combinatorics, Vol. 49, 01.10.2015, p. 57-67.

Resultado de la investigación: Article

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

U2 - 10.1016/j.ejc.2015.02.027

DO - 10.1016/j.ejc.2015.02.027

M3 - Article

AN - SCOPUS:84924944070

VL - 49

SP - 57

EP - 67

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

ER -

Aboulker P, Chudnovsky M, Seymour P, Trotignon N. Wheel-free planar graphs. European Journal of Combinatorics. 2015 oct 1;49:57-67. https://doi.org/10.1016/j.ejc.2015.02.027