Erdös--Hajnal Properties for Powers of Sparse Graphs
From MaRDI portal
Publication:5857003
DOI10.1137/20M1342756zbMath1460.05103arXiv2006.01500OpenAlexW3137762725MaRDI QIDQ5857003
Marcin Briański, Michał Pilipczuk, Piotr Micek, Michał T. Seweryn
Publication date: 30 March 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2006.01500
Related Items
Rainbow independent sets on dense graph classes, Bounding generalized coloring numbers of planar graphs using coin models
Cites Work
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- Turán-type results for partial orders and intersection graphs of convex sets
- Characterisations and examples of graph classes with bounded expansion
- Ramsey-type theorems
- Colouring graphs with bounded generalized colouring number
- Polynomial bounds for centered colorings on proper minor-closed graph classes
- Clustering powers of sparse graphs
- Regular partitions of gentle graphs
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- On nowhere dense graphs
- Interpreting nowhere dense graph classes as a classical notion of model theory
- Crossing patterns of semi-algebraic sets
- The Erdös-Hajnal Conjecture-A Survey
- Extremal Combinatorics
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Deciding First-Order Properties of Nowhere Dense Graphs
- Neighborhood complexity and kernelization for nowhere dense classes of graphs
- First-Order Interpretations of Bounded Expansion Classes
- On the number of types in sparse graphs
- Testing first-order properties for subclasses of sparse graphs
- Regularity lemmas for stable graphs
- On low rank-width colorings
- Pure pairs. V: Excluding some long subdivision
