Re: Some Thoughts on the Four Color Theorem

On Jul 14, 9:28 pm, Proginoskes <CCHeck...@xxxxxxxxx> wrote:
On Jul 14, 4:03 pm, bill <b92...@xxxxxxxxx> wrote:



On Jul 13, 9:42 pm, Proginoskes <CCHeck...@xxxxxxxxx> wrote:

On Jul 13, 3:56 pm, bill <b92...@xxxxxxxxx> wrote:

On Jul 11, 9:34 pm, Proginoskes <CCHeck...@xxxxxxxxx> wrote:

On Jul 11, 9:12 pm, bill <b92...@xxxxxxxxx> wrote:

On Jul 7, 8:08 pm, Proginoskes <CCHeck...@xxxxxxxxx> wrote:

On Jul 7, 12:44 pm, bill <b92...@xxxxxxxxx> wrote:

On Jul 6, 8:14 pm, Proginoskes <CCHeck...@xxxxxxxxx> wrote:

On Jul 6, 1:28 pm, bill <b92...@xxxxxxxxx> wrote:

On Jul 4, 4:12 pm, Proginoskes <CCHeck...@xxxxxxxxx> wrote:

On Jul 4, 2:16 pm, bill <b92...@xxxxxxxxx> wrote:

1. The minimal counter example (MCE) to the 4CT

The vertex-coloring version of the 4CT.

is a simple
loopless triangulation such that every vertex has degree
equal 5 or greater.

2. The dual of the MCE is a triangle-free cubic planar graph.

There are no triangular _faces_ in a triangulation with
minimum degree>= 5, but there might be triangles in a
planar graph which are not planar.

What are you trying to say?

You might have a triangle which has a vertex inside of it and a vertex
outside of it, sometimes called a "separating triangle". Seehttp://math.asu.edu/~checkman/septri.jpgforanexample.

However, this is not true for a MCE. (It takes a little bit of
work, though, which I'll let bill do.)

Exactly what "is not true for a MCE"?

The statement "G has not facial triangles and a separating triangle".

I am working on the problem! But right now, I think that a cubic with
a separating triangle must also have a bridge?. If, this is true, then
the dual cannot be a simple loopless triangulation!

Yes. Last night after posting I realized that this is true, and the
proof's not that bad.

If uvw is a separating triangle, and u', v', w' are the neighbors of
u, v, and w not in the triangle, then we may assume that u' is inside
the triangle and v' and w' are outside of it (using symmetry and the
fact that a separating triangle is not facial). Then uu' is a cut-edge
(bridge).

3 The MCE must be the dual of a triangle-free cubic planar graph!

This is the same thing you said in (2.)

4 Every triangle-less cubic planar graph is 3 edge colorable.

You can eliminate "triangle-less" here, but you need to put in "bridge-
free" (or 2-connected) here. If every triangle-free 2-connected cubic
planar graph is 3-edge colorable, then every 2-connected cubic planar
graph is 3-edge colorable. Again, I'll leave this as an exercise for
bill, hinting to do it by induction on the number of triangles in the
graph.

5 The 4CT is true if statement 4 above is true!

This is a statement of the form (False => something), so is vacuuously
true. After adding the 2-connected condition, it becomes equivalent.

FWIW. The dual of the MCE has no 3-cycles nor
4-cycles; only 5-cycles and 6-cycles. No cycles
larger than 6?

What if you had a vertex of degree 7 in your MCE? If you can't
definitely rule it out, it must be possible.

If the dual has a 3-cycle, then
he MCE would have a vertex of degree 3; if the
dual has a 4-cycle, then the MCE would have a degree 4 vertex.

Not necessarily. The proof of no separating 3-cycles above doesn't go
through: If you have a separating 4-cycle C = uvwx, and you let u',
v', w', x' be the neighbors of u,v,w,x not in C, then you can have u'
and w' inside of C and v' and x' outside of C, and not have a bridge.

(As of about 2000, Robin Thomas hadn't heard about a proof that a MCE
doesn't have a separating 4-cycle and would like to have found one,
since it simplifies the new proof of the 4CT.)

Once again, I forgot that bill is looking at the dual of a MCE. My
comments above apply to the vertex-coloring of the original graph.

Seehttp://www.geocities.com/b92057/S4C.

Figure 1 is a simple cubic with a separating 4-cycle. Note that faces
A & B have edges {1 5} and {4 7} in common. This translates to parallel
edges in the dual. If you combine the two parallel edges in to a single
edge; then the dual will not be fully triangulated. Faces D & E present
a similar problem. Of course an isolated 4-cycle becomes a 4 degree
vertex in the triangulation.

A question. How do the edge colors predict the face colors?

Found via Google: "Many people know of the Four Color Theorem. Less
known is the Edge Coloring Theorem. Tait, 1880: The edges of a
bridgeless cubic planar graph are three-colorable. A bridged graph ()
is not three-colorable. A cubic graph is one where each vertex has
three edges. Three-colorable means that no two edges of the same color
touch. The proof is easy. First, four-color the map. This can be done
via the Four Color Theorem. Next, color cyan any edge between red and
blue regions, or between yellow and green regions. Color orange any
edge between red and green regions, or between blue and yellow
regions. Color magenta any edge between red and yellow regions, or
between blue and green regions. That's it -- you now have a 3-colored
edge coloring." Source:http://www.mathpuzzle.com/4Dec2001.htm

Let a 5-cycle have edge colors R, G, R, Y, B in clockwise order.

Let the colors of the 5-cycle be R, G, R, G & B in clockwise order,
and the overall graph is 3 edge colorable. How does this guarantee
that the faces are 4 colorable?

There's a theorem here. (Tait proved that this scheme works.) But just
follow what I gave you. Hint: You can color the pentagon any color you
want, to start off with. Then the colors for the rest of the faces are
determined.

Here's a more explict description of the coloring:

(1) Any R edge must be between two faces colored 1 and 2,
or between two faces colored 3 and 4.
(2) Any G edge must be between two faces colored 1 and 3,
or between two faces colored 2 and 4.
(3) Any B edge must be between two faces colored 1 and 4,
or between two faces colored 2 and 3.

If your pentagon is colored 1, then the neighboring faces which are on
the opposite side of a R edge are colored 2. Neighboring faces (of the
pentagon) which are on the opposite side of a G edge are colored 3.
Etc.

--- Christopher Heckman

That's four colors on the edges, not three. But maybe you're working
on a MCE, whose dual cannot be 3-edge colored.

The Y edge is the only
Y edge in the graph. Why can't the face of the pentagon be colored R or G
or B or Y? Assuming that all other faces can be colored with one of those
4 colors!

What about the 'bridged' cubic?

Is it planar? If NO, then why? If YES, then is it 4 face colorable?

If NO, then why? If YES, then why isn't it 3 edge colorable?

---Bill J

.

Relevant Pages