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