Decomposition of class II graphs into two class I graphs
| Autor: | Cao, Yan, Jing, Guangming, Luo, Rong, Mkrtchyan, Vahan, Zhang, Cun-Quan, Zhao, Yue |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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\geq 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. Comment: 9 pages, no figures |
| Databáze: | arXiv |
| Externí odkaz: |
|