On interval colourings of graphs

arXiv2303.05505MaRDI QIDQ6429014FDOQ6429014

Authors: Lawrence Hollom, Julien Portier, Leo Versteegen 

Publication date: 9 March 2023

Abstract: An interval colouring of a graph $G=(V,E)$ is a proper colouring $ccolonEomathbbZ$ such that the set of colours of edges incident to any given vertex forms an interval of $mathbbZ$. The interval thickness $heta(G)$ of a graph $G$ is the smallest integer $k$ such that $G$ can be edge-partitioned into $k$ interval colourable graphs, and $heta(n)$ is the largest interval thickness over graphs on $n$ vertices. We show that $cfraclognloglognleqheta(n)leq{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$.

This page was built for publication: On interval colourings of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6429014)