Wheel-free planar graphs

Pierre Aboulker, Maria Chudnovsky, Paul Seymour, Nicolas Trotignon

Resultado de la investigación: Contribución a una revistaArtículo

2 Citas (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 originalInglés
Páginas (desde-hasta)57-67
Número de páginas11
PublicaciónEuropean Journal of Combinatorics
Volumen49
DOI
EstadoPublicada - 1 oct 2015
Publicado de forma externa

Áreas temáticas de ASJC Scopus

  • Matemáticas discretas y combinatorias

Huella Profundice en los temas de investigación de 'Wheel-free planar graphs'. En conjunto forman una huella única.

  • 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