On wheel-free graphs - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Reports (Research Report) Year : 2011

On wheel-free graphs

Abstract

A wheel is a graph formed by a chordless cycle and a vertex that has at least three neighbors in the cycle. We prove that every 3-connected graph that does not contain a wheel as a subgraph is in fact minimally 3-connected. We prove that every graph that does not contain a wheel as a subgraph is 3-colorable.

Domains

Discrete Mathematics [cs.DM]
Fichier principal
Vignette du fichier
RR-7651.pdf (321.81 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Frederic Havet  : Connect in order to contact the contributor

https://inria.hal.science/inria-00602079

Submitted on : Tuesday, June 21, 2011-2:44:21 PM

Last modification on : Monday, February 26, 2024-11:22:07 AM

Long-term archiving on: Friday, November 9, 2012-4:46:04 PM

Download

Dates and versions

inria-00602079 , version 1 (21-06-2011)

Identifiers

  • HAL Id : inria-00602079 , version 1

Cite

Pierre Aboulker, Frédéric Havet, Nicolas Trotignon. On wheel-free graphs. [Research Report] RR-7651, INRIA. 2011. ⟨inria-00602079⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

UNIV-PARIS7 CNRS INRIA LIAFA INRIA-RRRT I3S INRIA2 TDS-MACS LARA UNIV-COTEDAZUR
260 View
328 Download

Share

Gmail Facebook X LinkedIn More