Thread: Finding Chromatic Number of a Simple Graph w/ Brute Force Algorithm

Hello, I'm new to the forums here and really in a bind.

I'm trying to implement this pseudocode:

//graph G, vertices n, vertices are numbered 0, 1 . . n-1
//G is stored in adjacency list or adjacency matrix p
//colors are stored in array q
//q[i] has color of vertex i, initially all 0
 
//colors G using minimum number of colors, returns chromatic number
int color()
{
     for(i = 1 to n)
     {
          //if G can be colored using i colors starting at vertex 0
          if(color(0,i))
          {
               chromatic number is i, return it
          }
     }
}
 
//colors G using m colors starting at vertex v
boolean color(v,m)
{
     if(v exceeds n - 1)
          all vertices have been colored, success
     else
     {
          for(i = 1 to m)
          {
               assign color i to vertex v
 
               check whether colors of v and its neighbors conflict
 
               if(colors do not conflict)
               {
                    color the rest of G using m colors starting at vertex v+1
                    done by recursive call color(v+1,m)
 
                    if(the rest of G can be colored)
                         all vertices have been colored, success
               }
          }
          assign color 0 to vertex v and fail, this happens when
          none of the m colors can be assigned to vertex v
     }
}
 
//in color() method, chromatic numbers can be tried in ascending order
//(i = 1 to n) or descending order (i = n to 1), and both orders can be
//used to find a range of possible values of the chromatic number

I thought that my implementation was working because I tested it with a small sample graph and got the correct output. However, when testing with large graphs this algorithm was solving them in seconds, but is supposed to have a runtime of hours. I think that I may be missing a recursive call somewhere, or maybe am breaking out of the function too early somehow.

Anyway, here is my implementation of the above pseudocode. I am sincerely grateful for any help that you guys can provide. Thanks

Explanation of my variables:

this.size = the number of vertices in the graph
this.vertexColors = 1 dimensional array with this.size number of elements. holds
a chromatic number for each vertex
this.inputMatrix = a this.size x this.size element 2d matrix. only holds 0s and 1s.
the 0s represent no line between vertices, and a 1 represents a line

Example:
vertex
1 2 3 4

vertex 1 0 0 0 0
vertex 2 0 0 1 0
vertex 3 0 0 0 0
vertex 4 0 0 0 0

This represents a line connecting vertex 2 and 3. A 1 in row 3, column 2 would mean the same thing. It is also not necessary to have a 1 in both of those to represent the line, just one will work.

My implementation:

    //colors graph using minimum number of colors, returns chromatic number
    public int colorAscending()
    {
        for(int i = 1; i < this.size + 1; i++)
        {
            //if graph can be colored using i colors starting at
            //vertex 0
            if(colorAscending(0,i))
            {
                return i;
            }
        }
        //syntactically necessary return statement. should never get here
        return 0;
    }
 
 
 
 
 
 
    //v = current vertex, m = number of colors to try
    //colors graph using m colors starting at vertex v
    private boolean colorAscending(int v, int m)
    {
        if(v > this.size - 1)
        {
            //all vertices have been colored, success
            return true;
        }
        else
        {
            for(int i = 1; i < m+1; i++)
            {
                //assign color i to vertex v
                this.vertexColors[v] = i;
 
                //check whether colors of v and its neighbors conflict
                if(!checkForConflict(v))
                {
                    if(colorAscending(v+1,m))
                    {
                        return true;
                    }
                    else
                    {
                        return false;
                    }
                }
            }
            //assign color 0 to vertex v and fail
            this.vertexColors[v] = 0;
            return false;
        }
    }
 
 
 
 
 
    //checks if vertices adjacent to v have the same color or not
    private boolean checkForConflict(int vertex)
    {
        for(int i = 0; i < this.size; i++)
        {
            if((this.inputMatrix[i][vertex] == 1) &&
                    (this.vertexColors[i] == this.vertexColors[vertex]))
            {
                return true;
            }
        }
        return false;
    }

Sorry bud, I'll keep from double-posting like that in the future. Just a bit frustrated because I've been staring at this code trying to figure it out all day.

Meanwhile, any help anyone? You don't need knowledge of the algorithm exactly. I'm just looking for some extra pairs of eyes to see if I am somehow deviating from the pseudocode there in a bad way. Thanks in advance everyone!