ON INTERVAL EDGE-COLORINGS OF COMPLETE MULTIPARTITE GRAPHS

Author(s)

ON INTERVAL EDGE-COLORINGS OF COMPLETE MULTIPARTITE GRAPHS Levon Muradyan

A graph G is called a complete r-partite (r≥2) graph, if its vertices can be divided into r non-empty independent sets V1,…,Vr in a way that each vertex in Vi is adjacent to all the other vertices in Vj for 1≤i<j≤r. Let Kn1,n2,…,nr denote a complete r-partite graph with independent sets V1,V2,…,Vr of sizes n1,n2,…,nr. An edge-coloring of a graph G with colors 1,2,…,t is called an emph{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. In this paper we have obtained some results on the existence and construction of interval edge-colorings of complete r-partite graphs. Moreover, we have also derived an upper bound on the number of colors in interval colorings of complete multipartite graphs.

DOI: 10.46991/PYSU:A/2022.56.1.019 Physical and Mathematical Sciences, 56(1 (257) 19-26

Download PDF

Keywords

complete multipartite graph, edge-coloring, proper edge-coloring, interval coloring

Check for updates

Share

Contact admin with any questions, comments or concerns

[email protected]