tag:blogger.com,1999:blog-3722233.post4122561839268621412..comments2020-07-09T17:10:19.118-04:00Comments on Computational Complexity: A human-readable proof that every planar graph is 4.5-colorableLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-87786109934074749352015-11-20T01:00:44.475-05:002015-11-20T01:00:44.475-05:00Algorithm 1.[Description] Let S1, S2, ..., Sk be t...Algorithm 1.[Description] Let S1, S2, ..., Sk be the set of spiral chains of G. Color the vertices from an inner spiral chain towards an outer spiral chain. Color spiral chain from inner towards outer spiral segments. Color the core spiral segment with the color class CC1 = {G, R, Y }. For the other spiral segments use Sk,i =⇒ CC1 = {G, R, Y } , i = 1, 3, 5, ... and Sk,i =⇒CC2 = {R, Y, B} , i = 2, 4, 6, .... An vertex in the core-spiral receive an unique color form CC1 based on the adjacent previously colored triangle. In all spiral segments other than the core-spiral assign non-safe color to a vertex whenever is possible. If non-safe color cannot be assigned use respective safe color of the three color classes. In a spiral segment coloring if an vertex is in the sailing boat sub-graph and cannot be colored properly then switch safe color with non-safe color between the parallel spiral segments. This operation assures three colorability of the current outer spiral segment at any step. Furthermore three colorability of the outer-spiral segment assures always to find an safe color to assign to the last vertex of the spiral chain.<br />1 Exchange of a safe color of the upper spiral chain with a proper non-safe color of lower spiral chain can be viewed as preparation the rest of spiral chain segment vertices for 3-coloring. Think of hiding the unwanted colored spots on the surface of an cake by pushing them with your finger!<br /><br />extract from (page 9):<br />http://arxiv.org/pdf/0710.2066.pdfCahithttps://neu-tr.academia.edu/IbrahimCahitnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87229389070657507732015-11-11T14:05:37.814-05:002015-11-11T14:05:37.814-05:00attn to : Landon Rabern
and this one also
http://...attn to : Landon Rabern<br />and this one also<br /><br />http://arxiv.org/abs/0710.2066<br /><br />or<br /><br />https://www.academia.edu/1577705/A_Unified_Spiral_Chain_Coloring_Algorithm_for_Planar_GraphsCahithttps://neu-tr.academia.edu/IbrahimCahitnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11044497855446008182015-11-05T22:18:41.654-05:002015-11-05T22:18:41.654-05:00No Kempe chains used in the proof. Only switch of ...No Kempe chains used in the proof. Only switch of a "safe" color of a vertex of the spiral segment S_i with a safe color of a vertex of the spiral segment S_(i-1). This is the only case of color switching when an induced sailing boat sub-graph occur between S_i and S_(i-1). Note that, in this way maintaining 3-colorability of (current) outer-spiral segment. <br /> Cahithttps://neu-tr.academia.edu/IbrahimCahitnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67821380467852866812015-11-05T18:38:20.791-05:002015-11-05T18:38:20.791-05:00Hi Landon,
Have a look to the following to papers...Hi Landon,<br /><br />Have a look to the following to papers:<br /><br />https://www.academia.edu/541633/On_the_Algorithmic_Proofs_of_the_Four_Color_Theorem<br /><br />https://www.academia.edu/440527/VISUALIZATION_OF_THE_FOUR_COLOR_THEOREM<br /><br />Complexity of the spiral chain coloring algorithm is O(n).Cahithttps://neu-tr.academia.edu/IbrahimCahitnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91708147535710907262015-11-05T15:28:03.687-05:002015-11-05T15:28:03.687-05:00The most exciting thing about the proof for me is ...The most exciting thing about the proof for me is that it completely eschews Kempe chains. Does this lead to a faster than O(n^2) algorithm for 4.5 coloring planar graphs? Does the 4CT admit a proof without Kempe chains? Does this lead to a faster than O(n^2) algorithm for 4-coloring?Anonymoushttps://www.blogger.com/profile/02883657255047385172noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86940733950929703182015-11-05T15:03:47.998-05:002015-11-05T15:03:47.998-05:00Hi Cahit,
i attempted to understand your spiral c...Hi Cahit,<br /><br />i attempted to understand your spiral chains proof technique for the four color theorem, but after reading the paper i am not clear on how it works. Would you be willing to give an outline of the proof technique in plain language?<br /><br />Thanks,<br />landonAnonymoushttps://www.blogger.com/profile/02883657255047385172noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52837887972601128772015-11-03T22:53:58.822-05:002015-11-03T22:53:58.822-05:00How about a planar graph consist of serially conne...How about a planar graph consist of serially connected three diamond sub-graphs and an edge joining the two degree two vertices of the diamonds. This graph has no K_4 and its chromatic number is 4.Unknownhttps://www.blogger.com/profile/11131412020515799760noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36770490012463170972015-11-03T14:36:13.233-05:002015-11-03T14:36:13.233-05:00The 4 Color Theorem proves an upper bound of 4 on ...The 4 Color Theorem proves an upper bound of 4 on the fractional chromatic number of planar graphs. Any graph that contains a copy of K_4 gives a lower bound of 4. So, to summarize: <br /><br />Every planar graph has fractional chromatic number at most 4, and this bound cannot be improved.Dan Cranstonhttp://www.people.vcu.edu/~dcranston/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40735535833583594872015-11-01T06:21:34.848-05:002015-11-01T06:21:34.848-05:00A few days ago I have proposed a solution (draft) ...A few days ago I have proposed a solution (draft) to the unsettled case of Scheinerman's conjecture which was a case in the post <br /><br />https://rjlipton.wordpress.com/2015/10/29/guessing-conjectures/<br /><br />Recent version is here<br /><br />https://www.academia.edu/17504492/Scheinermans_conjecture_is_true_with_only_four_directions<br /><br />Non-computer proof of 4.5 colorability of planar graphs which is quite new for me but I have made proposition that computer-free proof based on spiral chain coloring (2004) together with the efficient algorithmic solution of three color problem (ICM2014 Seoul) may lead to the resolution P versus NP problem in the affirmative. See<br /><br />https://www.academia.edu/10213412/From_the_Proof_of_the_Four_Color_Theorem_to_P_NP<br /><br />and<br /><br />https://www.academia.edu/7108130/The_Big_Bang_Theory_of_Planar_Graph_Coloring_Solution_of_the_Three_Color_ProblemCahithttps://neu-tr.academia.edu/IbrahimCahitnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37450823078065499482015-10-28T18:17:08.904-04:002015-10-28T18:17:08.904-04:00Is there a lower bound on the fractional chromatic...Is there a lower bound on the fractional chromatic number of planar graphs? Anything strictly larger than 4?Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48418982213857021972015-10-28T14:52:26.738-04:002015-10-28T14:52:26.738-04:00Interestingly formulated problem!
As for thought ...Interestingly formulated problem!<br /><br />As for thought 5, I use feedly.com and subscribe to the relevant arXiv feeds. I subscribe to blogs I read to and such and so it keeps all of these feeds in one place. Just reading titles or abstracts seems to have been good for meAnonymoushttps://www.blogger.com/profile/05260705122889615843noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19722667023432434312015-10-28T06:36:14.477-04:002015-10-28T06:36:14.477-04:00Ryan Williams asked such a question on cstheory.st...Ryan Williams asked such a question on cstheory.stackexchange<br /><br />See: http://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-readAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17288106400348690052015-10-27T18:43:59.857-04:002015-10-27T18:43:59.857-04:00Yes.
I typically call it a 9/2 color theorem. I...Yes. <br />I typically call it a 9/2 color theorem. It implies that the fractional chromatic number of every planar graph is at most 4.5, but it is slightly stronger than that.Dan Cranstonhttp://www.people.vcu.edu/~dcranston/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32128325402891297802015-10-27T08:36:59.247-04:002015-10-27T08:36:59.247-04:004) Why does my spell checker thing colorable and c...4) Why does my spell checker thing colorable and colorings and parameterize are not words?<br /><br />British English? coloUrable and coloUrings and arametriSe? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80916033158389923672015-10-26T22:45:28.466-04:002015-10-26T22:45:28.466-04:00In graduate school I subscribed to the ArXiv's...In graduate school I subscribed to the ArXiv's combinatorics section for a few months and skimmed the abstracts, occasionally reading the papers that looked interesting. I think it was a good way to stay current, but decided it was a bad use of my time. Maybe it's not a coincidence that I'm no longer working in academics :-)Andy Parrishhttps://www.blogger.com/profile/12252029594014518238noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75359240714406799402015-10-26T19:33:44.442-04:002015-10-26T19:33:44.442-04:00Instead of saying 4.5-colorable (which makes no se...Instead of saying 4.5-colorable (which makes no sense to me since you can't have half a color) is if fair to call it 9/2-colorable?<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47275031673582974232015-10-26T13:01:49.297-04:002015-10-26T13:01:49.297-04:00Very interesting.
A few weeks ago, there was a q...Very interesting. <br /><br />A few weeks ago, there was a question on Quora (https://www.quora.com/What-are-the-papers-every-programmer-should-read) on the papers every programmer should read. My thoughts were immediately towards Cook's definition of NP Complete, Karp's 21 Problems, and Google's PageRank - the later two being more readable than the first but all being papers that I enjoyed reading a lot. <br /><br />This post makes me wonder about papers that CS Theory or Mathematicians should (and can) read, say in one sitting, or without having to already be an expert or reference a bunch of other outside texts to understand them. Maybe not the details of the proofs, but at least the concepts of the paper. <br /><br />Have you ever done anything like this?Charles Ghttp://learninglover.comnoreply@blogger.com