Timeline for Graph 5-Coloring
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 16, 2018 at 10:31 | history | edited | lynn | CC BY-SA 4.0 | added 68 characters in body |
| Aug 15, 2018 at 19:40 | comment | added | Neil | Well, you can easily improve the speed to \$O(4^n)\$, no? | |
| Aug 15, 2018 at 19:23 | history | edited | lynn | CC BY-SA 4.0 | added 464 characters in body |
| Aug 15, 2018 at 18:09 | comment | added | lynn | Now it checks all the colorings in lexicographic order :) so it's deterministic and O(5^n), but a lot slower for most inputs. | |
| Aug 15, 2018 at 18:08 | history | edited | lynn | CC BY-SA 4.0 | deleted 24 characters in body |
| Aug 15, 2018 at 18:02 | comment | added | Rushabh Mehta | Ah, I see, I've misunderstood. Interesting approach! | |
| Aug 15, 2018 at 17:59 | comment | added | lynn | My code randomly generates graph colorings and checks them until it generates a correct graph coloring, which it then prints upon exiting. In the case you describe it'd start over and hopefully not color those 5 nodes all 5 available colors. | |
| Aug 15, 2018 at 17:56 | comment | added | Rushabh Mehta | Suppose that a given node in your graph is surrounded by 5 other nodes, which you've already colored the 5 colors you are allowed. | |
| Aug 15, 2018 at 17:51 | comment | added | Rushabh Mehta | I'll try to build a test case to break this | |
| Aug 15, 2018 at 17:50 | history | edited | lynn | CC BY-SA 4.0 | deleted 7 characters in body |
| Aug 15, 2018 at 17:50 | comment | added | Rushabh Mehta | Nice effort, but I do believe you are missing one component. What about the case where a node is surrounded by 5 different colors? | |
| Aug 15, 2018 at 17:49 | history | answered | lynn | CC BY-SA 4.0 |