In the 1960’s, Erdős and Gallai conjectured that the edges of any n-vertex graph can be decomposed into O(n) cycles and edges. We improve upon the previous best bound of O(n loglogn) cycles and edges due to Conlon, Fox and Sudakov, by showing an n-vertex graph can always be decomposed into O(n log⋆ n) cycles and edges, where log⋆n is the iterated logarithm function. Our arguments make use and further develop the theory of robust sublinear expander graphs.

A symmetric $m\times m$ matrix $M$ with entries taken from $\{0,1,\ast\}$ gives rise to a graph partition problem, asking whether a graph can be partitioned into $m$ vertex sets matched to the rows (and corresponding columns) of $M$ such that, if $M_{ij}=1$, then any two vertices between the corresponding vertex sets are joined by an edge and, if $M_{ij}=0$, then any two vertices between the corresponding vertex sets are not joined by an edge. The entry $\ast$ places no restriction on the edges between the corresponding sets. This problem generalizes graph coloring and graph homomorphism problems. A graph with no $M$-partition but such that every proper subgraph does have an $M$-partition is called a minimal obstruction. Feder, Hell, and Xie [Electron. Notes Discrete Math., 28 (2007), pp. 371--378] have defined friendly matrices and shown that nonfriendly matrices have infinitely many minimal obstructions. They showed through examples that friendly matrices can have finitely or infinitely many minimal obstructions and gave an example of a friendly matrix with an NP-complete partition problem. Here we show that almost all friendly matrices have infinitely many minimal obstructions and an NP-complete partition problem.