## Graph Coloring Boards

< back to resources**Graph Coloring Boards**

These boards introduce to the child to a concept in computer science called graph coloring. In its simplest form, the graph coloring problem asks how to color the nodes in a graph such that no two adjacent nodes share the same color. The optimal graph coloring problem asks what the fewest number of colors are that can solve the graph coloring problem.

A common application of graph coloring is scheduling. For example, imagine if we have* k *airplanes, and we have to assign them to *n* flight times. If two flight times overlap, we could not assign them to the same airplane. To solve this problem, one would create a graph where each node represents a flight time, and there is an edge between two nodes if the flight times overlap. Each color would represent an airplane. One would then solve the graph coloring problem on this graph to show the minimal number of airplanes needed, and the way in which these airplanes should be scheduled.