Skip to main content

Math 428/529: Discrete Optimization

Jonathan A. Noel

Section 4.1 Vertex Colouring and Perfect Graphs

A proper colouring of a graph \(G\) is a mapping \(f:V(G)\to C\) for some set \(C\) of colours with the property that, if \(uv\in E(G)\text{,}\) then \(f(u)\neq f(v)\text{.}\) It is called a proper \(k\)-colouring if \(|C|=k\text{.}\) The chromatic number of \(G\text{,}\) denoted \(\chi(G)\text{,}\) is the minimum \(k\) such that \(G\) has a proper \(k\)-colouring. You may remember that we discussed a special case of this problem, the 3-Colourability problem (Problem 1.4.3), back in Chapter 1.
It is fairly clear that a graph \(G\) satisfies \(\chi(G)\leq 2\) if and only if it is bipartite, and that one can decide whether \(\chi(G)\leq 2\) or not in polynomial time (see Exercise 3). However, in contrast, the 3-Colourability problem (Problem 1.4.3) is NP-complete which implies that the problem of determining the chromatic number of a graph is NP-hard. Therefore, in general, there is no hope in coming up with a fast algorithm for computing the chromatic number of a general graph (unless \(\text{P}=\text{NP}\)). While the problem is intractable in general, it is still worth trying to “carve out” special cases of the problem that we can get a handle on.
The chromatic number of a graph is related to (but not determined by) the presence or absence of “dense” or “sparse” subsets of the vertex set. More precisely, say that a set \(S\subseteq V(G)\) is a clique if any two vertices in \(S\) are adjacent and a stable set if no two vertices in \(S\) are adjacent. We let \(\omega(G)\) (the clique number) and \(\alpha(G)\) (the stability number) be the cardinalities of the largest clique and stable set in \(G\text{,}\) respectively. Clearly, any graph \(G\) satisfies
\begin{equation*} \chi(G)\geq \omega(G) \end{equation*}
because any two vertices in a clique must receive different colours in any proper colouring. Also,
\begin{equation*} \chi(G)\geq \frac{|V(G)|}{\alpha(G)} \end{equation*}
because, for any colouring, the set of vertices of any given colour must form a stable set. Neither of these inequalities are tight in general. For example, an odd cycle \(C_{2k+1}\) for \(k\geq 2\) satisfies \(\chi(C_{2k+1})=3\) and \(\omega(C_{2k+1})=2\text{.}\) It is also not hard to find a graph with an arbitrarily large chromatic number such that \(|V(G)|/\alpha(G)\leq 1.0001\text{;}\) for example, one can start with a clique and add isolated vertices (i.e. vertices with no neighbours) to any graph until the inequality is true.
In this section, we focus on a special class of graphs defined in terms of a relationship between the chromatic number and clique number. For a set \(S\subseteq V(G)\text{,}\) we let \(G[S] = (S, \{uv\in E(G): u,v\in S\})\) be the subgraph of \(G\) induced by \(S\text{.}\)

Definition 4.1.1.

A graph \(G\) is said to be perfect if \(\chi(G[S])=\omega(G[S])\) for every \(S\subseteq V(G)\text{.}\)
Perfect graphs were first introduced due to their connection to interesting problems in information theory. One of the biggest breakthroughs in the history of graph theory is the following “structural characterization” of perfect graphs proved by Chudnovsky, Robertson, Seymour and Thomas.
The proof of the Strong Perfect Graph Theorem is beyond the scope of this course. However, we will prove the following precursor to it, now known as the Weak Perfect Graph Theorem, proved by Lovász.
In fact, what we will prove is the following elegant characterization of perfect graphs which easily implies Theorem 4.1.3 by observing that the clique number of a graph is equal to the stability number of its complement.

Proof.

First, suppose that \(G\) is perfect. Then, combining this with the trivial lower bound on the chromatic number in terms of the stability number, we have, for any \(S\subseteq V(G)\text{,}\)
\begin{equation*} \omega(G[S])=\chi(G[S])\geq \frac{|S|}{\alpha(G[S])}. \end{equation*}
For the other direction, we let \(G\) be a graph such that \(|S|\leq \alpha(G[S])\omega(G[S])\) for every set \(S\subseteq V(G)\) and prove that \(G\) is perfect. We proceed by induction on \(n:=|V(G)|\) where the case \(n=1\) is trivial. Note that, by induction, the graph \(G[S]\) is perfect for every proper subset \(S\subseteq G\text{.}\) We suppose that \(G\) is not perfect with the goal of deriving a contradiction. Let \(\omega:=\omega(G)\) and \(\alpha:=\alpha(G)\text{.}\) Since \(G\) is not perfect but every subgraph of \(G\) is, we must have that
\begin{equation*} \chi(G)>\omega. \end{equation*}
Recall that we are assuming that \(|S|\leq \alpha(G[S])\omega(G[S])\) for every \(S\subseteq V(G)\text{.}\) So, in particular,
\begin{equation*} n\leq \alpha\omega. \end{equation*}
We now establish the following two claims.

Proof.

