tag:blogger.com,1999:blog-3722233.post6427605045697247911..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: ''4col \le 3col is counter-intuitive and makes me sad'' NOT ANYMORE!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-513597030221490752014-05-20T19:28:52.858-05:002014-05-20T19:28:52.858-05:00I think the details differ, but the main ideas in ...I think the details differ, but the main ideas in Lovasz's reduction are similar to yours. Here is the paper http://www.cs.elte.hu/~lovasz/scans/covercolor.pdf. It goes in two steps: reducing k-colorability to deciding if a hypergraph is 2-colorable, and then reducing 2-coloring a hypergraph to 3-coloring a graph. Chvatal has very nice lecture notes that explain the reduction in a single shot: http://users.encs.concordia.ca/~chvatal/notes/color.html. Sashohttps://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88464984187955900182014-05-20T08:06:55.169-05:002014-05-20T08:06:55.169-05:00bill, out of curiosity, how much spam do you recei...bill, out of curiosity, how much spam do you receive normally ? you stated that you get spam comments ? I guess it is a good thing after all to have to go through approval method rather than being able to post directly.<br />and more interestingly, how many readers do you have on a weekly basis ? or per post ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89072017988000996922014-05-19T22:52:12.707-05:002014-05-19T22:52:12.707-05:00I have LaTeXed up the correct proof and the post n...I have LaTeXed up the correct proof and the post now points to it.<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31999144051833370122014-05-19T10:24:04.655-05:002014-05-19T10:24:04.655-05:00I have correct my proof (more like overhauled it c...I have correct my proof (more like overhauled it completely) and I think it is now correct. THANKS to all who pointed out mistakes.<br /><br />Lance and I get many spam comments, but one we got today is particularly off-base considering that my original was wrong and I had to modify:<br /><br />Howdy! This post could not be written much better!<br />Going through this article reminds me of my previous roommate!<br />He always kept talking about this. I will send this information to<br />him. Pretty sure he's going to have a great read.<br />Thanks for sharing!|<br /><br />(They then had a link to who-knows-what.)GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37222711806014725852014-05-19T09:35:17.934-05:002014-05-19T09:35:17.934-05:00I think I have seen a solution to reducing 6COL to...I think I have seen a solution to reducing 6COL to 3COL by replacing each vertex by a triangle and each edge by a suitable gadget. Then of course since 4COL<=6COL, we get a reduction. Now I cannot recall the gadget, but it should not be too complicated.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30638288030238661242014-05-19T08:35:33.360-05:002014-05-19T08:35:33.360-05:00Since current proof is WRONG I hope he had a diffe...Since current proof is WRONG I hope he had a different proof. If you have a reference or a proof please leave as a comment. If proof is too long to post as a comment please email me and I will modify my post.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68991381561799452592014-05-19T08:34:42.615-05:002014-05-19T08:34:42.615-05:00Bob- Typo fied, thanks
Dom-Proof retracted, thanks...Bob- Typo fied, thanks<br />Dom-Proof retracted, thanks. I hope something like what I have works- need a gadget that is 3-col and makes sure that only one of four vertices is colored T.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69450359508035420412014-05-19T06:59:59.574-05:002014-05-19T06:59:59.574-05:00I think Lovasz is attributed with proving this red...I think Lovasz is attributed with proving this reduction (perhaps not the same proof)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40299301789313967802014-05-19T06:45:30.018-05:002014-05-19T06:45:30.018-05:00I think that is happening, just there is a typo in...I think that is happening, just there is a typo in "G is 3-col iff G' is 4-col." There are a couple other grammatical typos.<br /><br />Unfortunately, I cannot understand the reduction, won't v(i,1), v(i,2), v(i,3), v(i,4), R form a 5-clique?domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50714905698523963432014-05-19T04:29:38.590-05:002014-05-19T04:29:38.590-05:00When proving 4-col \le 3-col, shouldn't you co...When proving 4-col \le 3-col, shouldn't you construct a graph G' such that G is 4-col iff G' is 3-col?Bobnoreply@blogger.com