Timeline for Small Ramsey numbers and Brooks' Theorem
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 29, 2012 at 4:30 | vote | accept | snufkin26 | ||
| Sep 27, 2012 at 22:30 | comment | added | Tony Huynh | Yes, every other vertex of $H$ means what you think it means. It seems that the Chvatal-Harary proof is wrong, but I cannot say what they definitely had in mind. At the very least it is unclearly written. Finally, another idea I had in mind is to use Hadwidger's Conjecture. Since $\chi(G) \geq 4$, we have that $G$ contains a $K_4$-minor, and hence a $K_4$-subdivision $H$. Note that $H$ contains at least one subdivided edge, else $G$ contains a $K_4$. By looking at which edges of $H$ are subdivided, and how $H$ attaches to the rest of $G$, I think we can prove the theorem. | |
| Sep 27, 2012 at 17:56 | comment | added | snufkin26 | Then above Chvatal-Harary's proof is wrong? or not? How do you think about it? I want to know this mainly, so I can't let your answer accepted, but your answer is very helpful, so I voted up yours. | |
| Sep 27, 2012 at 17:53 | comment | added | snufkin26 | Thank you very much for your edit. I was confused in "Hence, $G[N(v)]$ must be a matching $ab,cd$ of size 2" because I thought the case when c,d has two edges to $S(v)$. But by easy argument, this case can be excluded. And I can't understand (perhaps because of my weak ability of English) the sentence "Thus, every other vertex of $H$ is a stable set in $G$". Does this means "if let $C_8=v_1\dots v_8$, then $v_1v_3v_5v_7$ form stable set"? Finally, by your kindly help, we got two proofs which one is avoids Brooks' theorem, the other avoids above lemma. (to be continue) | |
| Sep 27, 2012 at 15:28 | comment | added | Tony Huynh | You are right. That part was totally unclear and misleading. I edited accordingly. | |
| Sep 27, 2012 at 15:27 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 469 characters in body; added 70 characters in body
|
| Sep 27, 2012 at 4:56 | comment | added | snufkin26 | Thank you very much. I'll add details my proof(?). Your proof is interesting to me. But I can't understand the sentence "This implies that some vertex of $C$ has degree 2 in $G$, since $N(v)$ only contains four vertices, a contradiction. ". Why there aren't no vertex in $N(v)$ which has two neighborhood in $S(v)$? Perhaps this is easy question, sorry. | |
| Sep 27, 2012 at 2:29 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 17 characters in body
|
| Sep 27, 2012 at 2:18 | history | answered | Tony Huynh | CC BY-SA 3.0 |