| Author | Thread |
|
|
07/12/2013 10:27:32 AM · #21926 |
Originally posted by Art Roflmao:
I'm starting to crave  bvy's math problems. |
Okay then! Let's continue where we left off...
Originally posted by bvy:
Originally posted by bvy:
To the Last Wins community, I sincerely apologize. Some time back, I promised to show the following: Given a k-chromatic graph G (k >= 2) with maximum degree D, that for any r >= D, there exists a k-chromatic, r-regular graph H that has G as an induced subgraph. I discovered this to be a simple extension of a more classic result -- identical to the one stated above but with no restrictions on the chromatic number of G or H.
I'm preparing a proof of the original statement now and will post it soon. I appreciate your patience. |
Well, I'm not a bot. Anyway...
I'd like to start things off with a simple prerequisite proof; I'll be referring to it later on. Let G1 be a k-chromatic graph with k >= 2, let G2 be a copy of G1, and let G be the graph which results by adding edges between corresponding vertices of G1 and G2. Then G is also k-chromatic. This is not difficult to visualize. Suppose G1 has colors {c1, c2, ..., ck}. We simply permute the colors of G2, such that it uses colors {c2, c3, ..., ck, c1}. So for any u in G1 and its corresponding vertex v in G2, if u is colored c(i) in G1 then it is colored c(i+1) in G2 (or if it's colored ck in G1 then it's colored c1 in G2). G1 and G2 are both k-chromatic, and the resulting construction of G is also k-chromatic since, as we've shown, we can add edges between G1 and G2 without connecting like-colored vertices. |
With this background already established, and presumably everyone's had time to review, I formally present the following:
Given a k-chromatic graph G (k >= 2) with maximum degree D, that for any r >= D, there exists a k-chromatic, r-regular graph H that has G as an induced subgraph.
Proof: We proceed by induction on r - d, where we define d as d(G), the smallest degree of any vertex of G.
If r - d = 0, then r = d and we are done. (Since r = d <= D and r >= D, then r = D, d = D, and the graph is regular.)
If r - d > 0, then we consider two disjoint copies of G, call them G1 and G2. For every vertex of G1 having degree less than r, we add an edge between it and the corresponding vertex of G2. We keep the original coloring of G1 and permute the colors of G2 as described above. We call the newly constructed graph H, and let d' = d(H). Observe that r - d' = r - (d + 1), and that H is k-chromatic.
If r = d' then we are done; otherwise continue as above starting with H until r = d'. Since none of the graph constructions involved adding edges between the vertices of G, G must be an induced subgraph of the final graph.
|
|
|
|
07/12/2013 10:44:50 AM · #21927 |
| Wait I saw this on the Simpsons.. the solution is RDRR |
|
|
|
07/12/2013 10:54:11 AM · #21928 |
|
|
|
07/12/2013 12:45:41 PM · #21929 |
| The only conclusion is that Spork wins. |
|
|
|
07/12/2013 12:57:20 PM · #21930 |
| Damn. I was just leaving.... |
|
|
|
07/12/2013 01:06:07 PM · #21931 |
|
|
|
07/12/2013 01:46:15 PM · #21932 |
|
|
|
07/12/2013 02:06:50 PM · #21933 |
Yes, sit down and you can speak after you pay tribute to Spork at his victory party.
Spork wins. |
|
|
|
07/12/2013 02:23:00 PM · #21934 |
| I hope you get your deposit back on that party! |
|
|
|
07/12/2013 02:26:35 PM · #21935 |
|
|
|
07/12/2013 09:39:04 PM · #21936 |
|
|
|
07/12/2013 09:51:01 PM · #21937 |
|
|
|
07/13/2013 08:49:57 AM · #21938 |
The Party was great
Spork wins. |
|
|
|
07/13/2013 04:51:03 PM · #21939 |
Originally posted by bvy:
Originally posted by Art Roflmao:
I'm starting to crave bvy's math problems. |
Okay then! Let's continue where we left off... |
Sorry, my craving dissipated and devolved to my usual disdain 30 seconds after I posted.
If it's any consolation, I win. |
|
|
|
07/14/2013 11:33:44 AM · #21940 |
Originally posted by Art Roflmao:
Originally posted by bvy:
Originally posted by Art Roflmao:
I'm starting to crave bvy's math problems. |
Okay then! Let's continue where we left off... |
Sorry, my craving dissipated and devolved to my usual disdain 30 seconds after I posted.
If it's any consolation, I win. |
Spork will console himself by continuing to win.
|
|
|
|
07/14/2013 11:51:57 AM · #21941 |
|
|
|
07/14/2013 12:12:31 PM · #21942 |
|
|
|
07/14/2013 12:16:04 PM · #21943 |
|
|
|
07/14/2013 12:16:18 PM · #21944 |
|
|
|
07/14/2013 12:27:00 PM · #21945 |
| But none of them really, since Spork always wins |
|
|
|
07/14/2013 04:56:39 PM · #21946 |
There really are no winners here.
...except for me. |
|
|
|
07/14/2013 07:28:36 PM · #21947 |
Originally posted by Art Roflmao:
There really are no winners here.
...except for me Spork. |
Spork vandalized your post while winning. |
|
|
|
07/14/2013 08:36:02 PM · #21948 |
| Correction: Spork vandalized my post while attempting to win. But to no avail. |
|
|
|
07/14/2013 08:47:51 PM · #21949 |
Originally posted by Art Roflmao:
Correction: Spork vandalized my post while attempting to win. But to no avail. With great success. |
Why thank you Art.
Spork wins |
|
|
|
07/14/2013 10:31:36 PM · #21950 |
| You're welcome and no, you don't. |
|
Home -
Challenges -
Community -
League -
Photos -
Cameras -
Lenses -
Learn -
Help -
Terms of Use -
Privacy -
Top ^
DPChallenge, and website content and design, Copyright © 2001-2025 Challenging Technologies, LLC.
All digital photo copyrights belong to the photographers and may not be used without permission.
Current Server Time: 08/04/2025 04:44:28 AM EDT.
