The (2,2)-Conjecture for graph decompositions

About 2 years old · traced to

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

G1⊆M1⊆2G1,G_1\subseteq M_1\subseteq {}^2G_1, G2⊆M2⊆2G2.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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.