Skip to main content

Discrete Structures: Course Notes

Mike Janssen

Section 6.2 Graph Coloring

Worksheet 6.2.1 Worksheet
A4US

Guiding Questions.

Today, we’ll seek to answer the questions:
  • What is the chromatic number of a graph?
  • How many colors are required to color a planar graph?

Subsection 6.2.1.1 Vertex Coloring

In this section, we consider the problem of coloring a graph. We begin with an exploration.
Problem 6.2.1.
In your work as a cartographer, you’ve made many maps. In order to make your maps comprehensible, you prefer to give adjacent states different colors. How many colors are required to color the map in Figure 6.2.2 so that adjacent states are colored differently?
Figure 6.2.2. A hypothetical map (source
 1 
discrete.openmathbooks.org/dmoi3/sec_coloring.html
).
One of the interesting problems in graph theory is the problem of vertex coloring. In a proper vertex coloring, each vertex is assigned a color so that adjacent vertices are given different colors. We make this precise using the notion of function in Definition 6.2.3.
Definition 6.2.3.
Let \(G = (V,E)\) be a graph, \(V = \set{v_1, v_2, \ldots, v_n}\text{,}\) and \(C = \set{c_1, c_2, \ldots, c_k}\) a set of labels called colors. A proper vertex coloring is a function \(c : V\to C\) such that if \(\set{v_i, v_j}\in E\text{,}\) \(c(v_i)\ne c(v_j)\text{.}\)
The chromatic number of \(G\text{,}\) denoted \(\chi(G)\text{,}\) is the cardinality of the smallest set of colors \(C\) for which there is a proper coloring for the vertices of \(G\text{.}\)
LaTeX Code 6.2.4.
To typset \(\chi(G)\) in \(\LaTeX\text{,}\) use the command \chi(G) in math mode.
Activity 6.2.6.
Calculate the chromatic numbers of the graphs below. Be ready to justify your answers.
Figure 6.2.7. A graph.
Figure 6.2.8. A graph.
Figure 6.2.9. A graph.
Let’s explore some properties of vertex coloring.
For Theorem 6.2.11, recall the definition of the clique number of a graph.
Problem 6.2.12.
Provide examples that demonstrate that the bounds on \(\chi(G)\) from Theorem 6.2.10 and Theorem 6.2.11 cannot be improved in general.
Problem 6.2.13.
Provide examples of graphs \(G_1\) and \(G_2\) that demonstrate that we may have \(\chi(G_1) \lt n\) and that \(\chi(G_2) \gt \omega(G_2)\text{.}\)

Worksheet 6.2.2 Worksheet
A4US

Subsection 6.2.2.1 Edge Coloring

In Subsection 6.2.1.1, we explored the problem of minimizing the number of colors needed to properly color the vertices of a graph \(G\text{.}\) In the sequel, we consider the problem of coloring edges.
Definition 6.2.15.
Let \(G = (V,E)\) be a graph, \(E = \set{e_1, e_2,\ldots, e_n}\text{,}\) and \(C = \set{c_1, c_2, \ldots, c_k}\) a set of labels called colors. A proper edge coloring of \(G\) is a function \(c: E \to C\) such that \(c(e_i) \ne c(e_j)\) if \(e_i \cap e_j \ne \emptyset\text{.}\)
Further, suppose \(C\) admits a proper edge coloring of \(G\text{.}\) We label the cardinality of a smallest such \(C\) the chromatic index of \(G\text{,}\) and use the symbol \(\chi'(G)\text{.}\)
Problem 6.2.17.
Calculate \(\chi'(C_{2n+1})\text{,}\) where \(n\ge 1\text{.}\) If \(G\) is a graph containing an odd cycle, what can we say about \(\chi'(G)\text{?}\)
Problem 6.2.18.
Calculate \(\chi'(K_n)\) for \(3\le n\le 7\text{.}\) Conjecture a value for \(\chi'(K_n)\) for any \(n\ge 3\text{.}\) Can you prove your conjecture?
Problem 6.2.19.
Another important class of graphs is that of the complete bipartite graphs. First, calculate \(\chi'(K_{2,2}), \chi'(K_{2,3}), \chi'(K_{3,3}), \chi'(K_{3,4})\text{,}\) and \(\chi'(K_{3,5})\text{.}\) Then, conjecture a value for \(\chi'(K_{m,n})\text{.}\) Can you prove your conjecture?
PrevTopNext