Chromatic number of Cartesian sum of two graphs
Kung-Wei Yang · Proceedings of the American Mathematical Society · 1968
In this note, we will consider the class of all finite undirected graphs with simple edges and no loops [l].Let G, Gi, G2 denote graphs.Let o(G) =the number of vertices in G, B(G) =the independence number of G, K(G) =the chromatic number of G, GiffiG2 = the Cartesian sum of Gi and G2 [l].We shall prove the following Theorem.o(Gi)o(G2)//3(Gi)j8(G2) ^K(Gi©G2) gK(Gi)K(G2).Moreover, an example is given to show that the inequality K(Gi©G2)<K(Gi)K(G2) in fact occurs.The proof is based on the following two lemmas.Lemma 1. /3(Gi©G2) = B(Gi)B(Gi).Proof.If G is a graph, we denote by ViG) the set of vertices of Gand by E(G) the set of edges of G.We say that a subset S C V(G) is independent if for any a, b in 5, (a, 6)$£(G).If 5 is a set, we denote