Re: Graph Coloring

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.

Abid's claim can be restated as: if a *minimum* coloring of a graph is
a *legal* coloring of its complement, then the graph is complete.

I don't immediately see a proof or a counterexample.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Re: The Lazy Persons Guide to Proving the Four Color Theorem
    ... In fact, the 4CT is false if there is a graph G with Chi> 4, ... For every possible 4-coloring of, there can be no proper ... rest of G, or equivalently, if C is a coloring of G, then Chas four ... You assumed we can recolor just v_a; ...
    (sci.math)
  • Re: Four Color Theorem
    ... My proof is based on the assumption that the following graph is not 4-chroma. ... Without the internal chord ... All you have done is made one coloring fail to work; ... that no minimal counterexample of the 4CT contains K4. ...
    (sci.math)
  • Re: Four Color Theorem
    ... My proof is based on the assumption that the following graph is not 4-chroma. ... Without the internal chord ... All you have done is made one coloring fail to work; ... that no minimal counterexample of the 4CT contains K4. ...
    (sci.math)
  • Re: Four Color Theorem
    ... My proof is based on the assumption that the following graph is not 4-chroma. ... Without the internal chord ... All you have done is made one coloring fail to work; ... You can't assume there is only one coloring of G-v. ...
    (sci.math)
  • Re: Four Color Theorem
    ... My proof is based on the assumption that the following graph is not 4-chroma. ... Without the internal chord ... All you have done is made one coloring fail to work; ... You can't assume there is only one coloring of G-v. ...
    (sci.math)