Produce a graph and degree sequence for which the greedy algorithm fails to give the chromatic number.
My first example is below- The first labeling uses 2 colors which is the chromatic number and the second labeling uses 3 colors, which shows that the greedy algorithm fails to give the chromatic number. The degree sequence of this graph is {3,3,2,2,1,1}.
I need to find a second example of this situation. Is there a systematic way to find another example? Is there a pattern in the degree sequence of graphs when the greedy alg. will fail to give the chromatic number? Or to find a second example will I just need to try random graphs and labelings?
*I also know that different labelings will produce different colorings when using the greedy algorithm.
Best Answer
The standard example is the crown graph which gives $n$ instead of $2$ in bad order