Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph

TY - JOUR

T1 - Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph

AU - Scott, Alex

AU - Seymour, Paul

N1 - Publisher Copyright: © 2023

PY - 2024/1

Y1 - 2024/1

N2 - The Gyárfás-Sumner conjecture says that for every forest H and every integer k, if G is H-free and does not contain a clique on k vertices then it has bounded chromatic number. (A graph is H-free if it does not contain an induced copy of H.) Kierstead and Penrice proved it for trees of radius at most two, but otherwise the conjecture is known only for a few simple types of forest. More is known if we exclude a complete bipartite subgraph instead of a clique: Rödl showed that, for every forest H, if G is H-free and does not contain Kt,t as a subgraph then it has bounded chromatic number. In an earlier paper with Sophie Spirkl, we strengthened Rödl's result, showing that for every forest H, the bound on chromatic number can be taken to be polynomial in t. In this paper, we prove a related strengthening of the Kierstead-Penrice theorem, showing that for every tree H of radius two and integer d≥2, if G is H-free and does not contain as a subgraph the complete d-partite graph with parts of cardinality t, then its chromatic number is at most polynomial in t.

AB - The Gyárfás-Sumner conjecture says that for every forest H and every integer k, if G is H-free and does not contain a clique on k vertices then it has bounded chromatic number. (A graph is H-free if it does not contain an induced copy of H.) Kierstead and Penrice proved it for trees of radius at most two, but otherwise the conjecture is known only for a few simple types of forest. More is known if we exclude a complete bipartite subgraph instead of a clique: Rödl showed that, for every forest H, if G is H-free and does not contain Kt,t as a subgraph then it has bounded chromatic number. In an earlier paper with Sophie Spirkl, we strengthened Rödl's result, showing that for every forest H, the bound on chromatic number can be taken to be polynomial in t. In this paper, we prove a related strengthening of the Kierstead-Penrice theorem, showing that for every tree H of radius two and integer d≥2, if G is H-free and does not contain as a subgraph the complete d-partite graph with parts of cardinality t, then its chromatic number is at most polynomial in t.

KW - Chromatic number

KW - Complete multipartite graph

KW - Induced subgraph

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

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

U2 - 10.1016/j.jctb.2023.10.004

DO - 10.1016/j.jctb.2023.10.004

M3 - Article

SN - 0095-8956

VL - 164

SP - 473

EP - 491

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -