Vertex colorings

Perhaps more than the edge-coloring problem, researchers have paid signif-icant attention to the vertex-coloring problem. In essence, the problem boils down to finding a coloring of the vertices of a (simple, connected) graph such that no two adjacent vertices have the same color. The problem be-comes interesting when we try to use a minimal number of different colors.

Definition 3.9:Consider a simple connected graph G. G is k-vertex colorable if there exists a partitioning of V(G)into k disjoint sets V1, . . . , V_ksuch that no two vertices from the same Viare adjacent.

Note 3.7 (Mathematical language)

The mathematical formulation that no two vertices from the same V_iare adja-cent is:

∀V_i,∀_{x, y}∈V_i:@e∈E(G): e= h_{x, y}i

where@is to be read as “there does not exist...” In other words, for all pairs of distinct vertices in V_i there is not an edge joining those two vertices. Note that in Chapter 2 we mentioned thath_{x, y}iis strictly speaking nothing else but stating that x and y are adjacent. If use the notation¬h_{x, y}ito indicate that x and y are not adjacent, we can simplify our mathematical formulation to:

∀V_i,∀x, y∈V_i:¬hx, yi

It is important that you gradually become familiar with these type of formal statements, but also that you can devise them yourself.

The vertex-coloring problem for a given graph G is finding the minimal k for which G is k-vertex colorable. This minimal k is called the chromatic numberof G, denoted as χ(G).

Before we delve into various details, let us first consider a simple, yet illustrative application of vertex colorings: scheduling classes. We consider a set of n classes that need to be taught to a population of students. Two classes are not allowed to be scheduled during the same time slot if they are to be taught to the same group of students. The question is how to schedule the classes in the minimal number of slots.

This problem can be modeled by means of a graph G in which the n classes are represented by n vertices v1, . . . , vn. Two vertices are connected by an edge if and only if there is a group of students to which the two classes must be taught. It is not too difficult to see that the minimal number of slots needed to teach all classes corresponds to χ(G), as we formally prove next.

Theorem 3.4:The minimum number of time slots needed for the class-scheduling problem is the value of χ(G)of the associated graph G.

Proof. We first prove that we need at most χ(G)slots to schedule all classes.

From the definition of chromatic number, we know that any two vertices with the same color cannot be adjacent. This also means that the two classes associated with those two vertices need not be taken by the same group of students. Hence, they can be scheduled at the same time, that is, for the same time slot. In general, all vertices with the same color represent the set of classes that can be scheduled at the same time. This means that χ(G)slots are sufficient to schedule all classes.

3.3. COLORINGS 3-19

We now prove that we need at least χ(G)slots to schedule all classes.

Suppose that k< χ(G)slots are sufficient. Classes in the same slot should be taught to different groups. In the graph G, this means that the vertices representing those classes should be nonadjacent. As a consequence, we should be able to use only k different colors yielding a k-vertex coloring of G, which contradicts the fact that χ(G)is minimal.

Note 3.8 (Proof techniques)

In our proof we have applied two techniques: the well-known proof by contra-diction, and what is known as a direct proof. We have applied the latter already on several occasions, but this is the first time we mention it explicitly. As its name suggests, a direct proof is a general technique by which you show a state-ment to hold through straightforward deduction. In our proof, this straightfor-ward deduction is done by simply considering the definition of the chromatic number and setting up a logical reasoning.

An indirect proof is typically done by eliminating cases, and indeed, a proof by contradiction is an example of an indirect proof.

Vertex colorings are often used in the context of scheduling and opti-mization problems. Unfortunately, finding the chromatic number of a graph is, in general, a notoriously difficult problem. As with determining whether two graphs are isomorphic, we are dealing with a problem for which no known efficient solution exists (at least not when considering graphs for which χ ≥ 3). In effect, to determine the chromatic number we would, in principle, need to test all color assignments before coming to conclusions conclusions.

Fortunately, we can alleviate problems a bit: the chromatic number of a graph G is bounded by its maximal vertex degree∆(G):

Theorem 3.5:For any (simple, connected) graph G, χ(G) ≤∆(G) +1.

Proof. We prove that the theorem holds by induction on the number n of vertices of G. For n=1, we need to consider the complete graph K₁. Obvi-ously, χ(K1) =1 and∆(K1) =0, so that the theorem holds.

Now assume the theorem holds for all graphs on k > 1 vertices, and consider a graph G with k+1 vertices. Let vertex v ∈ V(G)with δ(v) =

∆(_G). The graph G^∗=_G−v has k vertices, so there exists a vertex coloring C^∗of G^∗with χ(G^∗) ≤ _∆(G^∗) +1 different colors. If∆(G) =_∆(G^∗), then in the worst case, the number of colors used in G^∗is χ(G^∗) =_∆(G^∗) +1=

∆(G) +1. Considering that v has∆(G) −1 neighbors, this means that there is a color available from the ones used in G^∗that we can use for v and which has not been used for any of v’s neighbors.

On the other hand, if∆(G) > ∆(G^∗), then we can simply permit our-selves to introduce a new color for v and use the ones from an optimal col-oring of G^∗ for all other vertices. At worst, we will then have that χ(G) = χ(G^∗) +1≤ _∆(G^∗) +2. If∆(G^∗) < _∆(G), then the smallest value of∆(G) for which this inequality is true, is, of course, when∆(G) = ∆(G^∗) +1.

Therefore, we know that∆(G^∗) +2 ≤ ∆(G) +1, so that we indeed have that χ(G) ≤∆(G) +1.

