The bow-tie exception conjecture for locally irregular decompositions

Let T\mathfrak{T'} be the family consisting of the recursively defined family T\mathfrak{T}, all odd-length paths and all odd-length cycles, and let BB denote the bow-tie graph. For a graph GG, let lir(G){\rm lir}(G) be the least number of locally irregular graphs into which GG can be decomposed. Bow-tie exception conjecture. Every connected graph GTG\notin\mathfrak{T'}, except for the bow-tie graph BB, satisfies

lir(G)3.{\rm lir}(G)\leq 3.

The bow-tie graph is known not to admit a decomposition into three locally irregular graphs, while the conjecture has been proved for trees, cacti, sufficiently high minimum degree, and sufficiently large regular degree. It remains open for general connected graphs.

Sources & referencesView supporting material

Primary source

Igor Grzelec and Mariusz Woźniak, “On decomposing multigraphs into locally irregular submultigraphs”, arXiv:2208.08809 (2022).

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.