
Re: A New Graph Coloring Conjecture.
Posted:
Jun 22, 2013 10:36 PM


On Wednesday, June 19, 2013 9:25:28 PM UTC7, quasi wrote: > bill wrote: > > > > > >Okay. > > > > > >Finite planar graphs are 4C because they cannot > > >contain subgraphs isomorphic to K5! > > > > > >My thinking is thus. In any K4 subgraph one vertex is > > >unavailable. Therefore, there is no way to force any set of > > >4 vertices to have four different colors. Tangled chains are > > >not due to the congiguration of the graph but result from a > > >fortuitous coloring. Plus, if two chains are tangled; there > > >will be two that are not tangled. > > > > > >If there are no forceable sets of four vertices, the graph > > >must be 4 colorable. > > > > Except that I've already shown you a counterexample. > > > > quasi
If I understand correctly, your counterexample proves the 4CT to be false. Evidently your are also considering nonplanar graphs.
Is your counterexample a non 4colorable, nonplanar graph without no forceable four vertex sets?
But that doesn't make any sense.
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.
Also, all four vertices must be connected to the same external vertex.
bill > >

