Approximate coloring algorithm

MaxClique uses an approximate coloring algorithm^[2] to obtain set of color classes C. In the approximate coloring algorithm, vertices are colored one by one in the same order as they appear in a set of candidate vertices R, so that if the next vertex p is non-adjacent to all vertices in the same color class, it is added to this class, and if p is adjacent to at least one vertex in every one of existing color classes, it is put into a new color class.

The MaxClique algorithm returns vertices R ordered by their colors. Vertices ${\displaystyle v\in R}$ with colors ${\displaystyle C(v)<{|Q_{max}|}-{|Q|}+1}$ are never added to the current clique Q. Therefore, sorting those vertices by color is of no use to MaxClique algorithm.

ColorSort

The ColorSort algorithm improves on the approximate coloring algorithm by taking into consideration the above observation. Each vertex is assigned to a color class ${\displaystyle C_{k}}$. If ${\displaystyle k<{|Q_{max}|}-{|Q|}+1}$, the vertex is moved to the set R (behind the last vertex in R). If ${\displaystyle k\geq {|Q_{max}|}-{|Q|}+1}$, then the vertex stays in ${\displaystyle C_{k}}$ and is not moved to R. At the end, all of the vertices remaining in ${\displaystyle C_{k}}$ (where ${\displaystyle k\geq {|Q_{max}|}-{|Q|}+1}$) are added to the back of R as they appear in each ${\displaystyle C_{k}}$ and in increasing order with respect to index ${\displaystyle k}$. In the ColorSort algorithm, only these vertices are assigned colors ${\displaystyle C(v)=k}$.

The pseudocode of the ColorSort algorithm is:^[1]

procedure ColorSort(R, C) is
    max_no := 1;
    kmin := |Qmax| − |Q| + 1;
    if kmin ≤ 0 then kmin := 1;
    j := 0;
    C1 := Ø; C2 := Ø;

    for i := 0 to |R| − 1 do
        p := R[i]; {the i-th vertex in R}
        k := 1;
        while Ck ⋂ Γ(p) ≠ Ø do
            k := k+1;
        if k > max_no then
            max_no := k;
            Cmax_no+1 := Ø;
        end if
        Ck := Ck ⋃ {p};
        if k < kmin then
            R[j] := R[i];
            j := j+1;
        end if
    end for

    C[j−1] := 0;

    for k := kmin to max_no do
        for i := 1 to |Ck| do
            R[j] := Ck[i];
            C[j] := k;
            j := j+1;
        end for
    end for

Example

The graph above can be described as a candidate set of vertices R = {7⁽⁵⁾, 1⁽⁴⁾, 4⁽⁴⁾, 2⁽³⁾, 3⁽³⁾, 6⁽³⁾, 5⁽²⁾, 8⁽²⁾}, and used as input for both the approximate coloring algorithm and the ColorSort algorithm. Either algorithm can be used to construct the following table:

The approximate coloring algorithm returns set of vertices R = {7⁽⁵⁾, 5⁽²⁾, 1⁽⁴⁾, 6⁽³⁾, 8⁽²⁾, 4⁽⁴⁾, 2⁽³⁾, 3⁽³⁾} and its corresponding set of color classes C = {1,1,2,2,2,3,3,3}. The ColorSort algorithm returns set of vertices R = {7⁽⁵⁾, 1⁽⁴⁾, 6⁽³⁾, 5⁽²⁾, 8⁽²⁾, 4⁽⁴⁾, 2⁽³⁾, 3⁽³⁾} and its corresponding set of color classes C = {–,–,–,–,–,3,3,3}, where – represents unknown color class with k < 3.