2013/10/08 by Wang, Wei, Yan, Zhidan, Zhang, Xin
#05C15 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1310.2188
A graph G is r-equitably k-colorable if its vertex set can be partitioned into k independent sets, any two of which differ in size by at most r. The r-equitable chromatic threshold of a graph G, denoted by χr=^*(G), is the minimum k such that G is r-equitably k'-colorable for all k'≥ k. Let G× H denote the Kronecker product of graphs G and H. In this paper, we completely determine the exact value of χr=^*(Km× Kn) for general m,n and r. As a consequence, we show that for r≥ 2, if n≥ (1)/(r-1)(m+r)(m+2r-1) then Km× Kn and its spanning supergraph Km(n) have the same r-equitable colorability, and in particular χr=^*(Km× Kn)=χr=^*(Km(n)), where Km(n) is the complete m-partite graph with n vertices in each part.