@article{0e12d923654747b384833c365865d442,
title = "Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree",
abstract = "Let (Formula presented.) be a tree. It was proved by R{\"o}dl that graphs that do not contain (Formula presented.) as an induced subgraph, and do not contain the complete bipartite graph (Formula presented.) as a subgraph, have bounded chromatic number. Kierstead and Penrice strengthened this, showing that such graphs have bounded degeneracy. Here we give a further strengthening, proving that for every tree (Formula presented.), the degeneracy is at most polynomial in (Formula presented.). This answers a question of Bonamy, Bousquet, Pilipczuk, Rz{\c a}{\.z}ewski, Thomass{\'e}, and Walczak.",
keywords = "bipartite graphs, induced subgraphs",
author = "Alex Scott and Paul Seymour and Sophie Spirkl",
note = "Funding Information: Research supported by EPSRC grant EP/V007327/1 to Alex Scott and AFOSR grant A9550‐19‐1‐0187, and by NSF grant DMS‐1800053 to Paul Seymour. Sophie Spirkl: We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) (funding reference number RGPIN‐2020‐03912). Cette recherche a {\'e}t{\'e} financ{\'e}e par le Conseil de recherches en sciences naturelles et en g{\'e}nie du Canada (CRSNG) (num{\'e}ro de r{\'e}f{\'e}rence RGPIN‐2020‐03912). Open Access Funding provided by JISC ‐ UNIVERSITY OF OXFORD. Funding Information: We would like to express our thanks to Andr{\'a}s Gy{\'a}rf{\'a}s, who clarified the somewhat confusing history of the authorship of 1.2 for us. Thanks also to a referee for a careful and helpful reading. Research supported by EPSRC grant EP/V007327/1 to Alex Scott and AFOSR grant A9550-19-1-0187, and by NSF grant DMS-1800053 to Paul Seymour. Sophie Spirkl: We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) (funding reference number RGPIN-2020-03912). Cette recherche a {\'e}t{\'e} financ{\'e}e par le Conseil de recherches en sciences naturelles et en g{\'e}nie du Canada (CRSNG) (num{\'e}ro de r{\'e}f{\'e}rence RGPIN-2020-03912). Open Access Funding provided by JISC - UNIVERSITY OF OXFORD. Publisher Copyright: {\textcopyright} 2022 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.",
year = "2023",
month = mar,
doi = "10.1002/jgt.22880",
language = "English (US)",
volume = "102",
pages = "458--471",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "3",
}