Graph Coloring: Rules, Bounds, Algorithms, and Applications

All flashcards

Proper vertex coloring

A vertex assignment in which the endpoints of every edge have different colors.

Chromatic number

The minimum number of colors needed for a proper vertex coloring of a graph.

Color class

The vertices assigned one color; in a proper coloring, they form an independent set.

Proper edge coloring

An edge assignment in which edges sharing an endpoint have different colors.

Total coloring

A coloring of vertices and edges where adjacent or incident elements have different colors.

Quiz questions

1. What does the chromatic polynomial $P(G,t)$ count?Answer: Proper vertex colorings of $G$ using a palette of $t$ colors.
2. What lower bound on the chromatic number follows from a clique of size $r$?Answer: $\chi(G)\geq r$, since all vertices in the clique need distinct colors.
3. What does the four color theorem guarantee for every planar graph?Answer: A proper vertex coloring using at most four colors.
4. What does Kőnig's theorem state about edge coloring of a bipartite graph?Answer: Its edge chromatic number equals its maximum degree.
5. For a fixed integer $k\geq 3$, what is the complexity status of deciding whether a graph is $k$-colorable?Answer: The decision problem is NP-complete.