Graph Coloring · Hard problem

Let $G$ have vertices $a_1,\dots,a_4,b_1,\dots,b_4$, with $a_i$ adjacent to $b_j$ exactly when $i\ne j$ ($K_{4,4}$ minus a perfect matching). Greedily color the vertices in the order $a_1,b_1,a_2,b_2,a_3,b_3,a_4,b_4$, giving each vertex the smallest color not used by an already-colored neighbor. How many colors does this greedy run use?