P=NP? (polynomial graph coloring)

I came up with a polynomial bounded algorithm (exponential to be specific) for graph coloring a year or two ago. Does anyone agree/disagree with my findings? Here is my doc:

Johnathon Pandich

Polynomial time (tractable) algorithm for solving graph coloring:

Given a sequence of “colors” we will visit each node of the graph. Upon visiting that node we will check the colors of each neighbor node and set the color of the current node to the “lowest” color which is different from all neighbor nodes (all nodes are initialized to null). Continue until all nodes have been colored. The number of colors used is the minimum number of colors required.

Lowest = earliest color in the sequence

This solution is O(n^2): We must visit each node and all of its neighbors. For a fully connected graph this is n^2 iterations.

Proof of correctness:

Assume that there was 1 less color that could be used in the graph. Removing this color would require it to be replaced by another color. Because we select the lowest color not currently being used by any neighbor node, we must select a larger color (later in sequence) to replace it.

This introduces three possibilities:

1) The eliminated color still exists in the graph and it is replaced with another color that exists in the graph (no loss in colors)

2) The eliminated color no longer exists in the graph and it is replaced with another color that did not exist in the graph (no loss in colors)

3) The eliminated color still exists in the graph and it is replaced with another that did not exist in the graph (color gain)

None of these possibilities reduce the number of colors required.

It is impossible that the eliminated color no longer exists in the graph and it is replaced with another color that does exist in the graph (loss of a color). This is because every node is colored with the lowest possible color in the sequence, for another higher color to exist in the graph, it must be either:

1) connected another node of this sequence number (meaning this a node of this color still exists in the graph)

OR

2) connected to this node (meaning we can not select it and thus must choose another higher color)
- A higher color will have the same issue

It is there for impossible to color the graph with fewer colors. This solves the NP-Complete problem of graph coloring in polynomial time.
Therefore NP=P

… In code we could keep track of the color sequence in a bit map .. traversing this bit map for every node to select the smallest color in the sequence would add at most n to the complexity O(n^2 + n) = O(n^2)

Quote:

---

Originally Posted by NinjaJohn

Given a sequence of “colors” we will visit each node of the graph. Upon visiting that node we will check the colors of each neighbor node and set the color of the current node to the “lowest” color which is different from all neighbor nodes (all nodes are initialized to null). Continue until all nodes have been colored. The number of colors used is the minimum number of colors required.

---

This sounds like greedy colouring, which apparently does "not in general use the minimum number of colors possible", hence it would be an incorrect algorithm here.

correction:

… In code we could keep track of the color sequence in a bit map .. traversing this bit map for every node to select the lowest color in the sequence would add at most n * t to the complexity, t being the map traversal cost (guaranteed to be <= n) O(n^2 + n^2) = O(n^2)

Thanks for the response laserlight! .. From what I have seen, It appears that minimum colors are not guaranteed when we have multiple "starting nodes", forcing additional color constraints. My statements above assume that we are traversing from the current node to an uncolored node connected to a colored node. To enforce this assumption I will place an additional restriction on graph traversal:

To ensure that every node is colored and that there is a single "color sprawl" per set of connected nodes, we will place each uncolored neighbor node in a queue and analyze them in order. As additional uncolored nodes are found, they are also placed in the queue. This process can be repeated for each set of connected nodes.

color sprawl - a set of colored nodes that are directly or indirectly connected.

It is important to have a single color sprawl to prevent multiple color sets from conflicting on a single node, thus imposing additional rules. This could result in more than the minimum number colors being used.

correction: color sprawl - a set of colored nodes that are directly or indirectly connected via other colored nodes.