Finding Chromatic Number w/ Brute Force Algorithm

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

I'm trying to implement this pseudocode:

Code :

---

//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 :D

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:

Code java:

---

    //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;
    }

---

http://www.javaprogrammingforums.com...algorithm.html

Duplicate post.

Can you explain the flow of your implementation. Which function calls first and next and next?
This implementation is taking us no where.
Please provide SSCCE