## Abstract

The present paper studies the following variation of vertex coloring on graphs. A graph G is equitably k-colorable if there is a mapping fV(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.

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

Pages (from-to) | 239-247 |

Number of pages | 9 |

Journal | Discrete Applied Mathematics |

Volume | 160 |

Issue number | 3 |

DOIs | |

State | Published - 1 Feb 2012 |

## Keywords

- Cartesian product
- Equitable chromatic number
- Equitable chromatic threshold
- Equitable coloring