On interval colourings of graphs
| Autor: | Hollom, Lawrence, Portier, Julien, Versteegen, Leo |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | An interval colouring of a graph $G=(V,E)$ is a proper colouring $c\colon 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} \leq \theta(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$. Comment: 11 pages, this work has been superseded and incorporated into arXiv:2303.04782 |
| Databáze: | arXiv |
| Externí odkaz: |
|