[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 Brooks 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 (Gv) <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.