Decomposability of graphs into subgraphs fulfilling the 1-2-3 Conjecture

Abstract

The well-known 1-2-3 Conjecture asserts that the edges of every graph without isolated edges can be weighted with $1$, $2$ and $3$ so that adjacent vertices receive distinct weighted degrees. This is open in general. We prove that every $d$-regular graph, $d\ge 2$, can be decomposed into at most $2$ subgraphs (without isolated edges) fulfilling the 1-2-3 Conjecture if $d\notin \{10,11,12,13,15,17\}$, and into at most $3$ such subgraphs in the remaining cases. Additionally, we prove that in general every graph without isolated edges can be decomposed into at most $24$ subgraphs fulfilling the 1-2-3 Conjecture, improving the previously best upper bound of $40$. Both results are partly based on applications of the Lovász Local Lemma.

13 pages