maths.free › Combinatorics & Graph Theory › 3. Graph Theory › Coloring

Coloring

Investigation Mapmakers in the fictional land of Euleria have drawn the borders of the various dukedoms of the land. To make the map pretty, they wish to color each region.

Section Preview

Investigation

Mapmakers in the fictional land of Euleria have drawn the borders of the various dukedoms of the land. To make the map pretty, they wish to color each region. Adjacent regions must be colored differently, but it is perfectly fine to color two distant regions with the same color. What is the fewest colors the mapmakers can use and still accomplish this task?

Perhaps the most famous graph theory problem is how to color maps.

Given any map of countries, states, counties, etc., how many colors are needed to color each region on the map so that neighboring regions are colored differently?

Actual map makers usually use around seven colors. For one thing, they require watery regions to be a specific color, and with a lot of colors it is easier to find a permissible coloring. We want to know whether there is a smaller palette that will work for any map.

How is this related to graph theory? Well, if we place a vertex in the center of each region (say in the capital of each state) and then connect two vertices if their states share a border, we get a graph. Coloring regions on the map corresponds to coloring the vertices of the graph. Since neighboring regions cannot be colored the same, our graph cannot have vertices colored the same when those vertices are adjacent.

In general, given any graph \(G\), a coloring of the vertices is called (not surprisingly) a vertex coloring. If the vertex coloring has the property that adjacent vertices are colored differently, then the coloring is called proper. Every graph has a proper vertex coloring. For example, you could color every vertex with a different color. But often you can do better. The smallest number of colors needed to get a proper vertex coloring is called the chromatic number of the graph, written \(\chi(G)\). \(\chi(G)\) the chromatic number of \(G\)

Our goal in this section is to see how graph coloring can be used to solve some problems and to understand some basic properties of graph coloring.

Coloring Vertices

Investigation

The math department plans to offer 10 classes next semester. Some classes cannot run at the same time (perhaps they are taught by the same professor, or are required for seniors).

Class:Conflicts with:
AD I
BD I J
CE F I
DA B F
EC H I
FC D I
GJ
HE I J
IA B C E F H
JB G H

How many different time slots are needed to teach these classes (and which should be taught at the same time)? More importantly, how could we use graph coloring to answer this question?

The best way to get a feel for the chromatic number is to actually try to color some graphs.

Example

Find the chromatic number of the graphs below.

Solution

The graph on the left is \(K_6\). The only way to properly color the graph is to give every vertex a different color (since every vertex is adjacent to every other vertex). Thus the chromatic number is 6.

The middle graph can be properly colored with just 3 colors (Red, Blue, and Green). For example:

There is no way to color it with just two colors, since there are three vertices mutually adjacent (i.e., a triangle). Thus the chromatic number is 3.

The graph on the right is just \(K_{2,3}\). As with all bipartite graphs, this graph has chromatic number 2: color the vertices on the top row red and the vertices on the bottom row blue.

It appears that there is no limit to how large chromatic numbers can get. It should not come as a surprise that \(K_n\) has chromatic number \(n\). So how could there possibly be an answer to the original map coloring question? If the chromatic number of a graph can be arbitrarily large, then it seems like there would be no upper bound to the number of colors needed for any map. But there is.

The key observation is that while it is true that for any number \(n\) there is a graph with chromatic number \(n\), only some graphs arrive as representations of maps. If you convert a map to a graph, the edges between vertices correspond to borders between the countries. So you should be able to connect vertices in such a way that the edges do not cross. In other words, the graphs representing maps are all planar!

So the question is, what is the largest chromatic number of any planar graph? The answer is the best-known theorem of graph theory:

Here is a further example:

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Coloring Edges

The chromatic number of a graph tells us about coloring vertices, but we could also ask about coloring edges. Just like with vertex coloring, we might insist that adjacent edges must be colored differently. Here, we are thinking of two edges as being adjacent if they are incident to the same vertex. The least number of colors required to properly color the edges of a graph \(G\) is called the chromatic index of \(G\), written \(\chi'(G)\). \(\chi'(G)\) the chromatic index of \(G\)

Example

Six friends decide to spend the afternoon playing chess. Everyone will play everyone else once. They have plenty of chess sets, but nobody wants to play more than one game at a time. Games will last an hour (thanks to their handy chess clocks). How many hours will the tournament last?

Solution

Represent each player with a vertex and put an edge between two players if they play each other. In this case, we get the graph \(K_6\):

We must color the edges; each color represents a different hour. Since different edges incident to the same vertex will be colored differently, no player will be playing two different games (edges) at the same time. Thus we need to know the chromatic index of \(K_6\).

