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.