
Re: A New Graph Coloring Conjecture.
Posted:
Jun 25, 2013 7:24 PM


On Tuesday, June 25, 2013 2:51:47 PM UTC7, 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 4Color Conjecture. > > >> > > >> They disprove _your_ conjectures. > > >> > > >> Your initial conjecture: > > >> > > >> If a graph contains no subgraph isomorphic to K5, then > > >> it's 4colorable, > > >> > > >> In reply, I defined a graph G such that: > > >> > > >> (1) G contains no subgraph isomorphic to K5. > > >> > > >> (2) G is not 4colorable. > > >> > > >> The graph G thus disproves your conjecture. > > >> > > >> Of course G is nonplanar. > > >> > > >> Any counterexample to your conjecture must be nonplanar. > > >> > > >> Your revised conjecture: > > >> > > >> If a graph has no vertex with degree less than 5 and no > > >> subgraph isomorphic to K5, then it's 4colorable. > > >> > > >> 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 4colorable. > > >> > > >> The graph G thus disproves your revised conjecture. > > >> > > >> And once again, G is nonplanar. > > >> > > >> It appears that you did not understand either of the > > >> > > >> counterexamples I posted. > > >> > > >> You repeatedly asked if my examples are nonplanar. > > >> Of course they are. I said as much several times. Moreover, > > >> they _had_ to be. Any counterexample to either of your > > >> conjectures must be nonplanar. > > >> > > >> >Evidently your are also considering nonplanar graphs. > > >> > > >> Yes, of course. > > >> > > >> >Is your counterexample a non 4colorable, nonplanar graph > > >> >without no forceable four vertex sets? > > >> > > >> No. > > >> > > >> My examples were non 4colorable and of course nonplanar, > > >> 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 4colorable. > > >> > > >> But that conjecture is also false. > > >> > > >> Butch Malahide has already shown (earlier in this thread) > > >> 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 4colorable. > > >> > > >> 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 4set is set of four vertices that cannot > > >> >be 3colored. 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 4point subgraph H such that H is not > > >> > > >> 3colorable, 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 4set, 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

