Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: A New Graph Coloring Conjecture.
Replies: 42   Last Post: Jul 2, 2013 4:08 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
b92057@yahoo.com

Posts: 1,183
Registered: 4/18/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 27, 2013 4:45 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Thursday, June 27, 2013 1:34:31 AM UTC-7, quasi wrote:
> bill wrote:
>

> >quasi wrote:
>
> >> Bill wrote:
>
> >> >
>
> >> >I took a second look at your graph information. When I say
>
> >> >those virtually invisible dots, I had enough to analyze the
>
> >> >graoh for FFS. I found one. It is vetices 1 7 8 9. Not a K4.
>
> >>
>
> >> Right, the subgraph determined by vertices 1,7,8,9 is not a
>
> >> K4, but it's not what you call a forced 4-set, since it's
>
> >> 3-colorable.
>
> >>
>
> >> As I previously noted, if a graph with 4 vertices is not
>
> >> 3-colorable, then it must be complete (that is, it must be
>
> >> isomorphic to K4).
>
> > 1 4 4 7
>
> > 7 . 2 4 5 7
>
> > |\ . 2 5 6 7
>
> > = 3 . | \ 8 3 4 8 5
>
> > | . | \ ./| 3 5 8 6
>
> > | 0 . \/ | 3 6 9 4
>
> > | . | . \ | 4 5
>
> > | . | /.\| 4 6
>
> > 2-------|--/---9 5 6
>
> > . | / .
>
> > . |/ .
>
> > 1
>
> >
>
> >ANALYSIS;
>
> >
>
> > 1. Arbitrarily assign colors initial
>
> >colors; 4=B 5=C 6=D
>
> >
>
> > 2. This forces 3=A & 7=A.
>
> >
>
> > 3. 8=B is forced by 7=A 5=C & 6=D
>
> >
>
> > 4. 9=C is forced by 6=D, 7=A & 8=B
>
>
>
> You're OK up to step 4.
>
>
>

> > 5. 1=D is forced by 7=A, 8=B & 9=C
>
>
>
>
>
>
>
> 1 is adjacent to 8,9,0,2,3,4
>

Revise 5. to read,

1=D is forced by 3=A, 8=B & 9=C
>
>
>

> >A classic example of what I call a "forced
>
> >four subset".
>
>
>
> Four colors are already forced at step 2. If all you want to
>
> show is that at least 4 colors are needed, you can stop right
>
> there.
>
>
>
> However if you continue past step 4 in the following way,
>
> you'll see you need a 5th color -- 4 colors is not enough.
>
>
>
> 5. 0=D is forced by 7=A, 8=B & 9=C
>
>
>
> 6. 1=E is forced by 8=B, 9=C, 0=D & 3=A


I was thinking 1=D then 0=E.
>
>
>
> To explain the last step, note that vertex 1 is adjacent to
>
> vertices 8,9,0, so vertex 1 can't have one of the colors B,C,D.
>
> But vertex 1 is also adjacent to vertex 3, which was forced
>
> earlier in the analysis (step 2) to have color A, hence vertex 1
>
> can't have color A either. Thus, vertex 1 can't have any of the
>
> colors A,B,C,D.
>
>
>
> It follows that the graph is not 4-colorable.
>
>
>
> In any case, it's now _really_ unclear what you mean by a forced
>
> 4-set. What's needed is a rigorous mathematical definition. Are
>
> you up to the task of providing such a definition using standard
>
> graph-theoretic terminology?
>

Once the concept of forced 4-set is clarified to the point where
>
> at least some of us understand what you're talking about, can
>
> you then state in a clear way what you're conjecturing with
>
> regard to 4-colorability or non-4-colorability?
>
>
>
> quasi


I don't have a mathematical definition. But here's one
in plain lsnguage.

Forced Five Set: A connected subset of five vertices
(not isomorphicc to K5), that cannot be 4-colored.
Not a stretch. I had always intended that a FFS or F4S implied a forced five set (F5S}.

In the example above, vertices 0 1 7 8 9 constitute an F5S.

As to 4-colorability, I present the following conjecture.

Conjecture: Every non 4-color planar graph contains at least one subset isomorphic to F5S.

bill


Date Subject Author
6/18/13
Read A New Graph Coloring Conjecture.
b92057@yahoo.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/18/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/18/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/19/13
Read Re: A New Graph Coloring Conjecture.
trj
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/22/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/23/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/25/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/25/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/25/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/26/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/26/13
Read Re: A New Graph Coloring Conjecture.
Brian Q. Hutchings
6/27/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/27/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/27/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/27/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/27/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/28/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/28/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/28/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/29/13
Read Re: A New Graph Coloring Conjecture.
quasi
7/1/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
7/2/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/19/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/19/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
Tucsondrew@me.com
6/21/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/21/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/22/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/23/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/19/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
quasi
6/20/13
Read Re: A New Graph Coloring Conjecture.
Butch Malahide
6/20/13
Read Re: A New Graph Coloring Conjecture.
Butch Malahide
6/19/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com
6/20/13
Read Re: A New Graph Coloring Conjecture.
b92057@yahoo.com

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.