CSDS 455: Applied Graph Theory
Homework 12
The next subject we will cover is graph coloring for general graphs. For your reading this weekend, take a
look at Brook’s Theorem and look up the greedy algorithm for coloring a graph.
Problem 1: Show that every graph G has a vertex ordering for which the greedy algorithm uses only χ(G)
colors.
Problem 2: For every n > 1, find a bipartite graph on 2n vertices, ordered in such a way that the greedy
algorithm uses n rather than 2 colors.
Problem 3: A k chromatic graph is called critically k-chromatic, or just critical, if χ(G − v) < k for every
v ∈ V (G). Show that every k-chromatic graph has a critical k-chromatic induced subgraph and that any
such subgraph has minimum degree at least k − 1.
Problem 4: Let ∆(G) be the maximum degree of G. Prove that for any ∆ ≥ 4, there exists a graph G
with χ(G) ≥ ∆(G) − 1 but G does not contain a ∆(G) − 1 clique.
