Excluding clocks

Pierre Aboulker; Zhentao Li; Stéphan Thomassé

doi:10.1016/j.endm.2015.07.018

Excluding clocks

Pierre Aboulker, Zhentao Li, Stéphan Thomassé

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	103-108
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	50
DOIs	https://doi.org/10.1016/j.endm.2015.07.018
Publication status	Published - 1 Dec 2015
Externally published	Yes

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2015.07.018

Cite this

@article{8889cd65028c4587ad43d6081aa6f37d,

title = "Excluding clocks",

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

author = "Pierre Aboulker and Zhentao Li and St{\'e}phan Thomass{\'e}",

year = "2015",

month = dec,

day = "1",

doi = "10.1016/j.endm.2015.07.018",

language = "English",

volume = "50",

pages = "103--108",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Excluding clocks

AU - Aboulker, Pierre

AU - Li, Zhentao

AU - Thomassé, Stéphan

PY - 2015/12/1

Y1 - 2015/12/1

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

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

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

U2 - 10.1016/j.endm.2015.07.018

DO - 10.1016/j.endm.2015.07.018

M3 - Article

AN - SCOPUS:84953373684

VL - 50

SP - 103

EP - 108

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

ER -

Excluding clocks

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this