
Re: cotpi 69  Black and white plane
Posted:
Oct 6, 2013 4:59 PM


On 10/06/2013 04:13 PM, David Bernier wrote: > On 10/06/2013 02:43 PM, quasi wrote: >> quasi wrote: >>> David Bernier wrote: >>>> >>>> Suppose we are looking for finite plane pointconfigurations >>>> that must use at least 4 colours. Suppose Q is such as >>>> configuration. >>>> >>>> If Z is a point in the configuration Q, and Z has >>>> two or fewer points in Q at unitdistance from Z, >>>> then it seems to me harmless to delete the Point Z >>> >from the configuration, meaning that >>>> Q less Z would still need at least 4 colours. >>>> >>>> But is it really true? and if so, how could one >>>> prove it? >>> >>> The proof is easy. >>> >>> In general, we have the following proposition: >>> >>> If G is graph with chi(G) = n and v is a vertex of G >>> with deg(v) < n1 then chi(Gv) = n. >>> >>> proof: >>> >>> Assume the hypothesis. >>> >>> Since Gv is a subgraph of G, chi(GV) <= n >>> >>> Suppose chi(Gv) < n. >>> >>> Choose some such coloring of Gv. Now color G the same way, >>> leaving vertex v temporarily uncolored. >>> >>> Case 1: chi(G) <= n2. >>> >>> Then we can color v with an entrirely new color (not one of >>> the ones used for Gv), which would imply chi(G) <= n1, >>> contrary to chi(G) = n. >>> >>> Case 2: chi(G) = n1 >>> >>> Since deg(v) < n1, there are at most n2 vertices of G which >>> are adjacent to v, hence at most n2 colors are used for those >>> vertices. It follows that of the n1 colors used to color Gv, >>> at least one of those colors is still available to color v. >>> But that meaans chi(G) <= n1, contrary to chi(G) = n. >>> >>> It follows that chi(G) = n, as was to be shown. >> >> I meant: >> >> It follows that chi(Gv) = n, as was to be shown. > > I mentally checked quasi's proof for n = 4, to test > a concrete case. > > I see that quasi used a proof by contradiction, > in assuming that: chi(Gv) < n, > and then derived a contradiction from there. > That then shows that chi(Gv) = n. > > Also the hypothesis/notation chi(G) = n (just to be clear > to all) means that the graph G can be colored with > n colors, but can't be colored with less than n > colors. > > Similarly, deg(v) stands for the degree of a vertex v > of the graph G, defined for example here: > > < http://en.wikipedia.org/wiki/Degree_%28graph_theory%29 > .
The kinds of graphs being considered are known as 'unit distance graphs', cf.: < http://en.wikipedia.org/wiki/Unit_distance_graph > .
I believe the quoted statement below is true, based on quasi's theorem:
``Suppose G is a finite unit distance graph such that chi(G) = 5.
Furthermore, suppose that any proper induced subgraph H of G has chi(H) < 5.
cf.: http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs
Then any vertex v of G has the property: deg(v) >= 4."
Proof:
If not, then for some vertex v of G, deg(v) < 4. By quasi's theorem, chi(Gv) = 5. Note: the subgraph Gv is "properly known as" the induced subgraph of G induced by V\{v}, where V is the vertexset of G. So the proper induced subgraph conveniently denoted Gv is such that chi(Gv) = 5. This contradicts the assumption that: any proper induced subgraph H of G has chi(H) < 5.
Therefore, if v is a vertex of G, one must have deg(v) >=4. qed.
Broadly speaking, a finite unit distance graph G with chi(G)=5 which has the minimum possible number of vertices must have deg(v)>=4 for any vertex v of G.
David Bernier
 Let us all be paranoid. More so than no such agence, Bolon Yokte K'uh willing.

