Equitable colorings of complete multipartite graphs

Abstract

A $q$-\emph{equitable coloring} of a graph $G$ is a proper $q$-coloring such that the sizes of any two color classes differ by at most one. In contrast with ordinary coloring, a graph may have an equitable $q$-coloring but has no equitable $(q+1)$-coloring. The \emph{equitable chromatic threshold} is the minimum $p$ such that $G$ has an equitable $q$-coloring for every $q\ge p.$ In this paper, we establish the notion of $p(q:n_1,\dots ,n_k)$ which can be computed in linear-time and prove the following. Assume that $K_{n_1,\dots ,n_k}$ has an equitable $q$-coloring. Then $p(q:n_1,\dots ,n_k)$ is the minimum $p$ such that $K_{n_1,\dots ,n_k}$ has an equitable $r$-coloring for each $r$ satisfying $p\le r\le q.$ Since $K_{n_1,\dots ,n_k}$ has an equitable $(n_1+\cdots +n_k)$-coloring, the equitable chromatic threshold of $K_{n_1,\dots ,n_k}$ is $p(n_1+\cdots +n_k:n_1,\dots ,n_k).$ We find out later that the aforementioned immediate consequence is exactly the same as the formula of Yan and Wang \cite{YW12}. Nonetheless, the notion of $p(q:n_1,\dots ,n_k)$ can be used for each $q$ in which $K_{n_1,\dots ,n_k}$ has an equitable $q$-coloring and the proof presented here is much shorter.

arXiv admin note: text overlap with arXiv:1506.03913

References in corpus (1)

• Equitable chromatic threshold of complete multipartite graphs