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

Alex Scott; Paul Seymour; Sophie Spirkl

doi:10.1002/jgt.22880

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

Alex Scott, Paul Seymour, Sophie Spirkl

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

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 language	American English
Pages (from-to)	458-471
Number of pages	14
Journal	Journal of Graph Theory
Volume	102
Issue number	3
DOIs	https://doi.org/10.1002/jgt.22880
State	Published - Mar 2023

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Keywords

bipartite graphs
induced subgraphs

Access to Document

10.1002/jgt.22880

Cite this

@article{1074b85ddfc849fcb098e658879bfffd,

title = "Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree",

abstract = "Let (Formula presented.) be a tree. It was proved by R{\"o}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{\c a}{\.z}ewski, Thomass{\'e}, and Walczak.",

keywords = "bipartite graphs, induced subgraphs",

author = "Alex Scott and Paul Seymour and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} 2022 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.",

year = "2023",

month = mar,

doi = "10.1002/jgt.22880",

language = "American English",

volume = "102",

pages = "458--471",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

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

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2023/3

Y1 - 2023/3

N2 - 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.

AB - 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.

KW - bipartite graphs

KW - induced subgraphs

UR - http://www.scopus.com/inward/record.url?scp=85137418527&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85137418527&partnerID=8YFLogxK

U2 - 10.1002/jgt.22880

DO - 10.1002/jgt.22880

M3 - Article

SN - 0364-9024

VL - 102

SP - 458

EP - 471

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

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

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this