Vertex backtrackingColoring(const Graph &g, CSet &c)
{
    Vertex k = 0;
    bool success = false;
    
    while (!success) {
        ++k;
        success = kBacktracking(g, k, c);
    }

    return k;
} /* backtrackingColoring */ 

bool kBacktracking(const Graph &g, const Color k, CSet &c)
{
    if (k < 1)
        error("kBacktracking", "Farbe %d zu klein.", k);

    /**************************************************************************
    * Initialisierungen:                                                      *
    **************************************************************************/
    const Vertex n = g.getn();
    c.resize(n);
    for (Vertex i=0; i<n; ++i)
        c[i] = 0;

    /**************************************************************************
    * Aufruf der rekursiven Untersuchung:                                     *
    **************************************************************************/
    return btcTry(g, 0, k, c);
} /* kBacktracking */ 

bool btcTry(const Graph &g, const Vertex i, const Color k, CSet &c)
{
    /**************************************************************************
    * Initialisierungen:                                                      *
    **************************************************************************/
    const Vertex n = g.getn();
    Color color = 0;
    bool q = false;

    /**************************************************************************
    * Fehler abfangen:                                                        *
    **************************************************************************/
    if (i >= n)
        error("btcTry", "Ecke i = %d ist außerhalb des zulässigen Bereiches "
            "[0, %d]", i, n-1);
    if (k < 1 || k > static_cast<Color>(n))
        error("btcTry", "Farbe k = %d ist außerhalb des zulässigen Bereiches "
            "[1, %d]", k, n);

    /**************************************************************************
    * Schleife:                                                               *
    **************************************************************************/
    while (q == false && color != k) {
        ++color;
        /*** Abbruch, falls i==0 und color>1: ***/
        if (i == 0 && color > 1)
            break;
        if (btcPossible(g, i, color, c)) {
            c[i] = color;
            if (i < n-1) {
                q = btcTry(g, i+1, k, c);
                if (!q)
                    c[i] = 0;
            }
            else
                q = true;
        }
    }

    return q;
} /* btcTry */

bool btcPossible(const Graph &g, const Vertex i, const Color color,
    const CSet &c)
{
    VSet N;
    g.getNeighbours(i, N);
    for (Vertex j=0; j<N.size(); ++j)
        if (c[N[j]] == color)
            return false;

    return true;
} /* btcPossible */