$5.$ A $\backslash ($ k $\backslash )-$coloring of a graph $\backslash ($ G$=($V$,$ E$)\backslash )$ is a mapping $\backslash ($ f: V $\backslash$rightarrow$\backslash \{1,2,\backslash$cdots$,$ k$\backslash \}\backslash ).$ That is$,$ the mapping $\backslash ($ f $\backslash )$ associates with each node in $\backslash ($ V $\backslash )$ a number from $\backslash (1,2,\backslash$ldots$,$ k $\backslash ).$ Different nodes may map to different numbers or the same number. The restriction is that adjacent vertices $($that is$,$ vertices with an edge between them$)$ are mapped to different numbers. That is$,$ no two neighbors in $\backslash ($ G $\backslash )$ receive the same number.

We typically refer to the numbers as colors. For example, the number $"1"$ might be the color "red". Distinct numbers meant distinct colors. This usage is because the first applications of this problem were in map coloring. Consider, for example, a map of a country. Each state in the country would be a node in a graph, and nodes representing states that shared a border would have an edge between them $($be adjacent$)$ on the graph. One could then look for an $\backslash ($ f $\backslash )$ as defined above, to find a map coloring. Each number will refer to the color for the corresponding state, so that two neighboring states do not have the same color.

We will refer to the numbers as colors. Answer parts $($a$)-($e$)$ below.

$($a$)$ In parts $($i$),($ii$)$ and $($iv$),$ show that the given value of $\backslash ($ k$\_\{0\}\backslash )$ is the minimum value of $\backslash ($ k $\backslash )$ such that the graph is $\backslash ($ k $\backslash )-$colorable. $($As always, explanations are required: you should argue that the graph can be colored with $\backslash ($ k$\_\{0\}\backslash )$ colors by showing how each node would be colored, and you should also argue that it cannot be colored with fewer colors. As an example, see $($iii$),$ which is solved below$)$

i$.(2$ points$)$ The empty graph with $\backslash ($ n $\backslash )$ nodes. $\backslash ($ k$\_\{0\}=0\backslash )$

ii$.(3$ points$)$ The star with $\backslash ($ n $\backslash )$ nodes, $\backslash ($ n $\backslash$geq $2\backslash ).($A star is a graph with a single node $($the hub$)$ adjacent to all others; all nodes that are not the hub are adjacent only to the hub and no other node.$)\backslash ($ k$\_\{0\}=2\backslash )$

iii. The clique with $\backslash ($ n $\backslash )$ nodes. $($A clique is another name for the complete graph.$)\backslash ($ k$\_\{0\}=$n $\backslash )$

Solution: Each node will have a distinct color. For $\backslash ($ n $\backslash )$ nodes, there are $\backslash ($ n $\backslash )$ colors and thus we have shown that the clique with $\backslash ($ n $\backslash )$ nodes can be colored with $\backslash ($ n $\backslash )$ colors. Suppose we use fewer than $\backslash ($ n $\backslash )$ colors. Then there will be at least $2$ nodes with the same color $($by the pigeonhole principle$).$ Because the graph is a complete graph, there is an edge between each pair of nodes, and these nodes have an edge between them. By the definition of a coloring, they cannot have the same color. Hence it is not possible to color the clique with $\backslash ($ n $\backslash )$ nodes using fewer than $\backslash ($ n $\backslash )$ colors. Thus $\backslash ($ k$\_\{0\}=$n $\backslash )$ is the minimum number of colors required to color the clique with $\backslash ($ n $\backslash )$ nodes.

iv$.(5$ points$)$ A cycle with $\backslash ($ n $\backslash )$ nodes. $($A cycle is another name for what the text book refers to as a simple circuit: a trail which ends and begins at the same node and has no other repeated node.$)\backslash ($ k$\_\{0\}=2\backslash )$ if $\backslash ($ n $\backslash )$ is even and $\backslash ($ k$\_\{0\}=3\backslash )$ if $\backslash ($ n $\backslash )$ is odd.

$($b$)$ Define $\backslash (\backslash$Delta$($G$)=\backslash$max $\backslash \{$d$($v$)\backslash$mid v $\backslash$in V$($G$)\backslash \}\backslash ),$ i$.$e$.,\backslash (\backslash$Delta$($G$)\backslash )$ denotes the maximum degree of $\backslash ($ G $\backslash )$ where the degree $\backslash ($ d$($v$)\backslash )$ of $\backslash ($ v $\backslash )$ denotes the number of edges adjacent to $\backslash ($ v $\backslash ).$ Consider the following greedy algorithm to assign a color to each vertex and then answer parts $($i$)$ and $($ii$).$

For $\backslash ($ i$=1,\backslash$cdots$,$ n $\backslash )$ do

Color vertex $\backslash ($ v$\_\{$i$\}\backslash )$ using the smallest available color in $\backslash (\backslash \{1,2,\backslash$cdots$,$ k$\backslash \}\backslash ).$

i$.(10$ points$)$ Given any graph $\backslash ($ G $\backslash ),$ prove that the above greedy algorithm colors the vertices of $\backslash ($ G $\backslash )$ with at most $\backslash ($ k$=\backslash$Delta$($G$)+1\backslash )$ colors.

ii$.(10$ points$)$ Give an example of a graph $\backslash ($ G $\backslash )$ that requires $\backslash (\backslash$Delta$($G$)+1\backslash )$ colors.

$($c$)(20$ points$)$ A bipartite graph is another name for a $2-$colorable graph. Show that a graph is bipartite if and only if it contains no odd cycle.