Re: 4CT
- From: "Proginoskes" <CCHeckman@xxxxxxxxx>
- Date: 22 Feb 2006 22:57:05 -0800
bill wrote:
Let graph G be a minimal counter-example to the 4CT. If G has more
than 5 vertices, there will be at least two vertices with the same
color. Let there vertices be O_1 and O_2. If O_1 is removed, then O_2
can be recolored to say R. If O_2 is removed and O_1 can be recolored,
then Chi(G) = 4. If O_1 cannot be recolored, then G is not minimal.
In fact, if you have a minimal counterexample G, deleting ANY vertex
results in a 4-colorable graph, by definition.
I think that it has been shown that a mce to the 4CT must have at least
90 vertices.
(!!!)
Walter Stromquist proved that any counterexample to the 4CT has at
least 52 vertices, in a doctoral dissertation he got accepted just
before A & H announced their results.
Then at least 18 vertices will have the same color. The
task of removing each of the 18 vertices in turn and reassigning the
remaining 17 seems impossible. But this is necessary if G is minimal. [...]
Things really aren't that bad ... There is a 5-coloring of G which uses
some color only once. Proof: Delete a vertex v, color the smaller graph
with 4 colors, then color v with a fifth color.
--- Christopher Heckman
.
- References:
- 4CT
- From: bill
- 4CT
- Prev by Date: L(G) and L(G')
- Next by Date: How do I simplify this function x?
- Previous by thread: 4CT
- Next by thread: Re: 4CT
- Index(es):
Relevant Pages
|
