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 ]
quasi

Posts: 10,202
Registered: 7/15/05
Re: A New Graph Coloring Conjecture.
Posted: Jul 2, 2013 4:08 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

bill wrote:
>quasi wrote:
>>bill wrote:
>>>quasi wrote:
>>>>
>>>> If you can't define forced sets in a way that others can
>>>> understand, there's not much chance that anyone would be
>>>> able to follow a proposed proof of yours of the 4CT.

>>>
>>>Can you accept this definition?
>>>
>>>Consider;
>>>
>>>Impasse. A difficulty encountered in the attempted
>>> four coloring of a graph.
>>>
>>>Type I " An impasse that is created by the presence of a
>>>vertex adjacent to four other vertices, each of which has an
>>>assigned color that is different from the assigned color any
>>>of the three other vertices".
>>>
>>>Type II "All other impasses."

>>
>>No, I don't view that as an acceptable definition.
>>
>>It appears your concept of a forced 5-set in a graph G is a
>>set of 5 vertices, S = {a,b,c,d,e} say, such that
>>
>>(1) Not all vertices of S are adjacent.
>>
>>(2) One of the vertices of S, e say, is adjacent to the other 4.
>>
>>(3) Vertices a,b,c,d have already somehow been forced to have
>>4 distinct colors.
>>
>>My objection is to property (3). It's not clear what it means.

>
>I hope I finally understand. Tho vertices in (3) are not
>"forced". Their colors are arbitrarily assigned by the creator
>of the graph.


Yes.

Let G denote the full graph. Since the subgraph H determined by
the vertices a,b,c,d is not complete (i.e. H is not isomorphic
to K4), H is 3-colorable. Of course, if you've already colored
some of the other vertices of G, then you may need 4 colors for
H, but in and of itself, H is not forced to have 4 colors.
Trying to say H is forced to have 4 colors based on a prior
analysis of the coloring options for other vertices just shifts
the problem of defining "forced sets" to an unspecified analysis
of how the subgraph H relates to the rest of G.

quasi


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.