### 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 χ=*(G), 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 χ=*(G×H) when G and H are complete graphs, bipartite graphs, paths or cycles.

Original language | English |
---|---|

Pages (from-to) | 1816-1826 |

Number of pages | 11 |

Journal | Discrete Applied Mathematics |

Volume | 158 |

Issue number | 16 |

DOIs | |

State | Published - 28 Aug 2010 |

### Keywords

- Equitable chromatic number
- Equitable chromatic threshold
- Equitable coloring
- Kronecker product

## Fingerprint Dive into the research topics of 'Equitable colorings of Kronecker products of graphs'. Together they form a unique fingerprint.

## Cite this

Lin, W-H., & Chang, G. J. (2010). Equitable colorings of Kronecker products of graphs.

*Discrete Applied Mathematics*,*158*(16), 1816-1826. https://doi.org/10.1016/j.dam.2010.06.011