Review the documentation of the graph-coloring
algorithms included in the networkx
library — our strategy is essentially the same as
strategy_largest_first.
Pick one of the other methods and write additional code to apply it on our graph. Does the number of colors it uses seem to differ from our approach?
Systematically compare at least two other methods with our original strategy, using at least ten different replicas of the graph-generation process. Record the minimum, average, and maximum number of colors used by each method over the set of replicas and discuss the results in writing.
Read (for example DOI 10.1016/j.matpr.2022.06.392) or watch (for example a video tutorial) information on other applications of graph coloring (than map coloring and frequency assignment).
Write down your personal top five of unfamiliar terms that you encounter along with your present best guess of what those terms might mean. Then, consult them in the glossary and fill in the glossary feedback form if any are missing.
Pick three applications of the graph coloring problem (from what you studied in the basic stage of the assessment and/or those discussed in class). For each one, think about how important it would be to truly minimize the total number of colors instead of just trying to keep the amount low?
Also, think about whether you find it truly critical that no neighbors ever share a color or would it simply be mildly inconvenient for each application.
Discuss your thought process and conclusions in writing. Remember to clearly cite all sources.