Daniel Cranston's Python

I work in discrete mathematics, mainly in structural graph theory and graph coloring. I write Python code for some of my research, and below are a few Jupyter notebooks that may be useful to others. The code is also available on GitHub.

Jupyter Notebooks

• Equitable Colorings
  
  Algorithms for equitable colorings of sparse graphs, including computational experiments related to my paper Equitably Coloring Planar and Outerplanar Graphs with Reem Mahmoud. Our work in that paper requires us to acyclically color planar graphs. So along the way we implement a fast algorithm for acyclically 7-coloring any planar graph, based on an old result of Albertson and Berman; this may be of independent interest.
  
  
• Correspondence Packing
  
  Algorithms for 5-choosability of planar graphs and packing 3 correspondence colorings, given any K₅-minor free graph and a correspondence 6-cover. Includes a nice visualization for converting Thomassen's proof to a coloring algorithm that is very efficient! Related to Disjoint Correspondence Colorings for K₅-Minor-free Graphs by Wouter Cames van Batenburg, Daniel W. Cranston, and František Kardoš.
  
  
• Sparse Recoloring
  
  Algorithms for reconfiguration of list-colorings in sparse graphs. Based on the paper List-Recoloring of Sparse Graphs, by Daniel W. Cranston. Given a graph G, list assignment L, and L-colorings α,β, a reconfiguration sequence transforms α to β by recoloring one vertex at a time, so that each intermediate coloring is also a proper L-coloring. A key tool for growing a reconfiguration sequence for G − v to one for G is the so-called Extension Lemma, which we implement here. A naive implementation runs in time Θ(n²). But by using a custom type of treap as our data structure, we reduce this to time O(nlog n). This allows us to handle much larger graphs. Based on this technical advance, we implement two key results from the paper, and test them on large graphs.