Interval edge-colorings of complete graphs

An edge-coloring of a graph GG with colors 1,2,…,t1,2,…,t is an interval  tt-coloring   if all colors are used, and the colors of edges incident to each vertex of GG are distinct and form an interval of integers. A graph GG is interval colorable   if it has an interval tt-coloring for some positive integer tt. For an interval colorable graph GG, W(G)W(G) denotes the greatest value of tt for which GG has an interval tt-coloring. It is known that the complete graph is interval colorable if and only if the number of its vertices is even. However, the exact value of W(K2n)W(K2n) is known only for n≤4n≤4. The second author showed that if n=p2qn=p2q, where pp is odd and qq is nonnegative, then W(K2n)≥4n−2−p−qW(K2n)≥4n−2−p−q. Later, he conjectured that if n∈Nn∈N, then W(K2n)=4n−2−⌊log2n⌋−‖n2‖W(K2n)=4n−2−⌊log2n⌋−‖n2‖, where ‖n2‖‖n2‖ is the number of 1’s in the binary representation of nn.In this paper we introduce a new technique to construct interval colorings of complete graphs based on their 1-factorizations, which is used to disprove the conjecture, improve lower and upper bounds on W(K2n)W(K2n) and determine its exact values for n≤12n≤12.