Find a bipartite graph and an ordering of its vertices so that the greedy algorithm uses at least 2014 colors.
I am unsure whether I just need to draw a graph (not sure how I would do it with two subgraphs seems tedious) or if there is a trick I am not seeing.
Best Answer
There is a graph called the crown graph which is an excelent counterexample. Consider the bipartite graph with vertex set $\{v_1,v_2,\dots ,v_{2014},u_1,u_2,\dots ,u_{2014}\}$ where two vertices are adjacent if they have different letters and different numbers, now order them in the following manner: $v_1,u_1,v_2,u_2,\dots ,v_{2014},u_{2014}$. the algorithm will assign the same color to $v_1$ and $u_1$ since they are not adjacent, it will then have to assign a different color to $v_2$ since it is adjacent to $u_1$ and it will then assign the same color to $u_2$ which will cause it to use yet another color for $v_3$ since it is adjacent to $u_1$ and $u_2$ however it will give this same color to $u_3$ and it will proceed like this until it has used $2014$ colors.
Here is an image from wikipedia: