The maximum matching conjecture for maximum edge-colorable subgraphs

From papers

Let GG be an rr-regular graph with maximum degree Δ\Delta and edge-chromatic number χ(G)=Δ+1\chi'(G)=\Delta+1. A maximum Δ\Delta-colorable subgraph is a subgraph with as many edges as possible whose edge-chromatic number is at most Δ\Delta, and let MM be a maximum matching of GG. Maximum matching conjecture. There is a maximum Δ\Delta-colorable subgraph HH of GG such that

ME(H)=E(G).M\cup E(H)=E(G).

This is proposed as a generalization of a theorem of Mkrtchyan and Steffen for bridgeless cubic graphs and perfect matchings. The conjecture asks whether the matching-completion property persists for regular class II graphs.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

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).

Solutions 0

No solutions have been posted yet.