Equitable chromatic threshold of complete multipartite graphs

Abstract

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most one. The equitable chromatic number of a graph $G$, denoted by ${\chi }_{=}(G)$, is the minimum $k$ such that $G$ is equitably $k$-colorable. The equitable chromatic threshold of a graph $G$, denoted by ${\chi }_{=}^{\ast }(G)$, is the minimum $t$ such that $G$ is equitably $k$-colorable for $k\ge t$. We develop a formula and a linear-time algorithm which compute the equitable chromatic threshold of an arbitrary complete multipartite graph.

10 pages

Cited by in corpus (1)

• Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs