Mkrtchyan–Steffen decomposition conjecture for multigraphs

About 4 years old · traced to

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.A∗∗maximum. A **maximum 4\Delta4−edge−colorablesubgraph∗∗isa4-edge-colorable subgraph** is a 4\Delta4−edge−colorablesubgraphcontainingasmanyedgesaspossible,andadecompositionpartitionstheedgesof4-edge-colorable subgraph containing as many edges as possible, and a decomposition partitions the edges of Gintoedge−disjointsubgraphs.∗∗Mkrtchyan–Steffen′sconjecture.∗∗into edge-disjoint subgraphs. **Mkrtchyan–Steffen's conjecture.**Gcanbedecomposedintoamaximumcan be decomposed into a maximum4\Delta4−edge−colorablesubgraph4-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.

References

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.