Problem 149

Erdős Problem #149: declared status 'open'. Formalized: no. Let $G$ be a graph with maximum degree $\Delta$. Is $G$ the union of at most $\tfrac{5}{4}\Delta^2$ sets of strongly independent edges (sets such that the induced subgraph is the union of vertex-disjoint edges)? Current best: This bound would be the best possible, as witnessed by a blowup of $C_5$. The best bound currently available is$$1.772\Delta^2,$$proved by Hurley, de Joannis de Verclos, and Kang [HJK22]. Mahdian has, in their Masters' thesis, proved an upper bound of $(2+o(1))\frac{\Delta^2}{\log \Delta}$ under the additional assumption that $G$ is $C_4$-free. Faron and Postle [FaPo19] proved $\omega\leq \frac{4}{3}\Delta^2$. Prize: no. Tags: graph theory.