Grinberg-Introduction-Graph-Theory · Problem 6.6

Colorings

Mathematics — Graph Theory · de-bruijn-graph-colorings

Problem

Let

n

and

k

be two positive integers. Let

K

be a set of size

k

. Let

D

be the de Bruijn digraph -- i.e., the multidigraph constructed in the proof of Theorem 5.16.2. Let

G

be the result of removing all loops from the undirected graph

D^{\mathrm{und}}

. Prove that

G

has a proper

(k+1)

-coloring.