Degeneracy of P_t-free and C_ t-free graphs with no large complete bipartite subgraphs

DOI10.1016/J.JCTB.2021.10.005MaRDI QIDQ2664559zbMATH OpenOpenAlexFDO

Authors Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk, Bartosz Walczak, Paweł Rzążewski, Stéphan Thomassé

Publication date 17 November 2021

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

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

zbMATH Keywords

\(\chi\)-boundedness\(C_{\geqslant t}\)-free graphs\(P_t\)-free graphsbiclique

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75)

Abstract: A hereditary class of graphs $mathcalG$ is emph{$chi$-bounded} if there exists a function $f$ such that every graph $GinmathcalG$ satisfies $chi(G)leqf(omega(G))$, where $chi(G)$ and $omega(G)$ are the chromatic number and the clique number of $G$, respectively. As one of the first results about $chi$-bounded classes, Gy'{a}rf'{a}s proved in 1985 that if $G$ is $P_t$-free, i.e., does not contain a $t$-vertex path as an induced subgraph, then $chi(G)leq(t-1{)}^{omega(G)-1}$. In 2017, Chudnovsky, Scott, and Seymour proved that $C_{geqt}$-free graphs, i.e., graphs that exclude induced cycles with at least $t$ vertices, are $chi$-bounded as well, and the obtained bound is again superpolynomial in the clique number. Note that $P_{t-1}$-free graphs are in particular $C_{geqt}$-free. It remains a major open problem in the area whether for $C_{geqt}$-free, or at least $P_t$-free graphs $G$, the value of $chi(G)$ can be bounded from above by a polynomial function of $omega(G)$. We consider a relaxation of this problem, where we compare the chromatic number with the size of a largest balanced biclique contained in the graph as a (not necessarily induced) subgraph. We show that for every $t$ there exists a constant $c$ such that for and every $C_{geqt}$-free graph which does not contain $K_{ell,ell}$ as a subgraph, it holds that $chi(G)leqel{l}^c$.

Recommendations

• Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree
• On chromatic number of graphs without certain induced subgraphs.
• On the chromatic number of \((P_{5},K_{2,t})\)-free graphs
• Chromatic bounds for some classes of 2 K₂-free graphs
• Linearly \(\chi \)-bounding \((P_6, C_4)\)-free graphs

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• A survey of -boundedness
• An extremal function for contractions of graphs
• Applications of a new separator theorem for string graphs
• Coloring the hypergraph of maximal cliques of a graph with no long path
• Density theorems for bipartite graphs and related Ramsey-type results
• Every planar map is four colorable
• Extending the Gyárfás-Sumner conjecture
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time
• Graph Theory and Probability
• scientific article; zbMATH DE number 1002021 (Why is no real title available?)
• scientific article; zbMATH DE number 3865318 (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 4183452 (Why is no real title available?)
• In absence of long chordless cycles, large tree-width becomes a local phenomenon
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• Induced subgraphs of graphs with large chromatic number. III: Long holes
• Linear time algorithm for computing a small biclique in graphs without long induced paths
• Lower bound of the Hadwiger number of graphs by their average degree
• Near-optimal separators in string graphs
• On the density of families of sets
• On tree width, bramble size, and expansion
• Orderings on graphs and game coloring number
• Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
• Radius two trees specify χ‐bounded classes
• Ramsey-type theorems
• Ramsey-type theorems with forbidden subgraphs
• Separators in region intersection graphs
• Sparsity. Graphs, structures, and algorithms
• String graphs. I: The number of critical nonstring graphs is infinite
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• Subexponential-time algorithms for finding large induced sparse subgraphs
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
• Sur le coloriage des graphs
• The Erdős-Hajnal conjecture for bull-free graphs
• The Erdős-Hajnal conjecture. A survey
• The strong perfect graph theorem
• Theory of uniform convergence of frequencies of events to their probabilities and problems of search for an optimal solution from empirical data
• VC-dimension and Erdős-Pósa property

Cited in

(12)

• Colouring graphs with forbidden bipartite subgraphs
• Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree
• Polynomial bounds for chromatic number VII. Disjoint holes
• Polynomial bounds for chromatic number. V: Excluding a tree of radius two and a complete multipartite graph
• Polynomial bounds for chromatic number. VIII: Excluding a path and a complete multipartite graph
• Induced Turán problem in bipartite graphs
• Induced subdivisions in \(K_{s,s}\)-free graphs with polynomial average degree
• A survey of degree-boundedness
• Induced C₄-free subgraphs with large average degree
• Kővári-Sós-Turán theorem for hereditary families
• Treedepth and 2-treedepth in graphs with no long induced paths
• Sparse induced subgraphs in P₇-Free graphs of bounded clique number

This page was built for publication: Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs

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