Introduction to Graph Theory · Problem 6.4

Colorings — Darij Grinberg

Mathematics — Graph Theory · cartesian-product-colorings

Problem

Let

k \in \mathbb{N}

. Let

G

and

H

be two simple graphs. Assume that each of

G

and

H

has a proper

k

-coloring. Prove that the Cartesian product

G \times H

(defined in Definition 2.14.11) has a proper

k

-coloring as well. [Remark: It is easy to see that the converse holds as well (i.e., if

G \times H

has a proper

k

-coloring, then so do

G

and

H

), provided that the vertex sets

V(G)

and

V(H)

are both nonempty.]