Graph 3-Coloring on the Invisible Graph

This presentation will explore an activity paradigm for engaging with computational problems in a way that is efficient with respect to set up costs. For the featured example of graph three coloring, one begins with just having some number of people standing around. Each person then secretly chooses two neighbors. This creates an invisible graph, with each person monitoring a small part, but without the entire graph being visible to anybody. The people are the vertices, and each vertex is asked to choose a color
(one of three) acted out dramatically. Each edge is being monitored by somebody, and if the coloring is not proper then people will have to choose new colors, independently. 

Besides engaging with combinatorial optimization, this activity engages with distributed computation, which is a very important topic in modern computing. Similarly, there could be activities based on different problems than graph three coloring. 

An open research question concerns the edge density for the best invisible 3-coloring. If every vertex has degree 2, then it is too simple.

Corresponding Authors: Mike Fellows and Fran Rosamond
Affiliation of corresponding author: Institute for Informatics, University of Bergen, Norway
Time frame: 30 minutes