Sparse Partitions of Graphs with Bounded Clique Number

Abstract

We prove that for each integer $r\ge 2$, there exists a constant $C_r>0$ with the following property: for any $0<\epsilon \le 1/2$ and any graph $G$ with clique number at most $r,$ there is a partition of $V(G)$ into at most $(1/\epsilon {)}^{C_r}$ sets $S_1,\dots ,S_t,$ such that $G[S_i]$ has maximum degree at most $\epsilon |S_i|$ for each $1\le i\le t.$ This answers a question of Fox, Nguyen, Scott and Seymour, who proved a similar result for graphs with no induced $P_4.$

8 pp