Crown graph
= Crown graph
{title2=$K_{n,n}\setminus\{a_ib_i:1\leq i\leq n\}$}
{wiki}
A crown graph is a <complete bipartite graph> with a perfect matching removed. For $n\geq2$ it has <chromatic number> two, but <greedy coloring> in the order $a_1,b_1,a_2,b_2,\ldots,a_n,b_n$ uses $n$ colors: the matched pair gets the same new color, and every subsequent pair sees all earlier colors.