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


Re: A New Graph Coloring Conjecture.
Posted:
Jun 23, 2013 5:57 AM


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

