Three-subgraph regular-irregular decomposition conjecture
Three-subgraph regular-irregular decomposition conjecture
A subgraph is called regular or locally irregular according as it is regular or locally irregular. The regular-irregular number is the minimum number of subgraphs into which the edges of a graph can be decomposed, with every subgraph regular or locally irregular. Three-subgraph regular-irregular conjecture. Every graph can be decomposed into subgraphs, such that each subgraph is locally irregular or regular.
This conjecture weakens the conjecture that every non-exception graph has irregular chromatic index at most and strengthens the conjecture that every graph has regular-irregular chromatic index at most . The supplied text does not report a resolution.
Sources & referencesView supporting material
Primary source
Arash Ahadi, Ali Dehghan, Mohammad-Reza Sadeghi and Brett Stevens, “On the algorithmic complexity of decomposing graphs into regular/irregular structures”, arXiv:1801.08876 (2018).
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.