2015/08/18 by Nakprasit, Keaitsuda Maneeruk, Nakprasit, Kittikorn
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1508.04201
A q-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 equitable chromatic threshold is the minimum p such that G has an equitable q-coloring for every q≥ p. In this paper, we establish the notion of p(q: n1,…, nk) which can be computed in linear-time and prove the following. Assume that Kn1,…,nk has an equitable q-coloring. Then p(q: n1,…, nk) is the minimum p such that Kn1,…,nk has an equitable r-coloring for each r satisfying p ≤ r ≤ q. Since Kn1,…,nk has an equitable (n1+⋯+nk)-coloring, the equitable chromatic threshold of Kn1,…,nk is p(n1+⋯+nk: n1,…, nk). We find out later that the aforementioned immediate consequence is exactly the same as the formula of Yan and Wang \citeYW12. Nonetheless, the notion of p(q: n1,…, nk) can be used for each q in which Kn1,…,nk has an equitable q-coloring and the proof presented here is much shorter.