Reduction conjecture for interval colorings of complete tripartite graphs

Let Kk,m,nK_{k,m,n} be the complete tripartite graph with part sizes k,m,nk,m,n, where kmnk\leq m\leq n and n>k+mn>k+m. Reduction conjecture.

Kk,m,n is interval colorableKk,m,nkm is interval colorable.K_{k,m,n}\text{ is interval colorable}\quad\Longleftrightarrow\quad K_{k,m,n-k-m}\text{ is interval colorable}.

This is proposed as a generalization of the K1,m,nK_{1,m,n} colorability problem; the source gives no resolution of the reduction in this range.

Sources & referencesView supporting material

Primary source

Andrzej Grzesik and Hrant Khachatrian, “Interval edge-colorings of K_1,m,n”, arXiv:1308.4431 (2013).

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.