|
|
TOFT PROBLEM. Suppose G is a (k+1)-colorable graph which does not
contain K_(k+1). Does it follow that there are two vertices x and y
and two
k-colorable subgraphs G1 and G2, each containing x and y, such that:
(1) in any k-coloring of G1, x and y receive different colors, and
(2) in any k-coloring of G2, x and y receive the same color.
>Let G be a minimal counter example to the 4-color theorem. Then x is a
vertex of degree 5 and y is any of x's five neighbors.
To get G1, remove any edge connected to x except the edge {x y}
To get G2, remove the edge between x & y
This makes the Toft problem true for k = 4!
OK! This started out as a joke! But, I wonder!
If the Toft problem is proved to be false for k=4;
wouldn't that prove that the 4CT is true?
Regards
Bill J
|
|