Skip to content

Formulations of coloring problems

Part 2 · Formulations and their properties · Chapter 11 · Lecture notes, volume 2 (PDF) · Slides · Exercises: Coloring problems

Prerequisites

Objectives

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

  • write the ILP model of the Vertex Coloring Problem and explain the role of the activation variables \(y_c\);

  • write the two LP relaxations and their duals, and compute their optimal solutions;

  • prove that the optimal value of the LP relaxations is \(2\) for every graph with an edge;

  • explain why this bound is very weak, and why the model is not enough to color a graph.

11.1 Overview of the family

  • The ILP models of the coloring problems use an upper bound \(k\) on the number of colors and the set \(\mathscr{C} = \{1,2,\dots,k\}\) of the colors that may be used.

  • The binary assignment variables \(x_{vc}\) give a color \(c \in \mathscr{C}\) to every vertex \(v \in V\), and the binary activation variables \(y_c\) say whether color \(c\) is used.

  • Each edge and each color give one constraint, which forbids the same color on the two endpoints of the edge, and the objective function minimizes the number \(\sum_{c \in \mathscr{C}} y_c\) of colors used.

The coloring models are assignment models, as the packing models: a vertex is assigned to a color as an item is assigned to a bin, and the edge constraints replace the capacity constraints.

  • The table lists the members of the family, with the name of their ILP model and the section that writes it.
Problem Model Variables Section
VCP \(\mathrm{ILP}_{\mathrm{VCP}}\) binary \(x_{vc}\) and \(y_c\) 11.2

  • Overview

    Overview of the family

    Open

  • 11.2 An ILP model for the Vertex Coloring Problem

    A second Linear Programming relaxation · Typical mistakes · In summary

    Open

Next: 11.2 An ILP model for the Vertex Coloring Problem

Exercises on this chapter: Coloring problems