Browsing Combinatorics and Optimization by Author "Fox, Jacob"

Now showing items 1-2 of 2

Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs

Chudnovsky, Maria; Fox, Jacob; Scott, Alex; Seymour, Paul; Spirkl, Sophie (Wiley, 2020-11)

A graph is H-free if it has no induced subgraph isomorphic to H, and |G| denotes the number of vertices of G. A conjecture of Conlon, Sudakov and the second author asserts that: - For every graph H, there exists ∈ > 0 ...
Towards Erdős-Hajnal for Graphs with No 5-Hole

Chudnovsky, Maria; Fox, Jacob; Scott, Alex; Seymour, Paul; Spirkl, Sophie (Springer Nature, 2019-11-01)

The Erdős-Hajnal conjecture says that for every graph H there exists c > 0 such that max(α(G), w(G)) ≥ nc for every H-free graph G with n vertices, and this is still open when H = C5. Until now the best bound known on ...