Re: Graph Coloring

In article <45b24e3d$0$562$b45e6eb0@xxxxxxxxxxxxxxxxxxxxxxxxx>, I wrote:
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.

This is trivial to prove. Given any two vertices, they are adjacent
either in the original graph or in its complement. Since the coloring
is legal both for the graph and its complement, it follows that the two
vertices must receive different colors. Thus all the vertices must have
distinct colors, and the only way that this can be a minimum coloring is
if the graph is complete.
--
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)