Journal article icon

Journal article

Induced subgraphs of graphs with large chromatic number. VI. Banana trees

Abstract:

We investigate which graphs H have the property that in every graph with bounded clique number and sufficiently large chromatic number, some induced subgraph is isomorphic to a subdivision of H. In an earlier paper, the first author proved that every tree has this property; and in another earlier paper with Maria Chudnovsky, we proved that every cycle has this property. Here we give a common generalization. Say a “banana” is the union of a set of paths all with the same ends but otherwise dis...

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

Actions


Access Document


Files:
Publisher copy:
10.1016/j.jctb.2020.01.004

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Role:
Author
ORCID:
0000-0003-4489-5988
Publisher:
Elsevier
Journal:
Journal of Combinatorial Theory, Series B More from this journal
Volume:
145
Pages:
487-510
Publication date:
2020-01-27
Acceptance date:
2020-01-27
DOI:
EISSN:
1096-0902
ISSN:
0095-8956
Language:
English
Keywords:
Pubs id:
1084707
Local pid:
pubs:1084707
Deposit date:
2021-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