dc.contributor.author | Scott, Alex | |
dc.contributor.author | Seymour, Paul | |
dc.contributor.author | Spirkl, Sophie | |
dc.date.accessioned | 2023-12-05 14:32:21 (GMT) | |
dc.date.available | 2023-12-05 14:32:21 (GMT) | |
dc.date.issued | 2023-09-15 | |
dc.identifier.uri | https://doi.org/10.1007/s00493-023-00015-w | |
dc.identifier.uri | http://hdl.handle.net/10012/20133 | |
dc.description | This article is made available open access through a Creative Commons Attribution 4.0 International license http://creativecommons.org/licenses/by/4.0/ | en |
dc.description.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˝os-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. | en |
dc.language.iso | en | en |
dc.publisher | Springer | en |
dc.relation.ispartofseries | Combinatorica;43 | |
dc.rights | Attribution 4.0 International | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | * |
dc.subject | chromatic number | en |
dc.subject | induced subgraphs | en |
dc.title | Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path | en |
dc.type | Article | en |
dcterms.bibliographicCitation | Scott, A., Seymour, P., & Spirkl, S. (2023). Polynomial bounds for chromatic number. IV: A near-polynomial bound for excluding the five-vertex path. Combinatorica, 43(5), 845–852. https://doi.org/10.1007/s00493-023-00015-w | en |
uws.contributor.affiliation1 | Faculty of Mathematics | en |
uws.contributor.affiliation2 | Combinatorics and Optimization | en |
uws.typeOfResource | Text | en |
uws.peerReviewStatus | Reviewed | en |
uws.scholarLevel | Faculty | en |