Coloring problems

Catalogue of combinatorial problems · Catalogue (PDF)

• Given an undirected graph \(G=(V,E)\), a solution assigns a color to every vertex so that adjacent vertices receive different colors.

• Equivalently, a solution is a partition of \(V\) into stable sets; the minimum number of colors is the chromatic number \(\chi(G)\).

Problem	Acronym	Difference
Vertex coloring problem	VCP	The central problem of the family.