Let's Color

Learning Resource Type

Learning Activity

Overview

Students will color the vertices of a network/graph using as many colors as possible and as few colors as possible.  

Phase

Before/Engage
Mathematics (2019) Grade(s): 09-12 - Applications of Finite Mathematics

MA19.FM.19

Use vertex-coloring, edge-coloring, and matching techniques to solve application-based problems involving conflict.

UP:MA19.FM.19

Vocabulary

  • Vertex coloring
  • Matching techniques
  • Conflict graphs
  • Adjacent edges
  • Adjacent vertices
  • Odd wheel graph
  • Proper coloring

Knowledge

Students know:

  • Graphing procedures and properties.

Skills

Students are able to:

  • Model application-based problems that may be solved using graph colorings.
  • Color the edges or vertices of a graph using the least number of colors so that no two adjacent vertices or edges are colored the same.
  • Interpret the coloring of the graph in terms of a solution for an application-based problem, such as scheduling committee meetings (vertex colorings) or class scheduling (edge-colorings).
  • Identify structures in a graph that require a minimum number of colors for a proper coloring.

Understanding

Students understand that:

  • -Techniques are used to minimize colors needed to color the vertices (edges) of a graph so that no two adjacent vertices (edges) are colored the same. -Real-world problems such as scheduling and conflict can be modeled with graphs and solved using the minimization of the number of colors.

Body

  1. Use vertex-coloring, edge-coloring, and matching techniques to solve application-based problems involving conflict.
    Examples: Use graph-coloring techniques to color a map of the western states of the United States so that no adjacent states are the same color, determining the minimum number of colors needed and why no fewer colors may be used; use vertex colorings to determine the minimum number of zoo enclosures needed to house ten animals given their cohabitation constraints; use vertex colorings to develop a time table for scenarios such as scheduling club meetings or for housing hazardous chemicals that cannot all be safely stored together in warehouses.

Learning Objectives

Students should be able to identify the chromatic number of a simple graph.

Activity Details

1. Share the Google Slide "Let's Color" with the students and direct them to open the document.

2. Instruct the students to follow the prompts to color the vertices of the graph in three different ways.

3. Remind students to refer to the definition for proper coloring presented at the top of the slide.

4. The students should share the document with the teacher and the teacher should check the responses and clear up any misconceptions.

Assessment Strategies

Once the students share their responses, the teacher can assess the students' answers. The teacher should correct the students' mistakes or misunderstandings.

Variation Tips

The Google Slide can be downloaded as a PDF, printed, and distributed to the students as a paper copy.  Please provide colored pencils for the student to use if a paper copy is used. 

Background / Preparation

The teacher will need to ensure the classroom has the following:

1) internet connection (WiFi).

2) classroom set of computers, iPads, or smart devices. (If allowed students can use their own personal devices.)

Prior to the lesson, the teacher should share the google slide "Let's Color" with the students.

The teacher should also preview the slide to anticipate problems or misconceptions.

ALSDE LOGO