Petrosyan's binary-weight conjecture for interval colorings of complete graphs

Let K2nK_{2n} be the complete graph on 2n2n vertices, and let W(K2n)W(K_{2n}) be the greatest number of colors in an interval coloring of K2nK_{2n}. Write n2\left\|n_2\right\| for the number of 11's in the binary representation of nn. Petrosyan's binary-weight conjecture.

W(K2n)=4n2log2nn2.W(K_{2n})=4n-2-\left\lfloor\log_2 n\right\rfloor-\left\|n_2\right\|.

This conjecture was proposed after the earlier exact-value conjecture was disproved. The supplied text gives no resolution of this binary-weight formula, so its status remains open.

Sources & referencesView supporting material

Primary source

Hrant H. Khachatrian and Petros A. Petrosyan, “Interval edge-colorings of complete graphs”, arXiv:1411.5661 (2016).

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.