Coloring vertices would have perhaps been just one of those many graph-theoretical problems, if not for an intriguing conjecture that proved to be extremely difficult to tackle. Consider an arbitrary area map, such as one consisting of countries. We ask ourselves a simple question: if we are to color each country such that no two neighboring countries have the same color, how many different colors do we need at most? The answer turns out to be four, but it took more than 120 years to find it! Even worse, it took a computer program to find the answer. Many mathematicians were not amused.

Let’s see what this map-coloring problem has to do with vertex colorings of graphs. First, the problem is easily translated into finding vertex color-ings of a planar graph. Each country is represented by a vertex, and two vertices are joined by an edge if and only if they are neighbors (i.e., they share a border). Figure 3.6 shows the map of Europe and its corresponding planar graph.¹

In 1852, the map-coloring problem surfaced and some specific cases were proven. However, it wasn’t until 1976 that Appel and Haken [1976] actually solved it. More formally, they proved:

Theorem 3.6:For any planar graph G, χ(G) ≤_4.

The only problem with their proof was that it was extremely difficult to ver-ify. First, they split the problem into over 2000 different cases. Second, they wrote computer programs to test each case. This approach was received with a lot of reservations, notably also because researchers claimed that one would need to formally prove the correctness of the computer programs before considering their outcomes to be correct. It may be clear that Ap-pel and Haken had entered the gray area between elegant mathematics and mechanical case testing by computers. So far, a “traditional” mathematical proof has not yet been found. It is worth noting that at that time it took more than 1200 hours of compute time to tackle the four-color conjecture.

By now, however, there is no more debate about the correctness of the con-jecture [Appel and Haken, 1986].

1For simplicity, some specific details have been omitted.

3.3. COLORINGS 3-21

Figure 3.6: A map of Europe and its corresponding representation by a planar graph, along with a four-coloring of the vertices.

To illustrate how complications can easily sneak into mathematics, it turns out that it is relatively easy to prove that the chromatic number of a planar graph is less than or equal to 5. Before we give this proof, we need to prove the following:

Theorem 3.7:Every planar graph G has a vertex v with δ(v) ≤_5.

Proof. For all planar graphs with n ≤ 6 vertices, the theorem is obviously true. For planar graphs with n>6, we prove the theorem by contradiction.

To this end, consider a planar graph G for which n>6. Let m be the number of edges of G. We know that∑v∈V(G)δ(v) = 2m. Therefore, if there is no vertex with degree 5 or less, then 6n≤ 2m. In addition, from Theorem 2.9 we know that m ≤ 3n−6, and thus that 6n ≤ 6n−12. Obviously, this is false, meaning that our assumption that there is no vertex with degree 5 or less must be false as well.

Note 3.9 (Proof techniques)

Note that this proof by contradiction tells us that there must be a vertex with degree less or equal to five, but it gives us no further hints on how to find such a vertex. This is typical for existential proofs, in contrast to proofs by construction.

Following Chartrand [1977], we now prove the following theorem by induc-tion on the number of vertices:

Theorem 3.8:For any planar graph G, χ(G) ≤5.

Proof. Let n = |_V(_G)|_{. For n} = 1, the theorem is obviously true. Assume the theorem holds for all planar graphs with k > 1 vertices and consider a graph G with k+1 vertices. Let vertex v with δ(v) ≤ 5 (we just proved that such a vertex exists), and consider the graph G^∗ = G−v. Because

|V(G^∗)| = k, we know there exists a 5-vertex coloring of G^∗, with, say, colors c1, . . . , c5. If not all of these colors are used by the vertices in the neighbor set N(v)of v, we can assign the unused color to v and will thus have constructed a 5-vertex coloring of G.

Consider the situation that all five colors have been used for coloring the vertices of N(v). Note that δ(v) = 5 so that we may assume that N(v) = {v1, . . . , v5}and that vertex vihas color ciaccording to a clockwise ordering of these vertices around v, as shown in Figure 3.7. We will rearrange the colors of G^∗such that we can assign one of the colors cito v.

v v1

v2

v3 v4

v5

Figure 3.7: The ordering of vertices adjacent to v. Vertex vihas color ci.

Let us first assume that there is no(_{v1, v3})_{-path in G}^∗for which all ver-tices have been colored either c₁or c₃. Now consider all paths in G^∗ that originate in v₁and for which the vertices are colored either c₁or c3. These paths induce a subgraph H of G^∗. Note that v36∈V(H), as this would mean that there is a(v1, v3)-path. For the same reason, none of v3’s neighbors can be in H, i.e., N(v3) ∩V(H) = ∅. What we can then do is interchange the

3.3. COLORINGS 3-23

colors c1and c3in H, which leads to another 5-vertex coloring of G^∗. How-ever, in this case, vertex v₁ will be colored c₃, and none of the vertices in N(v)will be colored c₁. Therefore, we can use c₁for v.

Let us now assume that there is a(v1, v3)-path P in G^∗for which all ver-tices have been colored either c1or c3. Consider the cycle[v3, v, v1, P]. This cycle either encloses v2 (as shown in Figure 3.7), or it encloses v4and v5. Hence, because G is planar, there can be no(v2, v4)-path in G^∗whose ver-tices are colored using only c₂and c₄. Again, consider all paths originating in v2 and that have either color c2 or c₄. As before, these paths induce a subgraph H⁰of G^∗. We interchange the colors of the vertices in H⁰, allowing us to assign color c2to v, and thus leading to a 5-vertex coloring of G.

There are many other properties related to coloring vertices, but we shall not discuss these any further. By now, it should have become clear that ver-tex coloring imposes a number of very difficult questions (such as efficiently finding the chromatic number of a graph), and that even under relatively fa-vorable conditions such as planarity, taking a small step from one problem formulation (“χ≤5”) to another (“χ≤4”) can make a difference between simple and complicated solutions.

C

4