The maximum matching conjecture for maximum edge-colorable subgraphs

About 4 years old · traced to

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

M∪E(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.

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.