Abstract

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.

‹ 1 / ? › − 100% + Open in new tab Download Cite

Loading the full text…