2012/07/16 by Zhidan Yan, Wei Wang, Yan, Zhidan +1
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1207.3578
openalex publication_date 2012/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 χ_=(G), is the minimum k such that G is equitably k-colorable. The equitable chromatic threshold of a graph G, denoted by χ_=^*(G), is the minimum t such that G is equitably k-colorable for k≥ t. We develop a formula and a linear-time algorithm which compute the equitable chromatic threshold of an arbitrary complete multipartite graph.