The four locally irregular subgraphs conjecture

Let G=(V,E)G=(V,E) be a connected graph, and let T\mathfrak{T}' be the family of connected graphs that are not decomposable into any number of locally irregular subgraphs. A graph is decomposable into kk locally irregular subgraphs if its edge set can be partitioned as E=E1EkE=E_1\cup\cdots\cup E_k so that each spanning subgraph (V,Ei)(V,E_i) is locally irregular, meaning that adjacent vertices have distinct degrees.

Four-subgraph conjecture. Each connected graph GG which does not belong to T\mathfrak{T}' is decomposable to 44 locally irregular subgraphs.

This is the less restrictive variant proposed after a connected exception to the three-subgraph conjecture was found. The source does not state a resolution of this four-subgraph variant.

Sources & referencesView supporting material

Primary source

Jakub Przybyło, “Decomposability of regular graphs to 4 locally irregular subgraphs”, arXiv:2402.18739 (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.