Summer research project 2023

• Advisor: Ewan Davies
• Researcher: Ben Blount

Objectives

• Understand graph coloring concepts such as vertex coloring, list coloring, list packing

• Understand list and correspondence packing through cover graphs

• Use sagemath and python to compute list and correspondence packing numbers

• Investigate list packing numbers of planar graphs

• Understand the 5-color theorem and related results

Study plan

1. Learn list coloring and list packing using resources such wikipedia and the first and second papers on list packing
2. Implement simple algorithms for finding list and correspondence packing numbers with sagemath
3. Use a database of planar graphs and gather data on list and correspondence packing numbers
4. Learn to run code on CSU’s compute cluster

Resources

• The first paper on list packing
• A follow-up paper that follows some interesting further directions, and some code for working with sagemath
• Thomassen’s amazing paper showing that all planar graphs are 5-list-colorable
• Some old code which delves deep into sagemath’s graphs api in C and implements a version of McKay’s “isomorph-free exhaustive generation” algorithm from here that might help us enumerate covers. WARNING, this code was developed for sagemath 7.2(ish) and won’t run unmodified on modern sagemath installations. Too much has changed including Python 2 to 3 and the visibility of important partition refinement functions in Cython code