Re: Coloring a graph with exact N colors


tzuchien <dot> chiu <at> gmail <dot> com wrote:
> I'm looking for an algorithm to color a graph with exact N colors,
> usually N is larger than the chromatic number of the graph. However,
> the number of occurrences of each color is expected to be the same, in
> probability. That is, each color is used as roughly many times to color
> the graph.
>
> In the othwords, the vertices are partitioned into N indepdent sets,
> and the number of vertices in each indepedent set shoudl be roughly the
> same.

You could try coloring vertices at random. If the number of colors is
larger than the number of edges, it shouldn't take too many tries.

--- Christopher Heckman

.

Relevant Pages

  • Coloring a graph with exact N colors
    ... I'm looking for an algorithm to color a graph with exact N colors, ... and the number of vertices in each indepedent set shoudl be ...
    (comp.compilers)
  • Minimum Dominating Set
    ... Is there an algorithm for finding Minimum Dominating Set of a graph? ... This algorithm should find the exact answer, not the approximation one. ...
    (comp.theory)
  • Re: Shortish paths
    ... For how many nodes and how many edges will the actual algorithm run ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • Re: Standard graph API?
    ... isomorphism graph library. ... It's pretty uniformly agreed that there is no standard graph ... the algorithm can't be specialized for the graph at ... My thought is to use some sort of templating system. ...
    (comp.lang.python)
  • Difference between two systems of DAGs
    ... I am looking for a graph algorithm, ... carry no label or other information except direction. ... edit operations are to change the label of a vertex or the ...
    (comp.theory)