Induced subgraphs of graphs with large chromatic number. VI. Banana trees
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 pa...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2020
|
| Summary: | 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 disjoint. We prove that if H is obtained from a tree by replacing each edge by a banana then H has the property mentioned. |
|---|