Premium
Triangle‐free graphs with large chromatic number and no induced wheel
Author(s) -
Davies James
Publication year - 2023
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22906
Subject(s) - combinatorics , mathematics , chromatic scale , conjecture , windmill graph , wheel graph , vertex (graph theory) , graph , petersen graph , discrete mathematics , line graph , graph power
A wheel is a graph consisting of an induced cycle of length at least four and a single additional vertex with at least three neighbours on the cycle. We prove that no Burling graph contains an induced wheel. Burling graphs are triangle‐free and have arbitrarily large chromatic number, so this answers a question of Trotignon and disproves a conjecture of Scott and Seymour.