Induced subgraphs of graphs with large chromatic number. XIII. New brooms

DOI10.1016/J.EJC.2019.103024MaRDI QIDQ2011144zbMATH OpenOpenAlexWikidataFDO

Authors Alex Scott, Paul Seymour

Publication date 28 November 2019

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.03768

zbMATH Keywords

handles\((k_1, \ldots, k_n)\)-multibroomGyárfás-Sumner conjecture

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Abstract: Gy'arf'as and Sumner independently conjectured that for every tree $T$, the class of graphs not containing $T$ as an induced subgraph is $chi$-bounded, that is, the chromatic numbers of graphs in this class are bounded above by a function of their clique numbers. This remains open for general trees $T$, but has been proved for some particular trees. For $kge1$, let us say a broom of length $k$ is a tree obtained from a $k$-edge path with ends $a,b$ by adding some number of leaves adjacent to $b$, and we call $a$ its handle. A tree obtained from brooms of lengths $k_1,\mathrm{...},k_n$ by identifying their handles is a $(k_1,\mathrm{...},k_n)$-multibroom. Kierstead and Penrice proved that every $(1,\mathrm{...},1)$-multibroom $T$ satisfies the Gy'arf'as-Sumner conjecture, and Kierstead and Zhu proved the same for $(2,\mathrm{...},2)$-multibrooms. In this paper give a common generalization: we prove that every $(1,\mathrm{...},1,2,\mathrm{...},2)$-multibroom satisfies the Gy'arf'as-Sumner conjecture.

Recommendations

• Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• Induced subgraphs of graphs with large chromatic number. VII: Gyárfás' complementation conjecture
• Induced subgraphs of graphs with large chromatic number. III: Long holes
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
• Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
• Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
• Induced subgraphs of graphs with large chromatic number. IV: Consecutive holes

Cites work

• scientific article; zbMATH DE number 1002021 (Why is no real title available?)
• scientific article; zbMATH DE number 3747156 (Why is no real title available?)
• scientific article; zbMATH DE number 3480625 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• Applications of hypergraph coloring to coloring graphs not inducing certain trees
• Induced subgraphs of graphs with large chromatic number. XII. Distant stars
• Induced subtrees in graphs of large chromatic number
• Nombre chromatique et plus longs chemins d'un graphe
• Radius Three Trees in Graphs with Large Chromatic Number
• Radius two trees specify χ‐bounded classes

Cited in

(16)

• Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
• Induced subgraphs of graphs with large chromatic number. VI. Banana trees
• Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs
• Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree
• Graphs of large chromatic number
• Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of \(P_4\)
• Polynomial bounds for chromatic number II: Excluding a star‐forest
• Polynomial bounds for chromatic number. III. Excluding a double star
• Polynomial bounds for chromatic number. VIII: Excluding a path and a complete multipartite graph
• Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree
• A note on the Gyárfás-Sumner conjecture
• Induced subgraphs of graphs with large chromatic number. XII. Distant stars

This page was built for publication: Induced subgraphs of graphs with large chromatic number. XIII. New brooms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011144)