A bipartite graph and an ordering of its vertices where the greedy algorithm uses at least $2014$ colours

Question

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.

Answer 1

There is a graph called the crown graph which is an excellent 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:

Answer 2

Assuming you mean the greedy algorithm with arbitrary ordering, the Wikipedia page has the solution: for $K_{n,n}$ minus a perfect matching, there is an ordering resulting in $n$ colors being used.