Re: Graph Coloring


tchow@xxxxxxxxxxxxx wrote:
In article <1169252592.272319.296370@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Proginoskes <CCHeckman@xxxxxxxxx> wrote:
Abid wrote:
1--If there are more than one pairs of nodes that donot have edges
between them , then atleast one pair will have same color.

I don't think so. The pentagon has chromatic number 3 (it requires 3
colors), and any 3-coloring (up to symmetry) looks like 12123 (going
around the cycle). If v1 and v3 are colored 1, v2 and v4 colored 2, and
v5 colored 3, then you have the two pairs (v5,v1), (v3,v2) show the
claim is false.

No, this doesn't work, because v1 and v3 have the same color.

That's not how I interpretted the problem. In my interpretation, you
choose the two non-edges first, then the coloring.

--- Christopher Heckman

.

Relevant Pages

  • Re: Graph Coloring
    ... I mean a pair of nodes and not pair of esges. ... Proginoskes wrote: ... In my interpretation, you ... --- Christopher Heckman ...
    (comp.theory)
  • Re: can I subtract 0.T from 0.0T?
    ... what my interpretation of the problem was. ... I think that Proginoskes was interpreting 0.T as the variable T with zero as ... its coefficient. ... he was saying. ...
    (sci.math)