Some bounds on the number of colors in interval edge-colorings of graphs

P. A. Petrosyan ; L. N. Muradyan

Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 58 (2024) no. 2, pp. 57-65.

Résumé

An edge-coloring of a graph $G$ with colors $1,\ldots,t$ is called an interval $t$-coloring, if all colors are used and the colors of edges incident to each vertex of $G$ are distinct and form an interval of integers. A vertex $v$ of a graph $G=(V,E)$ is called a dominating vertex if $d_{G}(v)=|V|-1$, where $d_{G}(v)$ is the degree of $v$ in $G$. In this paper we prove, that if $G$ is a graph with the dominating vertex $u$ and it has an interval $t$-coloring, then $t\leq |V|+2\Delta(G-u)-1$, where $\Delta(G)$ is the maximum degree of $G$. We also show, that if a $k$-connected graph $G=(V,E)$ admits an interval $t$-coloring, then $t\leq 1+\left(\left\lfloor \dfrac{|V|-2}{k}\right\rfloor+2\right)(\Delta(G)-1)$. Moreover, if $G$ is also bipartite, then this upper bound can be improved to $t\leq 1+\left(\left\lfloor \dfrac{|V|-2}{k}\right\rfloor+1\right)(\Delta(G)-1)$. Finally, we discuss the sharpness of the obtained upper bounds on the number of colors in interval edge-colorings of these graphs.

Détail

Keywords: edge-coloring, interval edge-coloring, $k$-connected graph, dominating vertex
Mots-clés : bipartite graph

Bibliographie

[1] D. B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 2001 https://dwest.web.illinois.edu/igt/

[2] A. S. Asratian, R. R. Kamalian, “Interval Colorings of Edges of a Multigraph”, Appl. Math., 5, Yerevan State University, 1987, 25–34, arXiv: (in Russian) 1401.8079 | MR

[3] A. S. Asratian, R. R. Kamalian, “Investigation of Interval Edge-Colorings of Graphs”, Journal of Combinatorial Theory. Series B, 62:1 (1994), 34–43 | DOI | MR | Zbl

[4] P. A. Petrosyan, “Interval Edge-Colorings of Complete Graphs and $n$-Dimensional Cubes”, Discrete Math., 310 (2010), 1580–1587 | DOI | MR | Zbl

[5] P. A. Petrosyan, H. H. Khachatrian, H. G. Tananyan, “Interval Edge-Colorings of Cartesian Products of Graphs I”, Discuss. Math. Graph Theory, 33 (2013), 613–632 | DOI | MR | Zbl

[6] K. Giaro, “The Complexity of Consecutive $\Delta$-Coloring of Bipartite Graphs: $4$ is Easy, $5$ is Hard”, Ars Combin., 47 (1997), 287–298 | MR

[7] S. V. Sevastjanov, “Interval Colorability of the Edges of a Bipartite Graph”, Metodi Diskret. Analiza, 50 (1990), 61–72 (in Russian)

[8] P. A. Petrosyan, H. H. Khachatrian, “Interval non-edge-colorable bipartite graphs and multigraphs”, J. of Graph Theory, 76 (2014), 200–216 | DOI | MR | Zbl

[9] K. Giaro, M. Kubale, M. Malafiejski, “Consecutive Colorings of the Edges of General Graphs”, Discrete Math., 236 (2001), 131–143 | DOI | MR | Zbl

[10] R. R. Kamalian, Interval Edge Colorings of Graphs, Doctoral Thesis, Novosibirsk, 1990

[11] M. A. Axenovich, “On Interval Colorings of Planar Graphs”, Congr. Numer., 59 (2002), 77–94

[12] M. Axenovich, A. Girao, et al., “A Note on Interval Colourings of Graphs”, European Journal of Combinatorics, 120 (2024), 103956 | DOI

[13] A. Hambardzumyan, L. Muradyan, “Upper Bounds on the Number of Colors in Interval Edge-Colorings of Graphs”, Discrete Math., 348 (2025), 114229 | DOI

[14] R. R. Kamalian, P. A. Petrosyan, “A Note on Upper Bounds for the Maximum Span in Interval Edge-Colorings of Graphs”, Discrete Math., 312 (2012), 1393–1399 | DOI

[15] C. J. Casselgren, H. H. Khachatrian, P. A. Petrosyan, “Some Bounds on the Number of Colors in Interval and Cyclic Interval Edge Colorings of Graphs”, Discrete Math., 341 (2018), 627–637 | DOI | MR | Zbl

[16] L. Muradyan, “On Interval Edge-Colorings of Complete Multipartite Graphs”, Proc. YSU. Phis. Math. Sci., 56:1 (2022), 19–26 | DOI