Skip to content

Coloring problems

Part 1 · Combinatorial optimization problems · Chapter 4 · Lecture notes, volume 1 (PDF) · Slides · Exercises: Coloring problems · App: Vertex coloring: greedy and DSATUR

Prerequisites

Objectives

At the end of this chapter you will be able to:

  • use the basic notions on graphs: neighbourhood, degree, induced graph, complement graph, clique and stable set;

  • state the definition of the vertex coloring problem and the assumptions on the graph;

  • count the candidate solutions of a small instance and recognize that they are partitions;

  • find a coloring by hand and compute the clique bound and the stable set bound;

  • explain why the clique bound is not always tight.

4.1 Overview of the family

  • The coloring problems share the same data: a simple undirected graph \(G = (V,E)\), whose edges are the pairs of vertices in conflict.

  • A solution assigns a color to every vertex, so that the two endpoints of every edge receive different colors: the vertices with the same color form a stable set of \(G\).

  • The objective is to minimize the number of colors used.

A coloring problem partitions the vertices of a graph into the fewest stable sets. The notions on graphs of the next subsection are the common notation of the family.

  • The table lists the members of the family, with the section that defines each of them.
Problem Acronym Solution Section
vertex coloring problem VCP a partition of \(V\) into stable sets 4.2

4.1.1 A short review of graphs

Definition 4.1: graph, neighbourhood, induced graph and complement graph

  • A graph \(G = (V,E)\) is given by a finite set \(V\) of vertices and a set \(E\) of edges, each edge being a \(2\)-element subset of \(V\). We write \(n = |V|\) and \(m = |E|\); the vertices are labelled \(1,2,\dots,n\). All the graphs of this chapter are simple and undirected.

  • Two distinct vertices \(u\) and \(v\) are adjacent if \(\{u,v\} \in E\). The neighbourhood of a vertex \(v\) is the set \(N(v) = \{\, u \in V : \{u,v\} \in E \,\}\), and its degree is \(\deg(v) = |N(v)|\).

  • For a subset \(U \subseteq V\) the induced graph \(G[U] = (U, E[U])\) has the vertices of \(U\) and the edges of \(E\) with both endpoints in \(U\).

  • The complement graph \(\overline{G} = (V, \overline{E})\) has the same vertices as \(G\), and two distinct vertices are adjacent in \(\overline{G}\) if and only if they are not adjacent in \(G\).

Definition 4.2: clique and stable set

Let \(G = (V,E)\) be a graph.

  1. A clique is a subset \(K \subseteq V\) of pairwise adjacent vertices: \(\{u,v\} \in E\) for all \(u,v \in K\) with \(u \neq v\).

  2. A stable set (also called independent set) is a subset \(Q \subseteq V\) of pairwise non-adjacent vertices: \(\{u,v\} \notin E\) for all \(u,v \in Q\) with \(u \neq v\).

The clique number \(\omega(G)\) is the largest number of vertices of a clique, and the stability number \(\alpha(G)\) is the largest number of vertices of a stable set.

  • A stable set of \(G\) is a clique of the complement graph \(\overline{G}\), and vice versa. A vertex alone and the empty set are both a clique and a stable set.

A clique is a group of vertices that pairwise conflict; a stable set is a group of vertices with no conflict. In a coloring, the vertices of a clique need different colors, and the vertices of a stable set can share one.

  • Overview

    Overview of the family · A short review of graphs

    Open

  • 4.2 The vertex coloring problem

    Two simple bounds · Counting the solutions, a first solution and the bounds · Remarks · Typical mistakes · In summary

    Open

Next: 4.2 The vertex coloring problem

Exercises on this chapter: Coloring problems

In depth: what the course does on this problem

In the interactive lab: Vertex coloring: greedy and DSATUR.