Mkrtchyan–Steffen decomposition conjecture for multigraphs

Let GG be a graph with maximum degree 4Δ(G)=Δ4\Delta(G)=\Delta4 and chromatic index 4χ(G)=Δ+k4\chi'(G)=\Delta+k4,where, where k\geq 1.Amaximum. A **maximum 4\Delta4edgecolorablesubgraphisa4-edge-colorable subgraph** is a 4\Delta4edgecolorablesubgraphcontainingasmanyedgesaspossible,andadecompositionpartitionstheedgesof4-edge-colorable subgraph containing as many edges as possible, and a decomposition partitions the edges of Gintoedgedisjointsubgraphs.MkrtchyanSteffensconjecture.into edge-disjoint subgraphs. **Mkrtchyan–Steffen's conjecture.**Gcanbedecomposedintoamaximumcan be decomposed into a maximum4\Delta4edgecolorablesubgraph4-edge-colorable subgraph H_1andasubgraphand a subgraphH_2suchthatsuch that4\chi'(H_2)=k44. This generalizes their theorem for simple graphs to graphs with multiple edges; the source gives no resolution.

Sources & referencesView supporting material

Primary source

Yan Cao, Guangming Jing, Rong Luo, Vahan Mkrtchyan, Cun-Quan Zhang and Yue Zhao, “Decomposition of class II graphs into two class I graphs”, arXiv:2211.05930 (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.