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

Alex Scott, Paul Seymour

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)487-510
Number of pages24
JournalJournal of Combinatorial Theory. Series B
Volume145
DOIs
StatePublished - Nov 2020

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Graph colouring
  • Trees
  • χ-boundedness

Fingerprint Dive into the research topics of 'Induced subgraphs of graphs with large chromatic number. VI. Banana trees'. Together they form a unique fingerprint.

Cite this