Last wins - DPChallenge Forums

12/30/2010 09:50:11 AM · #4602

wouldn't that be me????

Sony DT 18-70mm f/3.5-5.6 Aspherical ED Zoom Lens for Sony Alpha

12/31/2010 01:53:49 AM · #4603

nope. Me and the fat man!
:-)
game over

12/31/2010 09:24:55 AM · #4604

but of course it's me....it has to be...right

Sony DT 18-70mm f/3.5-5.6 Aspherical ED Zoom Lens for Sony Alpha

12/31/2010 02:16:16 PM · #4605

only, only, if you're the fat man

12/31/2010 02:21:35 PM · #4606

are you calling me FAT!!! Thanks a whole bunch...

TrollMan

Fujifilm X-T4

Fujifilm XF 35mm f/1.4

12/31/2010 02:36:11 PM · #4607

She also called you a man...

12/31/2010 03:26:45 PM · #4608

I know I have whiskers on my chinny chin chin...but really...(maybe I shouldn't admit to that...)

01/01/2011 08:49:58 PM · #4609

Happy New Year, everyone. As promised, I'm back with some elementary results from chromatic graph theory. Chromatic graph theory deals with the coloring of vertices of a graph such that no two adjacent vertices (i.e. vertices connected by an edge) have the same color. The chromatic number of a graph is the least number of colors needed to color a given graph in this manner.

We denote the chromatic number of a graph G as X(G), and we let d(G) denote the maximum degree of any of the vertices of G. With that, we are prepared to state our first result:

X(G) <= d(G) + 1

The proof is by induction. The basis is the graph of order p = 1. There is only one, namely K1. Since X(K1) = 1 and d(K1) = 0, 1 <= 0 + 1 and the hypothesis holds for p = 1.

Let G be a graph of order k and let v be some vertex of G. By our induction hypothesis, G - v is a graph of order p = k - 1, so X(G - v) <= d(G - v) + 1 and there exists a d(G - v) + 1 coloring of G - v. Now consider the degree of v in G. If d(G - v) = d(G), then v has degree no greater than any vertex in G - v, and some color of G - v is available for v (since G - v has a d(G - v) + 1 coloring). This gives us a d(G) + 1 coloring of G. If d(G - v) < d(G), then v is the vertex of maximum degree in G, and a new color can be introduced for v giving a d(G) + 1 coloring of G. In either case, X(G) <= d(g) + 1, which proves our statement.

With this important result in hand, we can explore some further elementary results -- the chromatic numbers of cycles and trees, for instance. Stay tuned...

Message edited by author 2011-01-01 22:07:21.

Sony DT 18-70mm f/3.5-5.6 Aspherical ED Zoom Lens for Sony Alpha

01/02/2011 02:37:07 PM · #4610

1/2 + 1/2 = 0

01/02/2011 03:38:32 PM · #4611

Afternoon everyone...

01/02/2011 08:51:33 PM · #4612

I found a small error in my proof.

Originally posted by bvy:

If d(G - v) < d(G), then v is the vertex of maximum degree in G, and a new color can be introduced for v giving a d(G) + 1 coloring of G.

Not necessarily. d(G - v) can be significantly less than d(G), so adding a new color gives us a coloring of G not greater than d(G) + 1. Consider C99, the cycle of length 99, with odd vertices 1 through 97 colored red, even vertices 2 through 98 green, and vertex 99 blue (since it's incident to both a red (1) and green (98) vertex). Here d(C99) = 2 and X(C99) = d(C99) + 1 = 2 + 1 = 3. Now consider creating a graph H by adding a new vertex incident to each of those 99 vertices. Obviously it requires a fourth color. So X(H) = 4 even though d(H) = 99.

Sorry for any confusion.

fotomann_forever

01/03/2011 02:41:07 AM · #4613

My mother said to me, 'If you are a soldier, you will become a general. If you are a monk, you will become the Pope.' Instead, I was a photographer and became Leroy Dickson. :D

Sony DT 18-70mm f/3.5-5.6 Aspherical ED Zoom Lens for Sony Alpha

01/04/2011 02:14:33 AM · #4614

So, you are winning!

01/04/2011 10:21:18 AM · #4615

No, I'm winning...why are you so confused...

01/04/2011 01:04:39 PM · #4616

If T is a tree, then X(T) <= 2.

The tree of order one (K1) has one vertex which can be assigned any color; it has chromatic number one.

Let T be a tree of order greater than or equal to two. We use induction to prove that the chromatic number of T is two. The base case is a tree with exactly two vertices and one edge (K2), in which case we must assign a different color to each vertex. This tree has chromatic number two.

Now assume the result is true for all trees having k â�� 1 vertices, and let T be a tree having k vertices. Pick any leaf node of T, call it v, and consider T â�� v. T â�� v has k â�� 1 vertices and, by our induction hypothesis, chromatic number two. Since v is a leaf node, it is incident with exactly one vertex of T â�� v, call it u. We add v back to T and assign it the color not assigned to u in T â�� v. Hence, we have achieved a two-coloring of T, and T has chromatic number two.

Sony FE 200-600mm f/5.6-6.3 G OSS

01/04/2011 01:43:31 PM · #4617

Brian....hush now with those math thingies...cause it won't help you win...

vawendy

Sony Alpha 1

01/05/2011 12:04:36 PM · #4618

ummm...

did anyone realize that ja-9 had the last post for 2010, so she wins for that year?

Congrats!!

Art Roflmao

Canon EOS-6D Mark II

Canon EF 24-105mm f/4.0L IS

01/05/2011 12:23:23 PM · #4619

I only popped in here because I was told that someone spilled math all over the place again. >:/

...oh, and also, I win.

Sony FE 200-600mm f/5.6-6.3 G OSS

01/05/2011 12:48:01 PM · #4620

Originally posted by vawendy:

ummm...

did anyone realize that ja-9 had the last post for 2010, so she wins for that year?

Congrats!!

I like this post...so we are done right...I win...

vawendy

Sony Alpha 1

01/05/2011 12:56:41 PM · #4621

Originally posted by Ja-9:

Originally posted by vawendy:
ummm...

did anyone realize that ja-9 had the last post for 2010, so she wins for that year?

Congrats!!

I like this post...so we are done right...I win...

nope. now we have to keep going to see who wins this year.

01/05/2011 02:58:43 PM · #4622

Originally posted by vawendy:

Originally posted by Ja-9:

Originally posted by vawendy:
ummm...

did anyone realize that ja-9 had the last post for 2010, so she wins for that year?

Congrats!!

I like this post...so we are done right...I win...

nope. now we have to keep going to see who wins this year.

oh good grief... are you serious??? ITMTIW

01/05/2011 11:26:06 PM · #4623

Originally posted by Art Roflmao:

I only popped in here because I was told that someone spilled math all over the place again. >:/

K_p, the complete graph on p vertices, has chromatic number p. Or, more succinctly and using notation presented earlier, X(K_p) = p.

Suppose X(K_p) = q < p. Then there is a q-coloring of K_p and since q < p, two vertices of K_p must share the same color. But since every two vertices of K_p are adjacent, this is not a valid coloring and we arrive at a contradiction. Hence, X(K_p) = p.