dc.contributor.author | Chudnovsky, Maria | |
dc.contributor.author | Scott, Alex | |
dc.contributor.author | Seymour, Paul | |
dc.contributor.author | Spirkl, Sophie | |
dc.date.accessioned | 2023-05-26 19:19:08 (GMT) | |
dc.date.available | 2023-05-26 19:19:08 (GMT) | |
dc.date.issued | 2023-05-14 | |
dc.identifier.uri | https://doi.org/10.1002/jgt.22987 | |
dc.identifier.uri | http://hdl.handle.net/10012/19494 | |
dc.description | © 2023 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.
This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited. More information about this license is found here: https://creativecommons.org/licenses/by/4.0/ | en |
dc.description.abstract | A hole in a graph G is an induced cycle of length at least four, and a k-multihole in G is the union of k pairwise disjoint and nonneighbouring holes. It is well known that if G does not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any integer k>1, if G does not contain a k-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 x-bounded. | en |
dc.description.sponsorship | Engineering and Physical Sciences Research Council. Grant Number: EP/V007327/1 || Air Force Office of Scientific Research. Grant Numbers: A9550-19-1-0187, FA9550-22-1-0234 || Natural Sciences and Engineering Research Council of Canada. Grant Number: RGPIN-2020-03912 || National Science Foundation. Grant Numbers: DMS-2120644, DMS-2154169. | en |
dc.language.iso | en | en |
dc.publisher | Wiley | en |
dc.relation.ispartofseries | Journal of Graph Theory; | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 International | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | colouring | en |
dc.subject | induced subgraph | en |
dc.subject | x-boundedness | en |
dc.title | Polynomial bounds for chromatic number VII. Disjoint holes. | en |
dc.type | Article | en |
dcterms.bibliographicCitation | Chudnovsky, M., Scott, A., Seymour, P., & Spirkl, S. (2023). Polynomial bounds for chromatic number VII. disjoint holes. Journal of Graph Theory. https://doi.org/10.1002/jgt.22987 | 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 |