On interval colourings of graphs

Abstract

An interval colouring of a graph $G=(V,E)$ is a proper colouring $c:E\to \mathbb{Z}$ such that the set of colours of edges incident to any given vertex forms an interval of $\mathbb{Z}$. The interval thickness $\theta (G)$ of a graph $G$ is the smallest integer $k$ such that $G$ can be edge-partitioned into $k$ interval colourable graphs, and $\theta (n)$ is the largest interval thickness over graphs on $n$ vertices. We show that $c\frac{\log n}{\log \log n}\le \theta (n)\le n^{8/9+o(1)}$ for some $c>0$. In particular this answers a question by Asratian, Casselgren, and Petrosyan. In the second part of the paper, we confirm a conjecture of Axenovich that the maximum number of colours used in an interval colouring of a planar graph on $n$ vertices is at most $3n/2-2$.

11 pages, this work has been superseded and incorporated into arXiv:2303.04782