The decomposition conjecture for class II graphs

Let GG be a graph with maximum degree Δ\Delta and edge-chromatic number χ(G)=Δ+k\chi'(G)=\Delta+k, and let p,qp,q be positive integers satisfying

p+q=Δ+kp+q=\Delta+k

with p,qΔp,q\leq\Delta. A graph is class I if its edge-chromatic number equals its maximum degree. Decomposition conjecture. The graph GG can be decomposed into two class I subgraphs H1H_1 and H2H_2 such that

Δ(H1)=p,Δ(H2)=q.\Delta(H_1)=p,\qquad \Delta(H_2)=q.

This would generalize the preceding theorem, which gives a decomposition with maximum degrees Δ\Delta and kk; the proposed statement allows any two positive maximum degrees at most Δ\Delta whose sum is Δ+k\Delta+k.

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

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.