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 reg-irr(G)\operatorname{reg\text{-}irr}(G) is the minimum number of subgraphs into which the edges of a graph GG can be decomposed, with every subgraph regular or locally irregular. Three-subgraph regular-irregular conjecture. Every graph can be decomposed into 33 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 33 and strengthens the conjecture that every graph has regular-irregular chromatic index at most 22. 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

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.