Remember that these problems are for individual work only (no collaboration).
Textbook, Problem 12.3
Textbook, Problem 12.7
Textbook, Problem 12.16
This question deals with the problem of extending graph colorings of a subgraph to a coloring of an entire graph. Given a graph G, an “induced subgraph” H of G is defined by taking a subset of G’s vertices (so V(H) ⊆ V(G)), and then H’s edges are the set of all edges that are incident to two vertices in V(H):
E(H) = {⟨u − v⟩ | u, v ∈ V(H)}.
You can think of this as “pulling out” a subset of vertices from G and all of the edges that come with those vertices.
We say that a coloring of H is extended to a coloring of G if every vertex in H retains the color of its original coloring, and all the vertices in V(G) − V(H) are assigned colors such that the result is a valid coloring of G.
Prove that for any H and G, any valid coloring of H can be extended to a valid coloring of G (the number of colors used for G is not important).
Let G and H be such that |V(G) − V(H)| = 1 (i.e., G is one vertex larger than H) and χ(G) = χ(H). Prove that there exists a χ(H)-coloring of H that can be extended to a χ(G)-coloring of G.
Let G and H be such that |V(G) − V(H)| = 1 (i.e., G is one vertex larger than H) and χ(G) = χ(H) + 1, so that any coloring of G requires one more color than is necessary to color H. Prove that any χ(H)-coloring of H can be extended to a χ(G)-coloring of G.
Let G and H be such that |V(G) − V(H)| = 2 (i.e., G is two vertices larger than H) and χ(G) = χ(H) + 1, so that any coloring of G requires one more color than is necessary to color H. Show that there exist graphs G and H that satisfy these conditions, but for which no χ(H)-coloring of H can be extended to a χ(G)-coloring of G.
If we can always extend a coloring when adding a single new vertex (as established in parts b and c), why can’t we just extend a coloring with two new vertices by adding the vertices one at a time? Since the chromatic number goes up by only one over the two vertex additions, one addition must keep the chromatic number the same and one must increase the chromatic number by one. Why can’t we apply part b for the first addition and part c for the second addition, extending the coloring each time, so that we end up extending the original coloring over the two vertex additions? (Hint: if you gave a good counter-example in part d, try working this through the “add one vertex at a time” argument and see where it fails.)