Equitable colorings of Cartesian products of graphs
Equitable colorings of Cartesian products of graphs
复制标题
DOI：
10.1016/j.dam.2011.09.020
复制
发表时间：
2012-02
期刊：
影响因子：
--
通讯作者：
Wu-Hsiung Lin;G. Chang
中科院分区：
文献类型：
--
作者：
Wu-Hsiung Lin;G. Chang
The present paper studies the following variation of vertex coloring on graphs. A graph G is equitably k-colorable if there is a mapping f:V(G)→{1,2,…,k} such that f(x)≠f(y) for xy∈E(G) and ∣∣f−1(i)∣−∣f−1(j)∣∣≤1 for 1≤i,j≤k. 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 all k≥t. Our focus is on the equitable colorability of Cartesian products of graphs. In particular, we give exact values or upper bounds of χ=(G□H) and χ=∗(G□H) when G and H are cycles, paths, stars, or complete bipartite graphs.
