Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418664 | Discrete Applied Mathematics | 2015 | 4 Pages |
Abstract
A proper vertex coloring of a graph is equitable if the sizes of any two color classes differ by at most one. The equitable chromatic number of a graph GG, denoted by χ=(G)χ=(G), is the minimum kk such that GG is equitably kk-colorable. Lin and Chang conjectured that for any (nontrivial) connected graphs GG and HH, χ=(G□H)≤χ(G)χ(H)χ=(G□H)≤χ(G)χ(H), where □□ denotes the Cartesian product. In this paper, we prove the conjecture when GG or HH is a balanced complete multipartite graph. More precisely, we show a stronger result that for any graph HH with χ(H)≥2χ(H)≥2, χ=(Kr(n)□H)≤r⌈χ(H)−1r−1⌉, where r≥2r≥2, n≥1n≥1 and Kr(n)Kr(n) denotes the balanced complete rr-partite graph with part size nn.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Zhidan Yan, Wei Wang, Xin Zhang,