Opuscula Math. 26, no. 1 (2006), 31-44

Opuscula Mathematica

# Equitable coloring of graph products

Hanna Furmańczyk

Abstract. A graph is equitably $$k$$-colorable if its vertices can be partitioned into $$k$$ independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest $$k$$ for which such a coloring exists is known as the equitable chromatic number of $$G$$ and denoted by $$\chi_{=}(G)$$. It is interesting to note that if a graph $$G$$ is equitably $$k$$-colorable, it does not imply that it is equitably $$(k+1)$$-colorable. The smallest integer $$k$$ for which $$G$$ is equitably $$k'$$-colorable for all $$k'\geq k$$ is called the equitable chromatic threshold of $$G$$ and denoted by $$\chi_{=}^{*}(G)$$. In the paper we establish the equitable chromatic number and the equitable chromatic threshold for certain products of some highly-structured graphs. We extend the results from [Chen B.-L., Lih K.-W., Yan J.-H., Equitable coloring of graph products, manuscript, 1998] for Cartesian, weak and strong tensor products.

Keywords: equitable coloring, graph product.

Mathematics Subject Classification: 05C15, 68R10.

Full text (pdf)

• Hanna Furmańczyk
• Gdańsk University, Mathematical Institute, Wita Stwosza 57, 80-952 Gdańsk, Poland