Sparse graphs with no polynomial-sized anticomplete pairs

arXiv1810.00058MaRDI QIDQ6307461FDOQ6307461

Maria Chudnovsky, Paul Seymour, Jacob Fox, Sophie Spirkl, Alex Scott

Publication date: 28 September 2018

Abstract: A graph is "$H$-free" if it has no induced subgraph isomorphic to $H$. A conjecture of Conlon, Fox and Sudakov states that for every graph $H$, there exists $s>0$ such that in every $H$-free graph with $n>1$ vertices, either some vertex has degree at least $sn$, or there are two disjoint sets of vertices, of sizes at least $s{n}^s$ and $sn$, anticomplete to each other. We prove this holds for a large class of graphs $H$, and we prove that something like it holds for all graphs $H$. Say $H$ is "almost-bipartite" if $H$ is triangle-free and $V(H)$ can be partitioned into a stable set and a set inducing a graph of maximum degree at most one. We prove that the conjecture above holds for when $H$ is almost-bipartite. We also prove a stronger version where instead of excluding $H$ we restrict the number of copies of $H$. We prove some variations on the conjecture, such as: for every graph $H$, there exists $s>0$ such that in every $H$-free graph with $n>1$ vertices, either some vertex has degree at least $sn$, or there are two disjoint sets $A,B$ of vertices with $|A||B|>s{n}^{1+s}$, anticomplete to each other.

This page was built for publication: Sparse graphs with no polynomial-sized anticomplete pairs

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