Graphs and Coloring

Coloring a graph is the idea of assigning each node a different color than any of its neighbors. It can be a very complex problem (see https://en.wikipedia.org/wiki/Graph_coloring for more details) especially if the goal is to minimize the number of different colors. That is not our goal (for which you should be thankful). We will cover the idea in lab.

Objectives

1. Learn to implement graphs
2. Learn understand some of graph coloring
3. Improve your testing skill

Assignment

Phase 1:

1. The software should take the file (specified by the command line argument if time permits). An example of the file is found in the folder for the class.
2. Assign the colors to the nodes via the algorithm discussed.
3. Implement the graph via an adjacency list
4. The maximum number of nodes is 100
5. Your testing plan needs to include the following (and other test cases as well)
   1. A graph with at least 7 nodes and at least 25 edges where the algorithm determines an optimal minimal coloring
   2. A graph with at least 7 nodes and at least 25 edges where the algorithm determines a suboptimal minimal coloring.

Phase 2:

1. Implement your designs
2. Test and debug your code

Submission instructions for Phase 2

1. Complete the SDR.
2. Combine your SDR and all of your .java and testing files into one zip folder
3. Submit the zip folder on Canvas by the due data specific there.

Restrictions:

• You may not use any Internet resources (other than to look up Java syntax) for any algorithms. You must use the algorithm specified in class.
• You may use code from this course or last semesters.