Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph

Alex Scott, Paul Seymour

Research output: Contribution to journalArticlepeer-review

Abstract

The Gyárfás-Sumner conjecture says that for every forest H and every integer k, if G is H-free and does not contain a clique on k vertices then it has bounded chromatic number. (A graph is H-free if it does not contain an induced copy of H.) Kierstead and Penrice proved it for trees of radius at most two, but otherwise the conjecture is known only for a few simple types of forest. More is known if we exclude a complete bipartite subgraph instead of a clique: Rödl showed that, for every forest H, if G is H-free and does not contain Kt,t as a subgraph then it has bounded chromatic number. In an earlier paper with Sophie Spirkl, we strengthened Rödl's result, showing that for every forest H, the bound on chromatic number can be taken to be polynomial in t. In this paper, we prove a related strengthening of the Kierstead-Penrice theorem, showing that for every tree H of radius two and integer d≥2, if G is H-free and does not contain as a subgraph the complete d-partite graph with parts of cardinality t, then its chromatic number is at most polynomial in t.

Original languageEnglish (US)
Pages (from-to)473-491
Number of pages19
JournalJournal of Combinatorial Theory. Series B
Volume164
DOIs
StatePublished - Jan 2024

All Science Journal Classification (ASJC) codes

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

Keywords

  • Chromatic number
  • Complete multipartite graph
  • Induced subgraph

Fingerprint

Dive into the research topics of 'Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph'. Together they form a unique fingerprint.

Cite this