Graph Coloring: Applications


Let's see how this information about graphs and coloring can be used to solve real-life problems:

A tropical fish hobbist had six different types of fish: Alphas, Betas, Certas, Deltas, Epsalas, and Fetas, which shall henceforth be designated by A, B, C, D, E, and F, respectively. Because of predator-prey relatinships, water conditions, and size, some fish can be kept in the same tank. The following table shows which fish cannot be together:

Type A B C D E F
Cannot be with B, C A ,C, E A, B, D, E C, F B, C, F D, E

What is the smallest number of tanks needed to keep all the fish?

We will use a graph to help us answer this question. Below you will see an uncolored graph that describes this situation. Can you figure out what each vertex represents? each edge?



Next: See the Fish Graph with Colors
Back: Map Coloring