Excluding clocks

Pierre Aboulker, Zhentao Li, Stéphan Thomassé

Research output: Contribution to journalArticlepeer-review

Abstract

A clock is a cycle with a vertex that has exactly two neighbors on the cycle. We show that (triangle, cube, clock)-free graphs of girth at least 9 always contain a vertex of degree 2, partially answering to a conjecture of Trotignon. As a second result, we show that the class of clock-free graphs is χ-bounded by max(4, ω(G)).

Original languageEnglish
Pages (from-to)103-108
Number of pages6
JournalElectronic Notes in Discrete Mathematics
Volume50
DOIs
Publication statusPublished - 1 Dec 2015
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Excluding clocks'. Together they form a unique fingerprint.

Cite this