Let \(S_0\) be any stable set in \(G\) of cardinality \(\alpha\text{.}\) For each vertex \(v\in S_0\text{,}\) we know that \(G\setminus\{v\}\) can be properly coloured with \(\omega(G\setminus\{v\})\leq \omega\) colours. So, the graph \(G\setminus\{v\}\) can be partitioned into exactly \(\omega\) stable sets (some of which could be empty). By taking such a partition for every vertex \(v\in S_0\text{,}\) we get a total of \(\alpha\omega\) stable sets with the property that every vertex outside of \(S_0\) is covered by \(\alpha\) of them and every vertex of \(S_0\) is covered by exactly \(\alpha-1\) of them. Taking these stable sets together with \(S_0\) completes the proof.

Proof.

First, let us show that there is a clique \(C_i\) of cardinality \(\omega\) disjoint from \(S_i\text{.}\) If \(S_i\) is empty, then we can let \(C_i\) be any clique of cardinality \(\omega\) in \(G\) and we are done. So, we assume \(S_i\neq \emptyset\text{.}\) If no such clique exists, then \(G[V(G)\setminus S_i]\) has clique number at most \(\omega-1\) which, since this graph is perfect, implies that it has chromatic number at most \(\omega-1\text{.}\) But then we get that \(G\) has chromatic number at most \(\omega\) by colouring \(G[V(G)\setminus S_i]\) with \(\omega-1\) colours and the vertices of \(S_i\) with the one additional colour. So, such a clique \(C_i\) exists.
Now, we show that, for any such choice of \(C_i\text{,}\) we have \(|C_i\cap S_j|=1\) for all \(j\neq i\text{.}\) Since \(|C_i\cap S_i|=0\) and every vertex of \(G\) is contained in exactly \(\alpha\) of the sets \(S_0,\dots,S_{\alpha\omega}\text{,}\) we have
\begin{equation*} \alpha\omega = \sum_{j\neq i}|S_j\cap C_i|. \end{equation*}
So, either all of the terms on the right side of the above equality are equal to one, or there would have to be at least one term that is greater than one. However, a clique and stable set cannot intersect on two vertices, and so we must have \(|S_j\cap C_i|=1\) for all \(j\neq i\text{.}\)
Okay, so let us now use a bit of linear algebra to finish this off. Label the vertices of \(G\) by \(v_1,\dots,v_n\text{.}\) Let \(A\) and \(B\) be \((\alpha\omega+1)\times n\) matrices where
  • \(a_{i,j}=1\) if \(v_j\in S_{i-1}\) and \(a_{i,j}=0\) otherwise.
  • \(b_{i,j}=1\) if \(v_j\in C_{i-1}\) and \(b_{i,j}=0\) otherwise.
Then the dot product of the \(i\)th row of \(A\) with the \(j\)th row of \(B\) simply computes \(|S_i\cap C_j|\text{.}\) Therefore
\begin{equation*} AB^T=\begin{bmatrix} 0 \amp 1\amp 1\amp \cdots \amp 1\\ 1 \amp 0\amp 1\amp \cdots \amp 1\\ \vdots \amp \ddots \amp \cdots \amp\vdots\\ 1 \amp 1 \amp 1\amp \cdots \amp 0 \end{bmatrix} \end{equation*}
where the number of rows and columns in the above matrix is \(\alpha\omega+1\text{.}\) The above matrix is non-singular, and so
\begin{equation*} \alpha\omega+1 =\rank(AB^T)\leq \min\{\rank(A),\rank(B)\}\leq n. \end{equation*}
However, this contradicts the fact that \(n\leq \alpha\omega\) and completes the proof.
It is obvious that bipartite graphs are perfect, since any bipartite graph satisfies \(\chi(G)=\omega(G)=2\) or \(\chi(G)=\omega(G)=1\) and all induced subgraphs of a bipartite graph are bipartite. So, by the Weak Perfect Graph Theorem, the complement of any bipartite graph is perfect as well. Now, let’s see what this tells us. A proper colouring of the complement of a graph \(G\) is equivalent to a partition of \(V(G)\) into cliques. Of course, every clique in \(G\) has cardinality \(1\) or \(2\text{,}\) and disjoint cliques of cardinality \(2\) form a matching, and so the chromatic number of \(\overline{G}\) is precisely \(|V(G)|-\nu(G)\text{.}\) Also, the clique number of \(\overline{G}\) is just the stability number of \(G\text{,}\) which is precisely \(|V(G)|-\tau(G)\text{.}\) So, the Weak Perfect Graph Theorem gives us another proof of Kőnig’s Theorem: \(\nu(G)=\tau(G)\) in any bipartite graph \(G\text{!}\)
Recall that, for bipartite graphs, the matching polytope is equal to the set of all fractional matchings (Corollary 3.2.5). We close this section by showing that a similar phenomenon holds for stable sets in perfect graphs. For a graph \(G\) with vertices \(v_1,\dots,v_n\text{,}\) a fractional stable set is a vector \(x\in\mathbb{R}^n\) such that \(x\geq 0\) and \(\sum_{v_i\in C}x_i\leq 1\) for every clique \(C\) of \(G\text{.}\) The stable set polytope of \(G\) is the convex hull of all indicator vectors of stable sets in \(G\text{.}\) It is evident that every element of the stable set polytope is a fractional stable set, however the converse is not true; as is often the case, odd cycles provide a counterexample. However, when \(G\) is perfect, the two polytopes coincide.

