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.03686MaRDI 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

05C35: Extremal problems in graph theory

05C75: Structural characterization of families of graphs

05C15: Coloring of graphs and hypergraphs

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree, Polynomial bounds for chromatic number VII. Disjoint holes

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