Polynomial -binding functions for t-broom-free graphs

DOI10.1016/J.JCTB.2023.04.005MaRDI QIDQ6170792zbMATH OpenFDO

Authors Xiaonan Liu, Joshua Schroeder, Zhiyu Wang, Xingxing Yu

Publication date 10 August 2023

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

\(t\)-broom-free graphschair-free graphspolynomial \(\chi\)-boundednesspolynomial binding function

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Structural characterization of families of graphs (05C75) Ramsey theory (05D10)

Abstract: For any positive integer $t$, a emph{$t$-broom} is a graph obtained from $K_{1,t+1}$ by subdividing an edge once. In this paper, we show that, for graphs $G$ without induced $t$-brooms, we have $chi(G)=o(omega(G{)}^{t+1})$, where $chi(G)$ and $omega(G)$ are the chromatic number and clique number of $G$, respectively. When $t=2$, this answers a question of Schiermeyer and Randerath. Moreover, for $t=2$, we strengthen the bound on $chi(G)$ to $7omega(G{)}^2$, confirming a conjecture of Sivaraman. For $tgeq3$ and {$t$-broom, $K_{t,t}$}-free graphs, we improve the bound to $o(omeg{a}^t)$.

Recommendations

• Chromatic number of triangle-free graphs with some forbidden subgraphs
• The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices
• Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree
• Induced subgraphs of graphs with large chromatic number. XIII. New brooms
• On the chromatic number of \((P_{5},K_{2,t})\)-free graphs

Cites work

• A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
• A note on Ramsey numbers
• Coloring graph classes with no induced fork via perfect divisibility
• Graph Theory and Probability
• 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?)
• Induced subgraphs of graphs with large chromatic number. XII. Distant stars
• Induced subgraphs of graphs with large chromatic number. XIII. New brooms
• Induced subtrees in graphs of large chromatic number
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Polynomial bounds for chromatic number. III. Excluding a double star
• Radius Three Trees in Graphs with Large Chromatic Number
• Radius two trees specify χ‐bounded classes
• Ramsey-type theorems
• Square-free graphs with no induced fork
• Sur le coloriage des graphs
• The early evolution of the \(H\)-free process
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The strong perfect graph theorem
• The structure of claw-free graphs
• The triangle-free process

Cited in

(17)

• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices
• Chromatic number of triangle-free graphs with some forbidden subgraphs
• Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree
• Graphs of bounded twin-width are quasi-polynomially -bounded
• Polynomial bounds for chromatic number II: Excluding a star‐forest
• Polynomial bounds for chromatic number. III. Excluding a double star
• Coloring of some crown-free graphs
• Polynomial bounds for chromatic number. V: Excluding a tree of radius two and a complete multipartite graph
• Perfect divisibility and coloring of some fork-free graphs
• \( \chi \)-binding function for \((C_4, t\text{-broom}^+)\)-free graphs
• Trisimplicial vertices in (fork, odd parachute)-free graphs
• A note on -binding functions and linear forests
• A survey of degree-boundedness
• -boundedness and related problems on graphs without long induced paths: a survey
• Perfect divisibility and coloring in fork-free graphs
• Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity

This page was built for publication: Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs

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