Abstract | ||
---|---|---|
It is known that every graph of sufficiently large chromatic number and bounded clique number contains, as an induced subgraph, a subdivision of any fixed forest, and a subdivision of any fixed cycle. Equivalently, every forest is pervasive, and K3 is pervasive, in the class of all graphs, where we say a graph H is “pervasive” (in some class of graphs) if for all ℓ≥1, every graph in the class of bounded clique number and sufficiently large chromatic number has an induced subgraph that is a subdivision of H, in which every edge of H is replaced by a path of at least ℓ edges. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1016/j.jctb.2021.05.001 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Colouring,χ-bounded,String graph | Journal | 150 |
ISSN | Citations | PageRank |
0095-8956 | 0 | 0.34 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Maria Chudnovsky | 1 | 390 | 46.13 |
Alex Scott | 2 | 251 | 40.93 |
Paul D. Seymour | 3 | 0 | 0.68 |