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

An edge-coloring of a graph with colors is called an emph{interval lb -coloring}, if all colors are used and the colors of edges incident to each vertex of are distinct and form an interval of integers. A vertex of a graph is called a dominating vertex if , where is the degree of in . In this paper we prove, that if is a graph with the dominating vertex and it has an interval -coloring, then , where is the maximum degree of . We also show, that if a -connected graph admits an interval -coloring, then . Moreover, if is also bipartite, then this upper bound can be improved to . Finally, we discuss the sharpness of the obtained upper bounds on the number of colors in interval edge-colorings of these graphs.