## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### MCQ and MCR
#### 2.2.1. MCQ in Java
\(degree\) is the degree of the vertex \(index\) and \(nebDeg\) is the sum of the degrees of the vertices in the neighbourhood of vertex \(index\). Given an array \(V\) of class Vertex, this can be sorted using Java's \(Arrays.sort(V)\) method in \(O(n.\log(n))\) time, and is ordered by default using the \(compareTo\) method in class Vertex. Our method forces a strict ordering of \(V\) by non-increasing degree, tie-breaking on \(index\). This ensures reproducibility of results. If we allowed the \(compareToMethod\) to deliver \(0\) when two vertices have the same degree, then \(Arrays.sort\) would break ties. If the sort method was unstable, _i.e._, it did not maintain the relative order of objects with equal keys [19], results may be unpredictable. The class MCRComparator (Listing 6) allows us to sort vertices by non-increasing degree, tie breaking on the sum of the neighbourhood degree \(nebDeg\) and then on \(index\), giving again a strict order. This is the MCR order given in [15], where MCQ uses the simple degree ordering and MCR is MCQ with tie-breaking on neighbourhood degree. Vertices can also be sorted into a minimum-width order. Given an ordered set of vertices, the width of a vertex is the number of edges that lead from that vertex to previous vertices in the order, and the width of the ordering is the maximum width of its vertices. The minimum width order (mwo) was proposed by [PERSON] [20] and also by [PERSON] and [PERSON] [21] where it was called \"smallest last\", and more recently in [16] as a _degeneracy ordering_. The method \(minWidthOrder\), lines 86 to 98 of Listing 7, sorts the array \(V\) of Vertex into an \"mwo\". The vertices of \(V\) are copied into an ArrayList \(L\) (lines 87 and 89). The while loop starting at line 90 selects the vertex in \(L\) with smallest degree (lines 91 and 92) and calls it \(v\). Vertex \(v\) is pushed onto the stack \(S\) and removed from \(L\) (line 93) and all vertices in \(L\) that are adjacent to \(v\) have their degree reduced (line 94). On termination of the while loop, vertices are popped off the stack and placed back into \(V\), giving a minimum width (smallest last) ordering. Method \(orderVertices\) (Listing 7 lines 74 to 84) is then called once, at the top of search. The array of Vertex \(V\) is created for sorting in lines 75 and 76, and the sum of the neighbourhood degrees is computed in lines 77 to 79. \(ColOrd\) is then sorted in one of three orders: \(style==1\) in non-increasing degree order, \(style==2\) in minimum width order, \(style==3\) in non-increasing degree tie-breaking on sum of neighbourhood degree. MCQ then uses the ordered candidate set \(P\) for colouring, initially in one of the initial orders, thereafter in the order resulting from \(numberSort\) and that is non-decreasing colour order. In [12] it is claimed that this is an improving order (however, no evidence was presented for this claim). In [15] [PERSON] proposes a new algorithm, MCR, where MCR is MCQ with a different initial ordering of vertices, _i.e._, MCQ with \(style==3\). #### 2.2.2 A Trace of MCQ

Figure 4 shows a cartoon and trace of MCQ over graph g10-50. Print statements were placed immediately after the call to \(expand\) (Listing 3 line 24), after the selection of a vertex \(v\) (line 31) and just before \(v\) is rejected from \(P\) and \(C\) (line 40). Each picture in the cartoon gives the corresponding line numbers in the trace immediately below. Line 0 of the trace is a print-out of the ordered array \(V\) just after line 83 in method \(orderVertices\) in Listing 7. This shows for each vertex the pair \(<index,degree>\): the first call to \(expand\) has \(P=\{3,0,4,6,1,2,5,8,9,7\}\), _i.e._, non-decreasing degree order. MCQ makes 3 calls to \(expand\) whereas MC makes 9 calls, and the MCQ colour bound cut-off in line 30 of Listing 3 is satisfied twice (Figure 4 lines 9 and 11). Figure 4: Trace of MCQ1 on graph g10–50. #### 2.2.3 Observations on MCQ

We noted above that MC can make recursive calls that immediately fail. Can this happen in MCQ?