NM - Graph Coloring Lesson

Graph Coloring Lesson

How can this situation be modeled with graphs?

Cities can be represented with vertices and possible railroad connections with edges. The cost for each segment of railroad needs to be noted on the graph next to each edge.

Cities can be represented with vertices and possible railroad connections with edges. The cost for each segment of railroad needs to be noted on the graph next to each edge.

  • Map I, Solution A: Color each region a different color.
  • Map I, Solution B: Regions 2 and 4 can be the same color, while the other regions are all different colors.
  • Map II, Solution A: Color each region a different color.
  • Map II, Solution B: Regions 1 and 3 can be the same color, while the other regions are all different colors (Or Regions 1 and 4 can be the same. Or Regions 2 and 4 can be the same). Regions 1 and 3 only meet at a single point, so they can be the same color.
  • Map II, Solution C: Use one color for Regions 1 and 3, another color for Regions 2 and 4, and a third color for Region 5.

If you want to color each map using the least number of colors (still keeping adjacent regions separate colors), how many colors are needed for each map? Map I needs four colors. Map II needs three colors. 

If you want to color each map using the least number of colors (still keeping adjacent regions separate colors), how many colors are needed for the map below? Starting with the inner country, you can alternate between two colors as you color the outer regions. Even though some countries are completely enclosed by others, every country or region is connected to at least one other. This satisfies the requirements for a map. 

Cities can be represented with vertices and possible railroad connections with edges. The cost for each segment of railroad needs to be noted on the graph next to each edge.

What is the largest number of colors required to color any map, that keeps adjacent regions separate? Four

Creating Graphs from Maps

Revisit the map coloring exercises in terms of graphs. For example, Map I can be represented by the following graph. The graph should include a vertex for each country (or region) in your map. If two countries share a border and need to be colored differently, the graph shows an edge between the vertices that represent them. After studying the relationship between Maps I and the graph for Map I, create a graph that represents Map II.

Revisit the map coloring exercises in terms of graphs. For example, Map I can be represented by the following graph. The graph should include a vertex for each country (or region) in your map. If two countries share a border and need to be colored differently, the graph shows an edge between the vertices that represent them. After studying the relationship between Maps I and the graph for Map I, create a graph that represents Map II.

Revisit the map coloring exercises in terms of graphs. For example, Map I can be represented by the following graph. The graph should include a vertex for each country (or region) in your map. If two countries share a border and need to be colored differently, the graph shows an edge between the vertices that represent them. After studying the relationship between Maps I and the graph for Map I, create a graph that represents Map II.

Restate the Map Coloring problem in terms of a Graph Coloring problem.

You are the publisher of a new edition of the world atlas. As you prepare the different maps for printing, you need to make sure that countries adjacent to each other (sharing a common border) are given different colors.

Color each vertex of the graph in such a way that two vertices sharing an edge receive a different color. Vertices sharing an edge are called adjacent vertices.

The graph for Map II needs three colors. A possible coloring is as follows:

The following are two examples of two colors:

Trees, or graphs with no cycles (paths that loop back to their starting place), can always be colored with two colors (like Graph I).

Also, graphs that look like n-gons where n is even, like the 4-gon (or square).

Note: If n is odd, alternating colors as you go around the polygon does not yield a two- coloring of the graph.

These simple examples can further be combined to create more complex two-color graphs. For example, an edge could be added to connect any tree like Graph I to a two-color n-gon like Graph II. Also, you could add more copies of the square to the right and bottom of the original 4-gon to create a grid pattern. This is also two-colorable.

If a graph can be drawn without any intersecting edges, it represents a map.

The chromatic number of a graph is the minimum number of colors needed to color each vertex in such a way that any two vertices sharing an edge are a different color.

[CC BY-NC-SA 4.0] UNLESS OTHERWISE NOTED | IMAGES: LICENSED AND USED ACCORDING TO TERMS OF SUBSCRIPTION - INTENDED ONLY FOR USE WITHIN LESSON.