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

DOI10.1016/J.EJC.2019.103024zbMATH Open1428.05118arXiv1807.03768OpenAlexW2978867875WikidataQ127178183 ScholiaQ127178183MaRDI QIDQ2011144FDOQ2011144

Authors: Alex Scott, Paul Seymour 

Publication date: 28 November 2019

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

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.

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

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

zbMATH Keywords

handles\((k_1, \ldots, k_n)\)-multibroom[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Gy%EF%BF%BD%EF%BF%BDrf%EF%BF%BD%EF%BF%BDs-Sumner+conjecture&go=Go Gy��rf��s-Sumner conjecture]

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Nombre chromatique et plus longs chemins d'un graphe
• Title not available (Why is that?)
• Induced subtrees in graphs of large chromatic number
• Radius two trees specify χ‐bounded classes
• Radius Three Trees in Graphs with Large Chromatic Number
• Title not available (Why is that?)
• Applications of hypergraph coloring to coloring graphs not inducing certain trees
• Induced subgraphs of graphs with large chromatic number. XII. Distant stars

Cited In (16)

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

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)