Vertex Coloring Planar Graphs
- From: b92057@xxxxxxxxx
- Date: 27 Jul 2005 16:02:54 -0700
Specifically, G is a simple loopless maximal planar graph.
PA is a (theoretically) perfect vertex coloring algorithm. If Ch(G) =
4, then PA will always achieve a 4-coloring. If PA cannot achieve a
4-coloring, then
Chi(G) = 5.
PA operates on a simple principle. There is a pallete of four colors.
If possible, a vertex will be colored with a preselected color. If and
only if,
a preselected color cannot be assigned to a vertex, then that vertex
will be colored 'O'! If G has at least one 'O' vertex, then Chi(G) =
5.
Hypothesis; Every 'O' vertex in G will be adjacent to exactly four
different colors!
I suspect that some may doubt the validity of this hypothesis?
SOUND OFF!?
.
- Follow-Ups:
- Re: Vertex Coloring Planar Graphs
- From: Norm Dresner
- Re: Vertex Coloring Planar Graphs
- From: Gerry Myerson
- Re: Vertex Coloring Planar Graphs
- Prev by Date: Re: New Member
- Next by Date: Re: Hey
- Previous by thread: Recognise this?
- Next by thread: Re: Vertex Coloring Planar Graphs
- Index(es):
Relevant Pages
|
