quasi
Posts:
11,911
Registered:
7/15/05


Re: A New Graph Coloring Conjecture.
Posted:
Jul 2, 2013 4:08 AM


bill wrote: >quasi wrote: >>bill wrote: >>>quasi wrote: >>>> >>>> If you can't define forced sets in a way that others can >>>> understand, there's not much chance that anyone would be >>>> able to follow a proposed proof of yours of the 4CT. >>> >>>Can you accept this definition? >>> >>>Consider; >>> >>>Impasse. A difficulty encountered in the attempted >>> four coloring of a graph. >>> >>>Type I " An impasse that is created by the presence of a >>>vertex adjacent to four other vertices, each of which has an >>>assigned color that is different from the assigned color any >>>of the three other vertices". >>> >>>Type II "All other impasses." >> >>No, I don't view that as an acceptable definition. >> >>It appears your concept of a forced 5set in a graph G is a >>set of 5 vertices, S = {a,b,c,d,e} say, such that >> >>(1) Not all vertices of S are adjacent. >> >>(2) One of the vertices of S, e say, is adjacent to the other 4. >> >>(3) Vertices a,b,c,d have already somehow been forced to have >>4 distinct colors. >> >>My objection is to property (3). It's not clear what it means. > >I hope I finally understand. Tho vertices in (3) are not >"forced". Their colors are arbitrarily assigned by the creator >of the graph.
Yes.
Let G denote the full graph. Since the subgraph H determined by the vertices a,b,c,d is not complete (i.e. H is not isomorphic to K4), H is 3colorable. Of course, if you've already colored some of the other vertices of G, then you may need 4 colors for H, but in and of itself, H is not forced to have 4 colors. Trying to say H is forced to have 4 colors based on a prior analysis of the coloring options for other vertices just shifts the problem of defining "forced sets" to an unspecified analysis of how the subgraph H relates to the rest of G.
quasi

