The maximum matching conjecture for maximum edge-colorable subgraphs
Let be an -regular graph with maximum degree and edge-chromatic number . A maximum -colorable subgraph is a subgraph with as many edges as possible whose edge-chromatic number is at most , and let be a maximum matching of . Maximum matching conjecture. There is a maximum -colorable subgraph of such that
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
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.