Pith. sign in

REVIEW

A note on interval colourings of graphs

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2303.04782 v2 pith:BWJXC5KR submitted 2023-03-08 math.CO

A note on interval colourings of graphs

classification math.CO
keywords intervalgraphcolouringthetavertexauthorboundcolourable
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
read the original abstract

A graph is said to be interval colourable if it admits a proper edge-colouring using palette $\mathbb{N}$ 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 $\theta(n)$, the maximum interval colouring thickness of an $n$-vertex graph, satisfies $\theta(n) =\Omega(\log(n)/\log\log(n))$ and $\theta(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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.