A survey of χ-boundedness

Alex Scott; Paul Seymour

doi:10.1002/jgt.22601

A survey of χ-boundedness

Alex Scott, Paul Seymour

Mathematics

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

87 Scopus citations

Abstract

If a graph has bounded clique number and sufficiently large chromatic number, what can we say about its induced subgraphs? András Gyárfás made a number of challenging conjectures about this in the early 1980s, which have remained open until recently; but in the last few years there has been substantial progress. This is a survey of where we are now.

Original language	English (US)
Pages (from-to)	473-504
Number of pages	32
Journal	Journal of Graph Theory
Volume	95
Issue number	3
DOIs	https://doi.org/10.1002/jgt.22601
State	Published - Nov 1 2020

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

colouring
χ-boundedness

Access to Document

10.1002/jgt.22601

Cite this

@article{1a781be704064b56ab0ba3145e0fc291,

title = "A survey of χ-boundedness",

abstract = "If a graph has bounded clique number and sufficiently large chromatic number, what can we say about its induced subgraphs? Andr{\'a}s Gy{\'a}rf{\'a}s made a number of challenging conjectures about this in the early 1980s, which have remained open until recently; but in the last few years there has been substantial progress. This is a survey of where we are now.",

keywords = "colouring, χ-boundedness",

author = "Alex Scott and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2020 Wiley Periodicals LLC",

year = "2020",

month = nov,

day = "1",

doi = "10.1002/jgt.22601",

language = "English (US)",

volume = "95",

pages = "473--504",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - A survey of χ-boundedness

AU - Scott, Alex

AU - Seymour, Paul

PY - 2020/11/1

Y1 - 2020/11/1

N2 - If a graph has bounded clique number and sufficiently large chromatic number, what can we say about its induced subgraphs? András Gyárfás made a number of challenging conjectures about this in the early 1980s, which have remained open until recently; but in the last few years there has been substantial progress. This is a survey of where we are now.

AB - If a graph has bounded clique number and sufficiently large chromatic number, what can we say about its induced subgraphs? András Gyárfás made a number of challenging conjectures about this in the early 1980s, which have remained open until recently; but in the last few years there has been substantial progress. This is a survey of where we are now.

KW - colouring

KW - χ-boundedness

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

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

U2 - 10.1002/jgt.22601

DO - 10.1002/jgt.22601

M3 - Article

AN - SCOPUS:85089733921

SN - 0364-9024

VL - 95

SP - 473

EP - 504

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

A survey of χ-boundedness

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this