Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs

DOI10.1016/j.jctb.2021.10.005zbMath1478.05047arXiv2012.03686OpenAlexW3209002032MaRDI QIDQ2664559

Michał Pilipczuk, Marthe Bonamy, Nicolas Bousquet, Bartosz Walczak, Paweł Rzążewski, Steé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

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

Mathematics Subject Classification ID

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

Related Items (3)

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

Cites Work

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

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