Interval colorings of complete balanced multipartite graphs

Abstract

A graph $G$ is called a complete $k$-partite ($k\ge 2$) graph if its vertices can be partitioned into $k$ independent sets $V_1,...,V_k$ such that each vertex in $V_i$ is adjacent to all the other vertices in $V_j$ for $1\le i<j\le k$. A complete $k$-partite graph $G$ is a complete balanced $k$-partite graph if $|V_1|=|V_2|=...=|V_k|$. An edge-coloring of a graph $G$ with colors $1,...,t$ is an 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. A graph $G$ is interval colorable if $G$ has an interval $t$-coloring for some positive integer $t$. In this paper we show that a complete balanced $k$-partite graph $G$ with $n$ vertices in each part is interval colorable if and only if $nk$ is even. We also prove that if $nk$ is even and $(k-1)n\le t\le ((3/2)k-1)n-1$, then a complete balanced $k$-partite graph $G$ admits an interval $t$-coloring. Moreover, if $k=p{2}^q$, where $p$ is odd and $q\in \mathbb{N}$, then a complete balanced $k$-partite graph $G$ has an interval $t$-coloring for each positive integer $t$ satisfying $(k-1)n\le t\le (2k-p-q)n-1$.

10 pages

Cited by in corpus (1)

• On the deficiency of complete multipartite graphs