Browsing University of Waterloo by Subject "Erdos-Hanjnal conjecture"
Now showing items 1-1 of 1
-
Pure pairs. II. Excluding all subdivisions of a graph
(Springer Nature, 2021-06-01)We prove for every graph H there exists ɛ > 0 such that, for every graph G with |G|≥2, if no induced subgraph of G is a subdivision of H, then either some vertex of G has at least ɛ|G| neighbours, or there are two disjoint ...