Abstract

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.

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

Loading the full text…