Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path

Alex Scott; Paul Seymour; Sophie Spirkl

doi:10.1007/s00493-023-00015-w

Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path

Alex Scott, Paul Seymour, Sophie Spirkl

Mathematics

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

22 Scopus citations

Abstract

A graph G is H -free if it has no induced subgraph isomorphic to H. We prove that a P₅ -free graph with clique number ω≥ 3 has chromatic number at most ωlog2(ω) . The best previous result was an exponential upper bound (5 / 27) 3 ^ω , due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for P₅ , which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for P₅ -free graphs, and our result is an attempt to approach that.

Original language	English (US)
Pages (from-to)	845-852
Number of pages	8
Journal	Combinatorica
Volume	43
Issue number	5
DOIs	https://doi.org/10.1007/s00493-023-00015-w
State	Published - Oct 2023

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Keywords

Chromatic number
Induced subgraphs

Access to Document

10.1007/s00493-023-00015-w

Cite this

@article{44e633b1192346c8a73087cd8ddd6036,

title = "Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path",

abstract = "A graph G is H -free if it has no induced subgraph isomorphic to H. We prove that a P5 -free graph with clique number ω≥ 3 has chromatic number at most ωlog2(ω) . The best previous result was an exponential upper bound (5 / 27) 3 ω , due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erd{\H o}s-Hajnal conjecture holds for P5 , which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for P5 -free graphs, and our result is an attempt to approach that.",

keywords = "Chromatic number, Induced subgraphs",

author = "Alex Scott and Paul Seymour and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s).",

year = "2023",

month = oct,

doi = "10.1007/s00493-023-00015-w",

language = "English (US)",

volume = "43",

pages = "845--852",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "5",

}

TY - JOUR

T1 - Polynomial Bounds for Chromatic Number. IV

T2 - A Near-polynomial Bound for Excluding the Five-vertex Path

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2023/10

Y1 - 2023/10

N2 - A graph G is H -free if it has no induced subgraph isomorphic to H. We prove that a P5 -free graph with clique number ω≥ 3 has chromatic number at most ωlog2(ω) . The best previous result was an exponential upper bound (5 / 27) 3 ω , due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for P5 , which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for P5 -free graphs, and our result is an attempt to approach that.

AB - A graph G is H -free if it has no induced subgraph isomorphic to H. We prove that a P5 -free graph with clique number ω≥ 3 has chromatic number at most ωlog2(ω) . The best previous result was an exponential upper bound (5 / 27) 3 ω , due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for P5 , which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for P5 -free graphs, and our result is an attempt to approach that.

KW - Chromatic number

KW - Induced subgraphs

UR - https://www.scopus.com/pages/publications/85171303255

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

U2 - 10.1007/s00493-023-00015-w

DO - 10.1007/s00493-023-00015-w

M3 - Article

AN - SCOPUS:85171303255

SN - 0209-9683

VL - 43

SP - 845

EP - 852

JO - Combinatorica

JF - Combinatorica

IS - 5

ER -

Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this