The (2,2)-Conjecture for graph decompositions

From papers

Let GG be a connected graph of order at least four. A locally irregular multigraph is a multigraph in which the endpoints of every edge have different degrees. For a subgraph HH of GG, let 2H{}^2H denote the multigraph obtained by replacing each edge of HH by two parallel edges.

(2,2)-Conjecture. The graph GG can be decomposed into two subgraphs G1G_1 and G2G_2 such that there exist locally irregular multigraphs M1M_1 and M2M_2 satisfying

G1M12G1,G_1\subseteq M_1\subseteq {}^2G_1, G2M22G2.G_2\subseteq M_2\subseteq {}^2G_2.

Equivalently, every connected graph of order at least four should have a (2,2)(2,2)-coloring. This formulation connects locally irregular decompositions with neighbor-sum-distinguishing edge colorings; the source presents it as an open conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Igor Grzelec, Tomáš Madaras, Alfréd Onderko and Roman Soták, “On a new problem about the local irregularity of graphs”, arXiv:2405.13893 (2024).

Solutions 0

No solutions have been posted yet.