SOME BOUNDS ON THE NUMBER OF COLORS IN INTERVAL EDGE-COLORINGS OF GRAPHS

Abstract

An edge-coloring of a graph $G$ with colors $1,\ldots,t$ is called an \emph{interval \lb $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.