Every string graph with n vertices and at most (1/4 − ε)n²/2 edges contains two disjoint linear-size subsets with no edges between them; the constant 1/4 is sharp.
Pure pairs. II. Excluding all subdivisions of a graph
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We prove for every graph H there exists a>0 such that, for every graph G with at least two vertices, if no induced subgraph of G is a subdivision of H, then either some vertex of G has at least a|G| neighbours, or there are two disjoint sets A,B of at least a|G| vertices such that no edge joins A and B. It follows that for every graph H, there exists c>0 such that for every graph G, if no induced subgraph of G or its complement is a subdivision of H, then G has a clique or stable set of cardinality at least |G|^c. This is related to the Erdos-Hajnal conjecture.
fields
math.CO 1years
2019 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
A sharp threshold phenomenon in string graphs
Every string graph with n vertices and at most (1/4 − ε)n²/2 edges contains two disjoint linear-size subsets with no edges between them; the constant 1/4 is sharp.