Graph Coloring with the least collision

From: Bilal Sallakh (afkar_at_mail2world.com)
Date: 01/20/04 

Date: 20 Jan 2004 08:26:18 -0800

Finding the chromatic number of a graph is a famous NP-Complete
problem. Even

If we want to color an arbitrary undirected graph G with a fixed
number of colors, say k, wheather G is k-colorable or not.

How can we color G with the minimum number of collisions (violations
to the coloring criterion)?

Someone told me that the proble can be formulated as a linear program.
How?

Sure if it is, then the complexity is polynomial.

Another question is:
If a graph is k-colorable, then is the problem of finding a k-coloring
for the graph, NP-Complete?

Relevant Pages

  • Re: Graph Coloring with the least collision
    ... Or when you don't know for which k a graph is k-coloring, ... the input graph is k colourable), then you could apply that algorithm to ... If the graph was not k-colourable, the colouring will obviously ...
    (comp.theory)
  • TOFT PROBLEM
    ... TOFT PROBLEM. ... Suppose G is a -colorable graph which does not ... in any k-coloring of G2, x and y receive the same color. ... analyzing the ...
    (sci.math)