×

A note on interval colourings of graphs. (English) Zbl 07878009

Summary: 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 of edges that are 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) = \varOmega (\log (n)/\log \log (n))\) and \(\theta (n) \leqslant n^{5/6+o(1)}\), which improves on the trivial lower bound and the upper bound given by M. Axenovich and M. Zheng [J. Graph Theory 104, No. 4, 757–768 (2023; Zbl 1541.05053)]. As a corollary, we answer a question of A. S. Asratian et al. [Discrete Appl. Math. 335, 25–35 (2023; Zbl 1514.05127)] and disprove a conjecture of M. Borowiecka-Olszewska et al. [Result. Math. 76, No. 4, Paper No. 200, 21 p. (2021; Zbl 1477.05073)]. 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.

MSC:

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory

References:

[1] Asratian, A. S.; Casselgren, C. J.; Petrosyan, P. A., Decomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules, Discrete Appl. Math., 335, 25-35, 2023 · Zbl 1514.05127
[2] Asratian, A. S.; Kamalian, R. R., Interval colorings of edges of a multigraph (in Russian), Applied Mathematics 5, Yerevan State University, 25-34, 1987, For an English translation see arXiv:1401.8079 · Zbl 0742.05038
[3] Asratian, A. S.; Kamalian, R. R., Investigation on interval edge-colorings of graphs, J. Combin. Theory Ser. B, 62, 1, 34-43, 1994 · Zbl 0805.05024
[4] Axenovich, M., On interval colorings of planar graphs, Congr. Numer., 159, 77-94, 2002 · Zbl 1026.05036
[5] Axenovich, M.; Girão, A.; Powierski, E.; Savery, M.; Tamitegama, Y., A note on the interval colouring thickness of graphs, 2023, arXiv:2303.04782v1 preprint
[6] Axenovich, M.; Zheng, M., Interval colorings of graphs—Coordinated and unstable no-wait schedules, J. Graph Theory, 104, 4, 757-768, 2023 · Zbl 1541.05053
[7] B. Bollobás, 2023. Personal communication.
[8] Borowiecka-Olszewska, M.; Drgas-Burchardt, E.; Javier-Nol, N. Y.; Zuazua, R., Consecutive colouring of oriented graphs, Results Math., 76, 200, 2021 · Zbl 1477.05073
[9] Dean, A. M.; Hutchinson, J. P.; Scheinerman, E. R., On the thickness and arboricity of a graph, J. Combin. Theory Ser. B, 52, 1, 147-151, 1991 · Zbl 0675.05042
[10] Giaro, K.; Kubale, M.; Małafiejski, M., Consecutive colorings of the edges of general graphs, Discrete Math., 236, 131-143, 2001 · Zbl 1007.05045
[11] Hambardzumyan, A.; Muradyan, L., On interval edge-colorings of planar graphs, 2023, arXiv:2303.11466 preprint
[12] Hansen, H. M., Scheduling with Minimum Waiting Periods (in Danish), 1992, Odense University: Odense University Odense, Denmark, (Master’s thesis)
[13] Hollom, L.; Portier, J.; Versteegen, L., On interval colourings of graphs, 2023, arXiv:2303.05505v1 preprint
[14] Janson, S.; Luczak, T.; Rucinski, A., Random Graphs, 2011, John Wiley & Sons
[15] Jensen, T. R.; Toft, B., Graph Coloring Problems, 1995, John Wiley & Sons · Zbl 0855.05054
[16] Rödl, V.; Wysocka, B., Note on regular subgraphs, J. Graph Theory, 24, 2, 139-154, 1997 · Zbl 0873.05057
[17] Sevastianov, S. V., Interval colorability of the edges of a bipartite graph (in Russian), Metody Diskretnogo Anal., 50, 61-72, 1990, For an English translation see https://www.math.kit.edu/iag6/axenovich/seite/publications/media/sevastianov-translation.pdf · Zbl 0769.05040
[18] Stiebitz, M.; Scheide, D.; Toft, B.; Favrholdt, L. M., Graph Edge Coloring: Vizing’s Theorem and Goldberg’s Conjecture, 2012, John Wiley & Sons · Zbl 1339.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.