A note on interval colourings of graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911983234711552 |
|---|---|
| author | Axenovich, Maria Girão, António Hollom, Lawrence Portier, Julien Powierski, Emil Savery, Michael Tamitegama, Youri Versteegen, Leo |
| author_facet | Axenovich, Maria Girão, António Hollom, Lawrence Portier, Julien Powierski, Emil Savery, Michael Tamitegama, Youri Versteegen, Leo |
| contents | 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 $θ(n)$, the maximum interval colouring thickness of an $n$-vertex graph, satisfies $θ(n) =Ω(\log(n)/\log\log(n))$ and $θ(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_04782 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A note on interval colourings of graphs Axenovich, Maria Girão, António Hollom, Lawrence Portier, Julien Powierski, Emil Savery, Michael Tamitegama, Youri Versteegen, Leo Combinatorics 05C15, 05C35, 05C10 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 $θ(n)$, the maximum interval colouring thickness of an $n$-vertex graph, satisfies $θ(n) =Ω(\log(n)/\log\log(n))$ and $θ(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. |
| title | A note on interval colourings of graphs |
| topic | Combinatorics 05C15, 05C35, 05C10 |
| url | https://arxiv.org/abs/2303.04782 |