String graphs have the Erd\H{o}s-Hajnal property

Publication date 24 February 2020

Abstract: A string graph is the intersection graph of curves in the plane. We prove that there exists an absolute constant

c > 0

such that if

G

is a string graph on

n

vertices, then

G

contains either a clique or an independent set of size at least

n^{c}

.

This page was built for publication: String graphs have the Erd\H{o}s-Hajnal property