A zoo is going to place its animals in a set of large open a

A zoo is going to place its animals in a set of large open areas, instead of having them in individual cages. If two different animals cannot live together peacefully (e.g., a tiger and deer cannot live together because the tiger will eat the deer), then they must be put in different open areas. The zoo wants to determine the minimum number of open areas needed to safely house all its animals. Model this problem of assigning animals to a minimal number of open areas as a graph-coloring problem. What are the vertices, what are the edges, what are the colors?

Solution

Vertices: Animal

Edges: Animals cannot live together peacefuly. That is if two animals are connected by an edge then they cannot leave peacefully together.

colors: Open arreas needed to safely house all the animals.

Chromatic number: Minimum number of open arreas needed.