quasi
Posts:
12,050
Registered:
7/15/05


Re: A New Graph Coloring Conjecture.
Posted:
Jun 25, 2013 6:08 PM


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

