A note on interval colourings of graphs

arXiv2303.04782MaRDI QIDQ6428874FDOQ6428874

Authors: Maria Axenovich, António Girão, Lawrence Hollom, Julien Portier, Emil Powierski, Youri Tamitegama, Leo Versteegen 

Publication date: 8 March 2023

Abstract: A graph is said to be interval colourable if it admits a proper edge-colouring using palette $mathbbN$ in which the set of colours incident to each vertex is an interval. The interval colouring thickness of a graph $G$ is the minimum $k$ such that $G$ can be edge-decomposed into $k$ interval colourable graphs. We show that $heta(n)$, the maximum interval colouring thickness of an $n$-vertex graph, satisfies $heta(n)=Omega(log(n)/loglog(n))$ and $heta(n)leq{n}^{5/6+o(1)}$, which improves on the trivial lower bound and an upper bound of the first author and Zheng. As a corollary, we answer a question of Asratian, Casselgren, and Petrosyan and disprove a conjecture of Borowiecka-Olszewska, Drgas-Burchardt, Javier-Nol, and Zuazua. We also confirm a conjecture of the first author that any interval colouring of an $n$-vertex planar graph uses at most $3n/2-2$ colours.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: A note on interval colourings of graphs

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