Interval edge-colorings of complete graphs and \(n\)-dimensional cubes (Q968437)

The graphs considered in this paper are finite, undirected, and have neither loops nor multiple edges. The authors consider a special type of edge-colourings, named interval \(t\)-colourings: An edge-colouring of a graph \(G\) with colours \(1,2,\dots,t\) is called an interval \(t\)-colouring if for each \(i\in\{1,2,\dots,t\}\) there is at least one edge of \(G\) coloured by \(i\), and the colours of the edges incident to any vertex of \(G\) are distinct and form an interval of integers. They show that the complete graph \(K_n\) has an interval \(t\)-colouring if \(n= p\cdot 2^q\), where \(p\) is odd, \(q\geq 0\) and \(2n- 1\leq t\leq 4n- 2- p- q\). Moreover the authors show that if \(n\leq t\leq n(n+1)/2\), then the \(n\)-dimensional cube \(Q_n\) has an interval \(t\)-colouring.