Proof.

Every element of the stable set polytope is easily seen to be a fractional stable set. So, what remains is to show that every fractional stable set is a convex combination of indicator vectors of stable sets. Let \(x\) be a fractional stable set. If \(x\) is a vertex of the polytope \(\{x: 0\leq x\leq 1, x_i+x_j\leq 1\text{ for }v_iv_j\in E(G)\}\text{,}\) then all of the entries of \(x\) are rational. If it is not a vertex, then it can be written as a convex combination of two fractional stable sets with integer entries. So, from here forward, we may assume that \(x\) has integer entries. Let \(q\in\mathbb{N}\) and \(p\in \mathbb{Z}^n\) so that \(x=\frac{1}{q}p\text{.}\) Next, we will use the following claim.

Proof.

Let \(G'\) be a graph obtained from \(G\) by replacing each vertex \(v_i\) with a clique of cardinality \(p_i\text{.}\) By Claim 4.1.8, \(G'\) is perfect. We claim that \(\omega(G')\leq q\text{.}\) Indeed, let \(C'\) be any clique in \(G'\) and let \(C\) be the set of vertices of \(G\) such that \(v\in C\) if and only if \(C'\) contains at least one vertex of the clique of \(G'\) corresponding to \(v\text{.}\) Then we have
\begin{equation*} |C'|\leq \sum_{v_i\in C}p_i = q\sum_{v_i\in C}x_i\leq q. \end{equation*}
Now, since \(G'\) is perfect, it has a proper colouring, say \(f:V(G')\to\{1,\dots,q\}\text{.}\) For each \(1\leq j\leq q\text{,}\) let \(z^j\in\{0,1\}^n\) be a vector where \(z_i^j=1\) if the colour \(j\) is used by \(f\) on some vertex of the clique of \(G'\) corresponding to \(v_i\text{.}\) Then \(z^j\) is the indicator vector of a stable set in \(G\) and our original vector \(x\) satisfies
\begin{equation*} x=\frac{1}{q}\sum_{j=1}^qz^j \end{equation*}
and so \(x\) is indeed a convex combination indicator vectors of stable sets.
We close this section by stating a few important theorems in graph colouring. While we will not prove these theorems, they are worth being aware of. The first one is certainly the most famous result in graph colouring, if not graph theory itself. A graph is planar if it can be drawn on the plane \(\mathbb{R}^2\) without crossing edges.
The proof of the Four Colour Theorem is an extremely complicated induction proof using something known as the discharging method. At a high level, the discharging method starts by identifying a long list of “local substructures” such that a minimal counterexample cannot contain any of these substructures (otherwise, one could replace that substructure with a smaller one and it would yield a smaller counterexample). Typically, these substructures tend to be “sparse” subgraphs which are relatively easy to colour. After this, one proves that it is impossible for any planar graph to forbid all of these substructures simultaneously. The trick here is to assign each vertex, edge and face of the planar graph to a number called a charge with the property that the sum of all charges is negative by Euler’s Polyhedral Formula. Then one proves that, in any planar graph in which none of these sparse substructures appear, it is possible to “redistribute” the charges to that every vertex, edge and face has non-negative charge, which contradicts the fact that the sum of the charges is negative and completes the proof. The problem of finding such “redistribution” or “discharging” phrased in terms of showing that a certain LP has a non-negative value. Moreover, by LP duality, if the value is negative, there must be a set of constraints which causes this to occur, and these constraints correspond to local substructures; if one can rule out the existence one of these substructures, then the value of the LP may increase. Since LPs can be solved quickly, this provides us with a reasonably efficient method for searching for discharging rules. Still, in the case of the Four Colour Theorem, the set of forbidden local substructures and the discharging rules end up being very complicated. As a result, the proofs of the Four Colour Theorem that have been found are so complicated that no one has dared to verify them by hand; they have, however, been checked by computer.
It is trivial that any graph \(G\) satisfies \(\chi(G)\leq \Delta(G)+1\text{,}\) where \(\Delta(G)\) is the maximum degree of a vertex of \(G\text{.}\) The next theorem classifies the cases in which this inequality is tight. Unlike the Four Colour Theorem, the proof of this theorem is fairly reasonable.
Recall that the clique number of a graph provides a lower bound on its chromatic number. More generally, it seems evident that having many dense subsets should cause the chromatic number of a graph to be large. A natural question is whether the converse is true: does every graph of high chromatic number contain small “dense” subsets? The next theorem, which is proven via an interesting probabilistic approach, tells us that this is not the case. The girth of a graph \(G\) is the length of its shortest cycle.
Here is a YouTube video related to this section:
If you are interested in the proof of Theorem 4.1.11, a great source is the following video of Yufei Zhao at MIT.
PrevTopNext