On the Independent Coloring of Graphs with Applications to the Independence Number of Cartesian Product Graphs - Nopparat Pleanmani; Sayan Panma; Nuttawoot Nupo (Journal of Mathematics)
Let G be a graph with V=VG. A nonempty subset S of V is called an independent set of G if no two distinct vertices in S are adjacent. The union of a class {S:S is an independent set of G} and ∅ is denoted by IG. For a graph H, a function f:V⟶IH is called an H−independent coloring of G (or simply called an H− coloring) if fx∩fy=∅ for any adjacent vertices x,y∈V and fV is a class of disjoint sets. Let αH,G denote the maximum cardinality of the set{∑x∈Vfx:f is an H− coloring of G}. In this paper, we obtain basic properties of an H− coloring of G and find αH,G of some families of graphs G and H. Furthermore, we apply them to determine the independence number of the Cartesian product of a complete graph Kn and a graph G and prove that αKn□G=αKn,G.