Introduction to Graph Theory · Problem 6.6

Colorings — Darij Grinberg

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

Problem

Let nn and kk be two positive integers. Let KK be a set of size kk. Let DD be the de Bruijn digraph -- i.e., the multidigraph constructed in the proof of Theorem 5.16.2. Let GG be the result of removing all loops from the undirected graph DundD^{\mathrm{und}}. Prove that GG has a proper (k+1)(k+1)-coloring.
Intuitive explanation

The de Bruijn digraph encodes overlapping strings of length nn over a kk-letter alphabet, where each vertex represents a string of length n−1n-1 and edges represent extending those strings. When you convert to an undirected graph and remove loops, you're left with a graph where vertices can be naturally grouped by their "prefix structure"—the key insight is that the underlying string overlap structure is acyclic in a way that lets you assign colors based on the position or value of characters, using at most k+1k+1 colors to respect the alphabet size and the graph's inherent layering.

Intuitive explanation

The de Bruijn digraph encodes overlapping strings of length nn over a kk-letter alphabet, where each vertex represents a string of length n−1n-1 and edges represent extending those strings. When you convert to an undirected graph and remove loops, you're left with a graph where vertices can be naturally grouped by their "prefix structure"—the key insight is that the underlying string overlap structure is acyclic in a way that lets you assign colors based on the position or value of characters, using at most k+1k+1 colors to respect the alphabet size and the graph's inherent layering.

Browse the problem library