Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Messages: [ Previous | Next ]
 b92057@yahoo.com Posts: 1,187 Registered: 4/18/05
Re: A New Graph Coloring Conjecture.
Posted: Jun 25, 2013 7:24 PM

On Tuesday, June 25, 2013 2:51:47 PM UTC-7, quasi wrote:
> bill wrote:
>

> >quasi wrote:
>
> >> bill wrote:
>
> >>
>
> >> >If I understand correctly, your counterexample proves the 4CT
>
> >> >to be false.
>
> >>
>
> >> No, you don't understand correctly.
>
> >>
>
> >> My examples don't disprove the 4-Color Conjecture.
>
> >>
>
> >> They disprove _your_ conjectures.
>
> >>
>
>
> >>
>
> >> If a graph contains no subgraph isomorphic to K5, then
>
> >> it's 4-colorable,
>
> >>
>
> >> In reply, I defined a graph G such that:
>
> >>
>
> >> (1) G contains no subgraph isomorphic to K5.
>
> >>
>
> >> (2) G is not 4-colorable.
>
> >>
>
> >> The graph G thus disproves your conjecture.
>
> >>
>
> >> Of course G is non-planar.
>
> >>
>
> >> Any counterexample to your conjecture must be non-planar.
>
> >>
>
>
> >>
>
> >> If a graph has no vertex with degree less than 5 and no
>
> >> subgraph isomorphic to K5, then it's 4-colorable.
>
> >>
>
> >> In reply, I defined a graph G such that:
>
> >>
>
> >> (1) G has no vertex with degree less than 5.
>
> >>
>
> >> (2) G contains no subgraph isomorphic to K5.
>
> >>
>
> >> (3) G is not 4-colorable.
>
> >>
>
> >> The graph G thus disproves your revised conjecture.
>
> >>
>
> >> And once again, G is non-planar.
>
> >>
>
> >> It appears that you did not understand either of the
>
> >>
>
> >> counterexamples I posted.
>
> >>
>
> >> You repeatedly asked if my examples are non-planar.
>
> >> Of course they are. I said as much several times. Moreover,
>
> >> they _had_ to be. Any counterexample to either of your
>
> >> conjectures must be non-planar.
>
> >>
>
> >> >Evidently your are also considering non-planar graphs.
>
> >>
>
> >> Yes, of course.
>
> >>
>
> >> >Is your counterexample a non 4-colorable, non-planar graph
>
> >> >without no forceable four vertex sets?
>
> >>
>
> >> No.
>
> >>
>
> >> My examples were non 4-colorable and of course non-planar,
>
> >> but both of my examples had subgraphs isomorphic to K4.
>
> >>
>
> >> However, your conjectures never specified no K4s.
>
> >>
>
> >> You only specified no K5s.
>
> >>
>
> >> Both of my examples had no K5s.
>
> >>
>
> >> Thus, I disproved your first two conjectures, as they were
>
> >> originally stated.
>
> >>
>
> >> Now it appears that you want to revise the conjecture still
>
> >> further.
>
> >>
>
> >> Your current conjecture seems to be:
>
> >>
>
> >> If a graph has no vertex with degree less than 5 and no
>
> >> subgraph isomorphic to K4, then it's 4-colorable.
>
> >>
>
> >> But that conjecture is also false.
>
> >>
>
>
> >> the existence of a graph G such that
>
> >>
>
> >> (1) G has no vertex with degree less than 5.
>
> >>
>
> >> (2) G does not contain any triangles (G has no K3s).
>
> >>
>
> >> (3) G is not 4-colorable.
>
> >>
>
> >> It appears you didn't understand his example either.
>
> >>
>
> >> >But that doesn't make any sense.
>
> >>
>
> >> Try to understand Butch Malahide's examples.
>
> >>
>
> >> >Perhaps I have not explained "forceable" sets sufficiently.
>
> >> >
>
> >> >A forceable 4-set is set of four vertices that cannot
>
> >> >be 3-colored. The complete graph on four vertices is
>
> >> >such a set.
>
> >>
>
> >> That's the _only_ such set, up to isomorphism.
>
> >>
>
> >> More precisely:
>
> >>
>
> >> If a graph G has a 4-point subgraph H such that H is not
>
> >>
>
> >> 3-colorable, then H is isomorphic to K4.
>
> >>
>
> >> >Also, all four vertices must be connected to the same external
>
> >> >vertex.
>
> >>
>
> >> If you do that, then you get a K5.
>
> >>
>
> >> I thought your conjectures specified no K5s.
>
> >>
>
> >> I think there's a communication gap here.
>
> >>
>
> >> In any case, so far, all your conjectures in this thread have
>
> >> been disproved. All of them.
>
> >>
>
> >> If you have a new conjecture with revised conditions, you need
>
> >> to state it carefully and completely, otherwise further
>
> >> discussion is pointless.
>
> >
>
> >I can show a forced 4 set in your graph if you are interested.
>
>
>
> By a forced 4-set, it seems you mean a subgraph isomorphic
>
> to K4. If so, there's no need to show me that my examples
>
> contain such subgraphs since I already said that my examples
>
> had subgraphs isomorphic to K4.
>
>
>
> But I also noted (do you actually _read_ replies?) that your
>
> two conjectures did not explicitly prohibit subgraphs isomorphic
>
> to K4. Rather they prohibited subgraphs isomorphic to K5. So my
>
> examples met your stated restrictions.
>
>
>
> If you now want to change your restrictions to prohibit
>
> subgraphs isomorphic to K4, fine, but then Butch Malahide's
>
> examples disprove your conjecture, consistent with this new
>
> restriction.
>
>
>
> In any case, I challenged you to give a complete, rigorous
>
> mathematical statement of what you are currently claiming,
>
> but so far, no response from you.
>
>
>

> >Otherwise, I have no objection to ending this diatribe.
>
>
>
> Probably a good idea.
>
>
>
> quasi

I was not ready to respond before. 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. V 1 & y are not adjacent.

If your interest has been piqued; i would like to start a new thread or preferably correspond via by email.

bill

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