2017/01/19 by Alex Scott, Scott, Alex, Paul Seymour +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1701.05597
openalex publication_date 2017/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate which graphs H have the property that in every graph with\nbounded clique number and sufficiently large chromatic number, some induced\nsubgraph is isomorphic to a subdivision of H. In an earlier paper, one of us\nproved that every tree has this property; and in another earlier paper with M.\nChudnovsky, we proved that every cycle has this property. Here we give a common\ngeneralization. Say a banana is the union of a set of paths all with the same\nends but otherwise disjoint. We prove that if H is obtained from a tree by\nreplacing each edge by a banana then H has the property mentioned. We also find\nsome other multigraphs with the same property.\n