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

Author(s)

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

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.

DOI: 10.46991/PYSU:A.2024.58.2.057 Physical and Mathematical Sciences, 58(2 (264) 57-65

Download PDF

Keywords

edge-coloring, interval edge-coloring, k-connected graph, bipartite graph, dominating vertex

Check for updates

Share

Contact admin with any questions, comments or concerns

[email protected]