tag:blogger.com,1999:blog-2433841880619171855.post8705660315622800889..comments2024-03-27T21:09:44.320+00:00Comments on Pat'sBlog: Polynomials, Coloring Graphs, and SudokuUnknownnoreply@blogger.comBlogger2125tag:blogger.com,1999:blog-2433841880619171855.post-20016422003649566732010-02-24T16:34:10.104+00:002010-02-24T16:34:10.104+00:00Yes, If it is planer...(this one obviously is, it ...Yes, If it is planer...(this one obviously is, it is drawn without lines crossing; But keep in mind that even simple graphs like K-five (think of a pentagon with a pentagram inside it).. and that isn't planer. (in fact it is half the "forbidden" that Kuratowski's theorem uses to define Planer. This one obviously is, and I agree, it must have four colors, but how many different ways could it be colored with just four colors?? (by the way you know if it can be colored in four colors, none of the polynomial factors could be (n-a) could have a>3 since that would produce zero ways to color it with four colors (and you just proved it COUlD be done in four).. <br />One of the factors has to be n, and the other seven(remember with eight vertices, it will be an eighth degree polynomial) will be either (n-1), (n-2) or (n-3) ... I'm betting on a lot of (N-3) factors.. but (ugly confession) I'm not sure I have the polynomial for that one yet.Pat's Bloghttps://www.blogger.com/profile/15234744401613958081noreply@blogger.comtag:blogger.com,1999:blog-2433841880619171855.post-21580789088099682992010-02-24T13:02:16.135+00:002010-02-24T13:02:16.135+00:00>Ok, so what about one like this? Can you do i...>Ok, so what about one like this? Can you do it in three colors, four, five?<br /><br />I'm not getting the polynomial part yet, but I know the first graph can be colored in 4 colors or less, because this is the same as the map coloring theorem. So any planar graph can be colored in 4 colors or less. (I got that from <i>Euler's Gem</i>, by Dave Richeson, which I'm in the middle of.)<br /><br />I just worked it out (drew a map), and discovered that a loop of 4 in the graph is equivalent to a situation where 4 corners touch (like CO, UT, NM, AR).<br /><br />I've convinced myself that 4 colors are needed. To explain my reasoning, I'll use letters. Coming down the left, I have A on top, then B, the third one down touches both the first two, so it needs a third letter, C. The last one touches the 3rd and top, so it can be B. Next to C must be A, since it touches bottom left. Below that must be a C. Now the second down on the right touches A, B, and C, so must be D, leaving B for the top right.Sue VanHattumhttps://www.blogger.com/profile/10237941346154683902noreply@blogger.com