Greedy algorithm fails to give chromatic number 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. 
 A: The standard example is the crown graph which gives $n$ instead of $2$ in bad order
A: Here is a tree $G=(V,E)$ (so it's a $2$-colorable, $2$-choosable, $1$-degenerate graph) of order $2^{n-1}$ on which the greedy algorithm, with a badly chosen ordering of the vertices, uses $n$ colors.
Let $[n]=\{1,2,\dots,n\}$.
Let $V=\{X\subseteq[n]:n\in X\}$, so $|V|=2^{n-1}$.
Let $E=\{\{X,Y\}:X,Y\in V\text{ and }Y=X\setminus\{\min X\}\}$. It's easy to see that $|E|=|V|-1$, and each vertex is connected by a path to the vertex $\{n\}$, so the graph $G=(V,E)$ is a tree.
Given a vertex ordering in which $X$ precedes $Y$ whenever $\min X\lt\min Y$, the greedy algorithm will give each vertex $X$ the color $\min X$; in particular, the vertex $\{k,n\}$ gets color $k$ for $k=1,2,\dots,n$.
Example. Let me write $v_{i_1i_2\dots i_k}$ to denote the vertex $\{i_1,i_2,\dots,i_k\}$. For $n=4$ the graph has
vertices $v_{14},v_{124},v_{134},v_{1234},v_{24},v_{234},v_{34},v_4$
and edges $v_{14}v_4,v_{124}v_{24},v_{134}v_{34},v_{1234}v_{234},v_{24}v_4,v_{234}v_{34},v_{34}v_4$.
The greedy algorithm will give color $1$ to the vertices $v_{14},v_{124},v_{134},v_{1234}$; then color $2$ to the vertices $v_{24}$ and $v_{234}$ (adjacent to $v_{124}$ and $v_{1234}$ respectively); then color $3$ to the vertex $v_{34}$ (adjacent to $v_{134}$ and $v_{234}$); and finally color $4$ to the vertex $v_4$ (adjacent to $v_{14}$, $v_{24}$, and $v_{34}$).
A: There are a lot of ways to do that, here is the first one i thought of. Suppose you have a graph $G$ with chromatic number at least two and different vertices $x$ and $y$ that always get the same color in every $\chi(G)$-coloring of $G$. Add a new vertex $z$ and the edge $zx$ to get a graph $G'$. Then $\chi(G') = \chi(G)$. Now label $G'$ so that the ordering starts with $z, y, x$. The greedy algorithm will give $z$ color 0, $y$ color 0 and $x$ color 1.  Since $x$ and $y$ got different colors, our assumption implies that any way to finish the coloring will use at least $\chi(G') + 1$ colors, in particular the greedy algorithm will.
Lots of ways to get such a $G$ with $x$ and $y$, one is take a complete graph and remove one edge. 