Notice that for sure \(\chi'(K_6) \ge 5\), since there is a vertex of degree 5. It turns out, 5 colors is enough (go find such a coloring). Therefore the friends will play for 5 hours.

Interestingly, if one of the friends in the above example left, the remaining 5 chessletes would still need 5 hours: the chromatic index of \(K_5\) is also 5.

In general, what can we say about the chromatic index? Certainly \(\chi'(G) \ge \Delta(G)\). But how much higher could it be? Only a little higher.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (14)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. True or false: if a graph contains a vertex of degree 5, then the chromatic number of the graph is at least 5. Explain.

  2. In your own words, explain the difference between chromatic number and chromatic index.

  3. What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.

  4. What is the smallest number of colors you need to properly color the vertices of \(K_{4,5}\)? That is, find the chromatic number of the graph.

    Openbaar die antwoord

    2, since the graph is bipartite. One color for the top set of vertices, another color for the bottom set of vertices.

  5. Draw a graph with chromatic number 6 (i.e., which requires 6 colors to properly color the vertices). Could your graph be planar? Explain.

    Openbaar die antwoord

    For example, \(K_6\). If the chromatic number is 6, then the graph is not planar; the 4-color theorem states that all planar graphs can be colored with 4 or fewer colors.

  6. Find the chromatic number of each of the following graphs.

    Openbaar die antwoord

    The chromatic numbers are 2, 3, 4, 5, and 3 respectively from left to right.

  7. What is the smallest number of colors that can be used to color the vertices of a cube so that no two adjacent vertices are colored identically?

    Openbaar die antwoord

    The cube can be represented as a planar graph and colored with two colors as follows:

    Since it would be impossible to color the vertices with a single color, we see that the cube has chromatic number 2 (it is bipartite).

  8. Prove the 6-color theorem: every planar graph has chromatic number 6 or less. Do not assume the 4-color theorem (whose proof is MUCH harder), but you may assume the fact that every planar graph contains a vertex of degree at most 5.

  9. Not all graphs are perfect. Give an example of a graph with chromatic number 4 that does not contain a copy of \(K_4\). That is, there should be no 4 vertices all pairwise adjacent.

    Openbaar die antwoord

    The wheel graph below has this property. The outside of the wheel forms an odd cycle and so requires 3 colors; the center of the wheel must be a different color from all the outside vertices.

  10. Find the chromatic number of the graph below and prove you are correct.

    Openbaar die antwoord

    Hint:

    The chromatic number is 4. Now prove this!

    Note that you cannot use the 4-color theorem, or Brooke's theorem, or the clique number here. In fact, this graph, called the Grötzsch graph, is the smallest graph with chromatic number 4 that does not contain any triangles.

  11. Prove that any connected graph \(G\) which contains at least one vertex of degree less than \(\Delta(G)\) (the maximal degree of all vertices in \(G\)) has chromatic number at most \(\Delta(G)\).

  12. You have a set of magnetic alphabet letters (one of each of the 26 letters in the alphabet) that you need to put into boxes. For obvious reasons, you don't want to put two consecutive letters in the same box. What is the fewest number of boxes you need (assuming the boxes are able to hold as many letters as they need to)?

    Openbaar die antwoord

    If we drew a graph with each letter representing a vertex and each edge connecting two letters that were consecutive in the alphabet, we would have a graph containing two vertices of degree 1 (A and Z) and the remaining 24 vertices all of degree 2 (for example, \(D\) would be adjacent to both \(C\) and \(E\)). By Brooks' theorem, this graph has chromatic number at most 2, as that is the maximal degree in the graph, and the graph is not a complete graph or odd cycle. Thus only two boxes are needed.

  13. Suppose you colored the edges of a graph either red or blue (not requiring that adjacent edges be colored differently). What must be true of the graph to guarantee some vertex is incident to three edges of the same color? Prove your answer.

    Openbaar die antwoord

    Hint:

    You can color \(K_5\) in such a way that every vertex is adjacent to exactly two blue edges and two red edges. However, there is a graph with only 5 edges that will result in a vertex incident to three edges of the same color, no matter how they are colored. What is it, and how can you generalize?

  14. Prove that if you color every edge of \(K_6\) either red or blue, you are guaranteed a monochromatic triangle (that is, an all-red or an all-blue triangle).

    Openbaar die antwoord

    Hint:

    The previous exercise is useful as a starting point.

Symbols used here

i
imaginary unit
i² = −1.
\leq,\ \geq
less/greater than or equal
Inequalities that allow equality; < and > exclude it.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.

How to: Coloring

  1. Determine the chromatic number of a graph.
  2. Determine the chromatic index of a graph
  3. Decide whether using the chromatic number or chromatic index is more appropriate to solve particular problems.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Probeer jou eie

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Meer in Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs