
Re: A New Graph Coloring Conjecture.
Posted:
Jun 25, 2013 4:46 PM


On Sunday, June 23, 2013 2:54:53 AM UTC7, 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. > > > > quasi
I can show a forced 4 set in your graph if you are interested. Otherwise, I have no objection to ending this diatribe.
bill. bill

