Interval edge-colorings of complete graphs and n-dimensional cubes

摘要

An edge-coloring of a graph G with colors 1, 2, ... , t is called an interval t-coloring if for each i is an element of {1, 2, ... , t} there is at least one edge of G colored by i, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In this paper we show that if n = p2(q), where p is odd, q is nonnegative, and 2n - 1 <= t <= 4n - 2 - p - q, then the complete graph K-2n has an interval t-coloring. We also prove that if n <= t <= n(n+1)/2, then the n-dimensional cube Q(n) has an interval t-coloring.