Journal article icon

Journal article

Polynomial bounds for chromatic number II: excluding a star-forest

Abstract:

The Gyarfas-Sumner conjecture says that for every forest $H$, there is a function $f$ such that if $G$ is $H$-free then $\chi(G)\le f(\omega(G))$ (where $\chi, \omega$ are the chromatic number and the clique number of $G$). Louis Esperet conjectured that, whenever such a statement holds, $f$ can be chosen to be a polynomial. The Gyarfas-Sumner conjecture is only known to be true for a modest set of forests $H$, and Esperet's conjecture is known to be true for almost no forests. For instance, ...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1002/jgt.22829

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Oxford college:
Merton College
Role:
Author
ORCID:
0000-0003-4489-5988
Publisher:
Wiley
Journal:
Journal of Graph Theory More from this journal
Volume:
101
Issue:
2
Pages:
318-322
Publication date:
2022-04-04
Acceptance date:
2022-03-16
DOI:
EISSN:
1097-0118
ISSN:
0364-9024
Language:
English
Keywords:
Subjects:
Pubs id:
1189442
Local pid:
pubs:1189442
Deposit date:
2022-01-09

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP