Interval edge-colorings of complete graphs.

An edge-coloring of a graph G with colors 1 , 2 , … , t is an interval t -coloring if all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integers. A graph G is interval colorable if it has an interval t -coloring for some positive integer t . For an interval colorable graph G , W ( G ) denotes the greatest value of t for which G has an interval t -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 ( K 2 n ) is known only for n ≤ 4 . The second author showed that if n = p 2 q , where p is odd and q is nonnegative, then W ( K 2 n ) ≥ 4 n − 2 − p − q . Later, he conjectured that if n ∈ N , then W ( K 2 n ) = 4 n − 2 − ⌊ log 2 n ⌋ − ‖ n 2 ‖ , where ‖ n 2 ‖ is the number of 1’s in the binary representation of n . 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 ( K 2 n ) and determine its exact values for n ≤ 12 . [ABSTRACT FROM AUTHOR]