Equitable colorings of Kronecker products of graphs |
| |
Authors: | Wu-Hsiung Lin |
| |
Institution: | a Department of Mathematics, National Taiwan University, Taipei 10617, Taiwanb Taida Institute for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwanc National Center for Theoretical Sciences, Taipei Office, Taiwan |
| |
Abstract: | For a positive integer k, a graph G is equitably k-colorable if there is a mapping f:V(G)→{1,2,…,k} such that f(x)≠f(y) whenever 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 , is the minimum t such that G is equitably k-colorable for k≥t. The current paper studies equitable chromatic numbers of Kronecker products of graphs. In particular, we give exact values or upper bounds on χ=(G×H) and when G and H are complete graphs, bipartite graphs, paths or cycles. |
| |
Keywords: | Equitable coloring Equitable chromatic number Equitable chromatic threshold Kronecker product |
本文献已被 ScienceDirect 等数据库收录! |
|