@article{62248bedae564e83a3d80c1c0669301b,

title = "Polynomial bounds for chromatic number VII. Disjoint holes",

abstract = "A hole in a graph (Figure presented.) is an induced cycle of length at least four, and a (Figure presented.) -multihole in (Figure presented.) is the union of (Figure presented.) pairwise disjoint and nonneighbouring holes. It is well known that if (Figure presented.) does not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any integer (Figure presented.), if (Figure presented.) does not contain a (Figure presented.) -multihole, then its chromatic number is at most a polynomial function of its clique number. We show that the same result holds if we ask for all the holes to be odd or of length four; and if we ask for the holes to be longer than any fixed constant or of length four. This is part of a broader study of graph classes that are polynomially (Figure presented.) -bounded.",

keywords = "-boundedness, colouring, induced subgraph",

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

note = "Funding Information: Chudnovsky: Supported by NSF grant DMS-2120644. Scott: Research supported by EPSRC grant EP/V007327/1. Seymour: Supported by AFOSR grants A9550-19-1-0187 and FA9550-22-1-0234, and NSF grant DMS-2154169. 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). Funding Information: Chudnovsky: Supported by NSF grant DMS‐2120644. Scott: Research supported by EPSRC grant EP/V007327/1. Seymour: Supported by AFOSR grants A9550‐19‐1‐0187 and FA9550‐22‐1‐0234, and NSF grant DMS‐2154169. 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). Publisher Copyright: {\textcopyright} 2023 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.",

year = "2023",

doi = "10.1002/jgt.22987",

language = "English (US)",

volume = "104",

pages = "499--515",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}