Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes

Alex Scott; Paul Seymour

doi:10.1016/j.jctb.2018.03.006

Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes

Alex Scott, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

A hole in a graph is an induced subgraph which is a cycle of length at least four. We prove that for all ν>0, every triangle-free graph with sufficiently large chromatic number contains holes of ν consecutive lengths.

Original language	English (US)
Pages (from-to)	180-235
Number of pages	56
Journal	Journal of Combinatorial Theory. Series B
Volume	132
DOIs	https://doi.org/10.1016/j.jctb.2018.03.006
State	Published - Sep 2018

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Graph colouring
Holes
Induced subgraphs
χ-boundedness

Access to Document

10.1016/j.jctb.2018.03.006

Cite this

@article{5205f299d3a94891946e7de3c6a10fe0,

title = "Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes",

abstract = "A hole in a graph is an induced subgraph which is a cycle of length at least four. We prove that for all ν>0, every triangle-free graph with sufficiently large chromatic number contains holes of ν consecutive lengths.",

keywords = "Graph colouring, Holes, Induced subgraphs, χ-boundedness",

author = "Alex Scott and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier Inc.",

year = "2018",

month = sep,

doi = "10.1016/j.jctb.2018.03.006",

language = "English (US)",

volume = "132",

pages = "180--235",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes

AU - Scott, Alex

AU - Seymour, Paul

PY - 2018/9

Y1 - 2018/9

N2 - A hole in a graph is an induced subgraph which is a cycle of length at least four. We prove that for all ν>0, every triangle-free graph with sufficiently large chromatic number contains holes of ν consecutive lengths.

AB - A hole in a graph is an induced subgraph which is a cycle of length at least four. We prove that for all ν>0, every triangle-free graph with sufficiently large chromatic number contains holes of ν consecutive lengths.

KW - Graph colouring

KW - Holes

KW - Induced subgraphs

KW - χ-boundedness

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

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

U2 - 10.1016/j.jctb.2018.03.006

DO - 10.1016/j.jctb.2018.03.006

M3 - Article

AN - SCOPUS:85045018191

SN - 0095-8956

VL - 132

SP - 180

EP - 235

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this