Erdös-Hajnal properties for powers of sparse graphs

DOI10.1137/20M1342756MaRDI QIDQ5857003zbMATH OpenOpenAlexFDO

Authors Marcin Briański, Piotr Micek, Michał Pilipczuk, 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

zbMATH Keywords

Erdös-Hajnal conjecturegraph powergraph sparsityweak coloring numbers

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Graph minors (05C83)

Abstract: We prove that for every nowhere dense class of graphs $mathcalC$, positive integer $d$, and $varepsilon>0$, the following holds: in every $n$-vertex graph $G$ from $mathcalC$ one can find two disjoint vertex subsets $A,BsubseteqV(G)$ such that $|A|geq(1/2-varepsilon)cdotn$ and $|B|=Omega(n^{1-varepsilon})$ and either $operatornamedist(a,b)leqd$ for all $ainA$ and $binB$, or $operatornamedist(a,b)>d$ for all $ainA$ and $binB$. We also show some stronger variants of this statement, including a generalization to the setting of First-Order interpretations of nowhere dense graph classes.

Recommendations

• On nowhere dense graphs
• On the number of types in sparse graphs
• Sparsity. Graphs, structures, and algorithms
• Vertex-minors and the Erdős-Hajnal conjecture
• Clustering powers of sparse graphs

Cites work

• Approximation algorithms for polynomial-expansion and low-density graphs
• Characterisations and examples of graph classes with bounded expansion
• Clustering powers of sparse graphs
• Colouring graphs with bounded generalized colouring number
• Crossing patterns of semi-algebraic sets
• Erdős-Hajnal-type results on intersection patterns of geometric objects
• Extremal combinatorics. With applications in computer science
• First-order interpretations of bounded expansion classes
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• scientific article; zbMATH DE number 7029306 (Why is no real title available?)
• Interpreting nowhere dense graph classes as a classical notion of model theory
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• On low rank-width colorings
• On nowhere dense graphs
• On the number of types in sparse graphs
• Pure pairs. V: Excluding some long subdivision
• Ramsey-type theorems
• Regular partitions of gentle graphs
• Regularity lemmas for stable graphs
• Sparsity. Graphs, structures, and algorithms
• Testing first-order properties for subclasses of sparse graphs
• The Erdős-Hajnal conjecture. A survey
• Turán-type results for partial orders and intersection graphs of convex sets

Cited in

(8)

• Clustering powers of sparse graphs
• Bounds on half graph orders in powers of sparse graphs
• Bounding generalized coloring numbers of planar graphs using coin models
• Treelike decompositions for transductions of sparse graphs
• Indiscernibles in monadically NIP theories
• Decomposition horizons and a characterization of stable hereditary classes of graphs
• Turbocharging heuristics for weak coloring numbers
• Rainbow independent sets on dense graph classes

This page was built for publication: Erdös-Hajnal properties for powers of sparse graphs

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