The bow-tie exception conjecture for locally irregular decompositions
The bow-tie exception conjecture for locally irregular decompositions
Let be the family consisting of the recursively defined family , all odd-length paths and all odd-length cycles, and let denote the bow-tie graph. For a graph , let be the least number of locally irregular graphs into which can be decomposed. Bow-tie exception conjecture. Every connected graph , except for the bow-tie graph , satisfies
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.