ON INTERVAL EDGE-COLORINGS OF COMPLETE MULTIPARTITE GRAPHS
DOI:
https://doi.org/10.46991/PYSU:A/2022.56.1.019Keywords:
complete multipartite graph, edge-coloring, proper edge-coloring, interval coloringAbstract
A graph $G$ is called a complete $r$-partite $(r\geq 2)$ graph, if its vertices can be divided into $r$ non-empty independent sets $V_1,\ldots,V_r$ in a way that each vertex in $V_i$ is adjacent to all the other vertices in $V_j$ for $1\leq i<j\leq r$. Let $K_{n_{1},n_{2},\ldots,n_{r}}$ denote a complete $r$-partite graph with independent sets $V_1,V_2,\ldots,V_r$ of sizes $n_{1},n_{2},\ldots,n_{r}$. An edge-coloring of a graph $G$ with colors $1,2,\ldots,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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Proceedings of the YSU
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.