Re: Graph Coloring

Hi Chris:

When I say pair, I mean a pair of nodes and not pair of esges. I think
claim is true for a pair of nodes. In your example <v5,v1> and <v3,v2>
are two pairs of nodes with same color.

Abid

Proginoskes wrote:
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
    ... Proginoskes wrote: ... then atleast one pair will have same color. ... The pentagon has chromatic number 3 (it requires 3 ... In my interpretation, you ...
    (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)
  • Re: Properties of Numbers
    ... Proginoskes wrote: ... --- Christopher Heckman ... "A triangular number which is the product of two consecutive triangular ... (The last two are based on an AMM problem that was "leaked" to Usenet ...
    (sci.math)
  • Re: Difficult question
    ... Proginoskes wrote: ... has no solutions for odd x and y. ... --- Christopher Heckman ... The former replies make it likely that he was asking a question posed in the german competition "bundeswettbewerb mathematik" ...
    (sci.math)
  • Re: prove it if you can
    ... Gerry Myerson wrote: ... >> Proginoskes wrote: ... --- Christopher Heckman ... Prev by Date: ...
    (sci.math)