Last wins - DPChallenge Forums

02/08/2015 04:09:32 AM · #26726

winning is me

Canon EF 100mm f/2.8 USM Macro

02/08/2015 12:59:07 PM · #26727

Originally posted by the99:

So, the sun orbits the earth.

Of course it does! You can watch it happen! Are we supposed to believe some sort of scientific *theory* over the evidence of our own, God-given eyes?

beatabg

Google Pixel

02/08/2015 02:14:11 PM · #26728

I'm back, and I win!

Spork99

OM System OM-1

02/08/2015 04:16:59 PM · #26729

Yes, God is the problem. Spork is the heretic with the answer.

Spork wins

Originally posted by Bear_Music:

Originally posted by the99:
So, the sun orbits the earth.

Of course it does! You can watch it happen! Are we supposed to believe some sort of scientific *theory* over the evidence of our own, God-given eyes?

02/08/2015 05:23:37 PM · #26730

Who,s that girl, she looks like fun.

but i still win.

Canon EF 200mm f/2.8 L II USM Lens

02/08/2015 05:25:06 PM · #26731

There was someone like that here long long ago.

skewsme

Canon EOS-6D

02/08/2015 07:51:44 PM · #26732

beaty!

Spork99

OM System OM-1

Canon EF 100mm f/2.8 USM Macro

02/08/2015 10:15:25 PM · #26733

Meaty, Beaty, Big and Bouncy!

Spork wins

02/08/2015 11:02:41 PM · #26734

On edge colorings of connected graphs. Vizing's Theorem tells us that a graph's edges can be colored with D(G) or D(G) + 1 colors, where D(G) is the maximum degree of any vertex of G. A proper edge coloring is one requiring as few colors as possible such that no vertex is adjacent to two edges of the same color. A graph that requires D(G) colors is said to be of class 1. Every line graph is class 1. A graph that required D(G) + 1 colors is said to be of class 2. K3 is class 2.

With this in mind, over the coming days I'd like to share some elementary results of edge colorings of graphs.

02/08/2015 11:06:25 PM · #26735

only if you sing

02/09/2015 03:21:24 PM · #26736

Okay, good, we have some encouraging feedback thus far. Let B(G) denote the edge independence number of G, the maximum cardinality of any set of non-adjacent edges of G. Let m be the size of G. If m > D(G) B(G), then G is of class 2.

Proof: We show that the contrapositive is true. Suppose G is of class 1. Then there are exactly X(G) = D(G) independent edge sets of G, and since each set has at most B(G) edges, m <= D(G) B(G).

There is a corollary to this. We call a graph G of order n overfull if m >= D(G) floor(n/2). The simplest example of this is the complete graph on three vertices, K3. In this case, D(G) = 2 and floor(n/2) = floor(3/2) = 1, and m = 3 > 2. Since B(G) <= floor(n/2), we can state the following:

Every overfull graph is of class 2.

This is useful in that we don't have to consider the edge independence number of the graph to apply this test; the edge independence number will never exceed n/2.

02/09/2015 03:28:09 PM · #26737

but what is a song without words?

02/09/2015 04:09:30 PM · #26738

Like a graph without edges?

02/09/2015 04:53:13 PM · #26739

mere shrubbery

02/09/2015 05:08:53 PM · #26740

A word without a song would be
a leaf without a tree.
"A graph without an edge," she said,
"is merely shrubbery."
Oh, bail me out! Oh, set me free!
There's more to life than this!
The Jail of Reality
is a man who needs to piss.
Always stand upwind of him
and you'll usually smell just fine,
but I'm upwind of YOU, you see,
so the victory is MINE!

02/09/2015 07:28:51 PM · #26741

alas, this lass
will always outepistle
Capecodians

02/09/2015 10:25:25 PM · #26742

Originally posted by bvy:

It's important to note that the converse of our above theorem is not necessarily true -- that is, if m <= D(G) B(G), then G is of class 1. A notable example of this is the overfull Petersen graph, with m = 15, D(G) = 3, and floor(n/2) = floor(10/2) = 5. 15 <= 3 * 5 = 15, and yet the Petersen Graph is of class 2.

Also, no one caught the error in my earlier post. A graph is overfull if m is strictly greater than the product given; the correct definition of an overfull graph is one with size m > D(G) floor(n/2).

02/09/2015 10:30:08 PM · #26743

With this in mind, some exciting results will follow. Stick with me...

02/09/2015 11:10:33 PM · #26744

my graph runneth over.

02/09/2015 11:40:14 PM · #26745

When thy graph runneth over
thy numbers sink
without a trace
into the muck
adieu

02/09/2015 11:44:11 PM · #26746

stick in the muck?
bear with me?

02/10/2015 12:08:00 AM · #26747

The piney watchers watch.
A ripple wakes the pond.
Those stagnant waters lie
deeper than eye can reach,
as deep as mud can sift.
A tree breaks from its leaves.
Nothing that lives, but grieves.

02/10/2015 08:31:29 AM · #26748

Rubbish.

Another win for us.

02/10/2015 08:31:31 AM · #26749

Rubbish.

Another win for us.