Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree

Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

Let (Formula presented.) be a tree. It was proved by Rödl that graphs that do not contain (Formula presented.) as an induced subgraph, and do not contain the complete bipartite graph (Formula presented.) as a subgraph, have bounded chromatic number. Kierstead and Penrice strengthened this, showing that such graphs have bounded degeneracy. Here we give a further strengthening, proving that for every tree (Formula presented.), the degeneracy is at most polynomial in (Formula presented.). This answers a question of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak.

Original languageEnglish (US)
Pages (from-to)458-471
Number of pages14
JournalJournal of Graph Theory
Volume102
Issue number3
DOIs
StatePublished - Mar 2023

All Science Journal Classification (ASJC) codes

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Keywords

  • bipartite graphs
  • induced subgraphs

Fingerprint

Dive into the research topics of 'Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree'. Together they form a unique fingerprint.

Cite this