Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: cotpi 69 - Black and white plane
Replies: 26   Last Post: Oct 9, 2013 10:23 AM

 Messages: [ Previous | Next ]
 David Bernier Posts: 3,735 Registered: 12/13/04
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 point-configurations
>>>> 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 unit-distance 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) < n-1 then chi(G-v) = n.
>>>
>>> proof:
>>>
>>> Assume the hypothesis.
>>>
>>> Since G-v is a subgraph of G, chi(G-V) <= n
>>>
>>> Suppose chi(G-v) < n.
>>>
>>> Choose some such coloring of G-v. Now color G the same way,
>>> leaving vertex v temporarily uncolored.
>>>
>>> Case 1: chi(G) <= n-2.
>>>
>>> Then we can color v with an entrirely new color (not one of
>>> the ones used for G-v), which would imply chi(G) <= n-1,
>>> contrary to chi(G) = n.
>>>
>>> Case 2: chi(G) = n-1
>>>
>>> Since deg(v) < n-1, there are at most n-2 vertices of G which
>>> are adjacent to v, hence at most n-2 colors are used for those
>>> vertices. It follows that of the n-1 colors used to color G-v,
>>> at least one of those colors is still available to color v.
>>> But that meaans chi(G) <= n-1, contrary to chi(G) = n.
>>>
>>> It follows that chi(G) = n, as was to be shown.

>>
>> I meant:
>>
>> It follows that chi(G-v) = 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(G-v) < n,
> and then derived a contradiction from there.
> That then shows that chi(G-v) = 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(G-v) = 5. Note: the subgraph G-v
is "properly known as" the induced subgraph of G
induced by V\{v}, where V is the vertex-set of G.
So the proper induced subgraph conveniently
denoted G-v is such that chi(G-v) = 5.
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.

Date Subject Author
10/2/13 cotpi
10/2/13 Pubkeybreaker
10/2/13 quasi
10/2/13 Mike Terry
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 quasi
10/6/13 quasi
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 quasi
10/6/13 David Bernier
10/9/13 Phil Carmody
10/9/13 David Bernier
10/2/13 Eric Lafontaine
10/2/13 Michael F. Stemper
10/2/13 quasi
10/2/13 quasi
10/2/13 Haran Pilpel
10/2/13 quasi
10/2/13 quasi
10/2/13 Ted Schuerzinger