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 [6], the first author proved that every tree has this property; and in another earlier paper with Maria Chudnovsky [2], 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 disjoint. We prove that if H is obtained from a tree by replacing each edge by a banana then H has the property mentioned.
Original language | American English |
---|---|
Pages (from-to) | 487-510 |
Number of pages | 24 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 145 |
DOIs | |
State | Published - Nov 2020 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Keywords
- Graph colouring
- Trees
- χ-boundedness