Question

a. Explain how backtracking can be used to determine whether a simple graph can be colored using \(n\) colors.

b. Show, with an example, how backtracking can be used to show that a graph with a chromatic number equal to \({\bf{4}}\) cannot be colored with three colors, but can be colored with four colors.

Short answer

Select a first vertex and color it with "color \({\bf{1}}\)".

Select the next vertex. If the vertex does not have \({\bf{a}}\) as adjacent vertex, then color it with "color \({\bf{1}}\) ", else color it with "color \(2\) ".Repeatedly check every vertex that still needs to be colored and check if it can be colored with color \({\bf{1}}\) , color \(2\), color \(3\) and so on. If the vertex is adjacent to a vertex with "color \(i\) ", then the vertex cannot be color with "color \(i\) ". If not, then color it with color \(i\) (for the first \(i \in \{ 1,2, \ldots ,n\} \)) for which it is true).

Step-by-step solution

Definition

The chromatic number is the least number of colors needed for a coloring of the vertices of the graph.

Select a first vertex and color it with "color \({\bf{1}}\)".Select the next vertex. If the vertex does not have \({\bf{a}}\) as adjacent vertex, then color it with "color \({\bf{1}}\) ", else color it with "color \(2\) ".Repeatedly check every vertex that still needs to be colored and check if it can be colored with color \({\bf{1}}\), color \(2\), color \(3\) and so on. the first \(i \in \{ 1,2, \ldots ,n\} \) for which it is true).

Obtaining the graph for chromatic color

I will use a graph with \({\bf{4}}\) vertices \(a,b,c,d\) and an edge between every pair of vertices.

Chromatic color

One first selects vertex \({\bf{a}}\) and color it with the first color "Purple".Next, we select vertex \({\bf{b}}\). Since it is connected to \({\bf{a}}\), we cannot color it with the first color and thus we need to color \({\bf{b}}\) with a second color "Red".Next, we select vertex \({\bf{c}}\). Since it is connected to \({\bf{a}}\), one cannot color it with the first color. Since it is connected to \({\bf{b}}\), we cannot color it with the second color and thus we need to color \({\bf{c}}\) with a third color "Green". Next, we select vertex \({\bf{d}}\). Since it is connected to \({\bf{a}}\), we cannot color it with the first color. Since it is connected to \({\bf{b}}\), we cannot color it with the second color. Since it is connected to \({\bf{c}}\), we cannot color it with the third color and thus we need to color \({\bf{d}}\) with a fourth color "Orange".

One then note that we couldn't color the vertices with three colors and required exactly \({\bf{4}}\) colors, which implies that the chromatic number is \({\bf{4}}\).