Reduction conjecture for interval colorings of complete tripartite graphs

About 13 years old · traced to

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

Kk,m,n is interval colorable⟺Kk,m,n−k−m 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.

References

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.