Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph

Tung Nguyen; Alex Scott; Paul Seymour

doi:10.1002/jgt.23129

Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph

Tung Nguyen, Alex Scott, Paul Seymour

Mathematics

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

Abstract

We prove that for every path (Formula presented.), and every integer (Formula presented.), there is a polynomial (Formula presented.) such that every graph (Formula presented.) with chromatic number greater than (Formula presented.) either contains (Formula presented.) as an induced subgraph, or contains as a subgraph the complete (Formula presented.) -partite graph with parts of cardinality (Formula presented.). For (Formula presented.) and general (Formula presented.) this is a classical theorem of Gyárfás, and for (Formula presented.) and general (Formula presented.) this is a theorem of Bonamy et al.

Original language	English (US)
Pages (from-to)	509-521
Number of pages	13
Journal	Journal of Graph Theory
Volume	107
Issue number	3
DOIs	https://doi.org/10.1002/jgt.23129
State	Published - Nov 2024

All Science Journal Classification (ASJC) codes

Geometry and Topology
Discrete Mathematics and Combinatorics

Keywords

chromatic number
induced subgraphs

Access to Document

10.1002/jgt.23129

Cite this

@article{5d97b00043a54944a13f6bf7e1fc642c,

title = "Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph",

abstract = "We prove that for every path (Formula presented.), and every integer (Formula presented.), there is a polynomial (Formula presented.) such that every graph (Formula presented.) with chromatic number greater than (Formula presented.) either contains (Formula presented.) as an induced subgraph, or contains as a subgraph the complete (Formula presented.) -partite graph with parts of cardinality (Formula presented.). For (Formula presented.) and general (Formula presented.) this is a classical theorem of Gy{\'a}rf{\'a}s, and for (Formula presented.) and general (Formula presented.) this is a theorem of Bonamy et al.",

keywords = "chromatic number, induced subgraphs",

author = "Tung Nguyen and Alex Scott and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2024 The Author(s). Journal of Graph Theory published by Wiley Periodicals LLC.",

year = "2024",

month = nov,

doi = "10.1002/jgt.23129",

language = "English (US)",

volume = "107",

pages = "509--521",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph

AU - Nguyen, Tung

AU - Scott, Alex

AU - Seymour, Paul

PY - 2024/11

Y1 - 2024/11

N2 - We prove that for every path (Formula presented.), and every integer (Formula presented.), there is a polynomial (Formula presented.) such that every graph (Formula presented.) with chromatic number greater than (Formula presented.) either contains (Formula presented.) as an induced subgraph, or contains as a subgraph the complete (Formula presented.) -partite graph with parts of cardinality (Formula presented.). For (Formula presented.) and general (Formula presented.) this is a classical theorem of Gyárfás, and for (Formula presented.) and general (Formula presented.) this is a theorem of Bonamy et al.

AB - We prove that for every path (Formula presented.), and every integer (Formula presented.), there is a polynomial (Formula presented.) such that every graph (Formula presented.) with chromatic number greater than (Formula presented.) either contains (Formula presented.) as an induced subgraph, or contains as a subgraph the complete (Formula presented.) -partite graph with parts of cardinality (Formula presented.). For (Formula presented.) and general (Formula presented.) this is a classical theorem of Gyárfás, and for (Formula presented.) and general (Formula presented.) this is a theorem of Bonamy et al.

KW - chromatic number

KW - induced subgraphs

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

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

U2 - 10.1002/jgt.23129

DO - 10.1002/jgt.23129

M3 - Article

AN - SCOPUS:85196717564

SN - 0364-9024

VL - 107

SP - 509

EP - 521

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this