Decomposition of class II graphs into two class I graphs

Abstract

Mkrtchyan and Steffen [J. Graph Theory, 70 (4), 473--482, 2012] showed that every class II simple graph can be decomposed into a maximum $\Delta$-edge-colorable subgraph and a matching. They further conjectured that every graph $G$ with chromatic index $\Delta (G)+k$ ($k\ge 1$) can be decomposed into a maximum $\Delta (G)$-edge-colorable subgraph (not necessarily class I) and a $k$-edge-colorable subgraph. In this paper, we first generalize their result to multigraphs and show that every multigraph $G$ with multiplicity $\mu$ can be decomposed into a maximum $\Delta (G)$-edge-colorable subgraph and a subgraph with maximum degree at most $\mu$. Then we prove that every graph $G$ with chromatic index $\Delta (G)+k$ can be decomposed into two class I subgraphs $H_1$ and $H_2$ such that $\Delta (H_1)=\Delta (G)$ and $\Delta (H_2)=k$, which is a variation of their conjecture.

9 pages, no figures