You've probably heard that a map (with some restrictions: no enclaves, no "bridges", countries meeting at a
point are not considered adjacent) can be colored using only four colors.
Graph coloring is a bit more general: given a bunch of "nodes" with "edges" between them, color the nodes such that no two adjacent (ie, have an edge between them) nodes have the same color. A trivial way to do that would be giving every node its own color. A bit better would be to start at the first node, give it color 0, then the second node can have color 0 or 1 (depending on whether it's connected to the first) and so on, and there are tricks you can play here with the order in which you visit the nodes (it matters a lot, and in fact there is an order such that you get an optimal coloring this way, there are many interesting things you can do there).
The challenge is usually to find such a coloring with the fewest possible number of colors, but you could also ask: given a certain number of colors you're allowed to use, can you color the graph? (this is an example of an NP-complete problem)
Anyway for this mini challenge, there are two graphs (I could make more, if necessary), a small one with 50 nodes and 350 edges, and a big one with 500 nodes and 62423 edges. The second one is particularly nasty not so much because it has 500 nodes, but mainly because it has about half as many edges as it could maximally have, which is about the worst case (more edges and it becomes so constrained that there are not many solutions to try, less edges and you won't need as many colours so again there are few solution). But whatever, the point is, there's an easy one and a hard one. The east one is still big enough that you can't blindly try everything though, you have to be at least slightly clever.
50 graph:
gc50.txt500 graph:
gc500.txtFormat: first line is [number of nodes] [number of edges]
Other lines are the edges, a pair of nodes that has a link between them.
The last line is empty (so that every line you read can end in \r\n to simplify parsing or whatever), and there are exactly as many edges as advertised (so you can read them in a for loop and not care about end of file).
Challenges (easy):
- Find an optimal coloring for gc50.
- Find a coloring with at most 80 colors for gc500.
- Prove that you need at least 11 colors to color gc500.
Challenges (medium):
- Find a coloring with at most 60 colors for gc500.
Challenges (hard):
- Find a coloring with at most 52 (protip: that's not optimal) colors for gc500.
Challenges (impossible):
- Find an optimal coloring for gc500. (I don't even know how many colors it will have, so don't ask)
Challenges (other):
- Find a non-trivial lower bound on the number of colors necessary for gc500 (deliver proof/explanation of why it's a lower bound).
PM answers to me (don't post colorings please, feel free to post lower bounds), discuss everything (as long as it doesn't violate "don't post colorings"), pretty much anything goes with respect to how you solve this but it will be more interesting for you if you play with the problems yourself instead of just dumping them into open source solvers.
