The maximum matching conjecture for maximum edge-colorable subgraphs
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.
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
Sign in to submit a solution.
No solutions have been posted yet.