EQUITABLE COLORINGS OF CARTESIAN PRODUCTS OF SQUARE OF PATHS AND CYCLES WITH SQUARE OF PATHS AND CYCLES

EQUITABLE COLORINGS OF CARTESIAN PRODUCTS OF SQUARE OF PATHS AND CYCLES WITH SQUARE OF PATHS AND CYCLES

P. Elumalai, A. Parthiban

[PDF]

Abstract

Let [p] = {1, 2, 3, . . . , p} and G be an undirected simple graph. Graph coloring is a special case of labeling, and G is said to admit a proper coloring if no two neighbouring vertices of it are given an identical color. The vertices of an identical color constitute a color class. G is p - colorable if it admits proper p - coloring. The chromatic number, χ(G) = min {p : G is proper p - colorable} and G is equitably p - colorable if it admits proper p - coloring and the absolute difference in size between any distinct pairwise color class is at most 1. The equitable chromatic number, χ=(G) = min {p : G is equitably p - colorable}. The equitable chromatic threshold, χ∗ =(G) = min {p′ : G is equitably p - colorable ∀ p ≥ p′}. In this paper, we obtain exact values or bounds of χ∗ =(G1□G2) and χ=(G1□G2), where G1 = P2m or C2m and G2 = P2 n or C2n .

Keywords

Square of a path and cycle graph, Cartesian product, Equitable coloring, Equitable chromatic number, Equitable chromatic threshold.