2023/03/09 by Hollom, Lawrence, Portier, Julien, Versteegen, Leo
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2303.05505
An interval colouring of a graph G=(V,E) is a proper colouring c\colon E→ ℤ such that the set of colours of edges incident to any given vertex forms an interval of ℤ. The interval thickness θ(G) of a graph G is the smallest integer k such that G can be edge-partitioned into k interval colourable graphs, and θ(n) is the largest interval thickness over graphs on n vertices. We show that c (log n)/(log log n) ≤ θ(n) ≤ n8/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.