Excluding clocks

Pierre Aboulker, Zhentao Li, Stéphan Thomassé

Resultado de la investigación: Article

Resumen

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

Idioma originalEnglish
Páginas (desde-hasta)103-108
Número de páginas6
PublicaciónElectronic Notes in Discrete Mathematics
Volumen50
DOI
EstadoPublished - 1 dic 2015
Publicado de forma externa

Huella dactilar

Clocks
Cycle
Girth
Graph in graph theory
Vertex of a graph
Regular hexahedron
Triangle
Class

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Citar esto

Aboulker, Pierre ; Li, Zhentao ; Thomassé, Stéphan. / Excluding clocks. En: Electronic Notes in Discrete Mathematics. 2015 ; Vol. 50. pp. 103-108.
@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 = "12",
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",

}

Aboulker, P, Li, Z & Thomassé, S 2015, 'Excluding clocks', Electronic Notes in Discrete Mathematics, vol. 50, pp. 103-108. https://doi.org/10.1016/j.endm.2015.07.018

Excluding clocks. / Aboulker, Pierre; Li, Zhentao; Thomassé, Stéphan.

En: Electronic Notes in Discrete Mathematics, Vol. 50, 01.12.2015, p. 103-108.

Resultado de la investigación: Article

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 -