[Solved] CSDS455 Homework 12- greedy algorithm

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.