Graph Colorings and Symmetry
Jonathan L. Gross, Jay Yellen, Mark Anderson · 2018
This chapter explores the interplay between a graph&s;s symmetry and the number of different colorings of that graph. If one coloring of a graph can be obtained from another coloring by a simple rotation of the graph, then the two colorings are equivalent. The symmetries of a graph are precisely defined using the graph&s;s automorphism group, along with its vertex- and edge-permutations. The equivalence classes under these group actions determine when colorings are equivalent. The chapter develops the basic mathematical concepts and tools to enumerate these equivalence classes. As the size of the graph and the number of colors increase, it becomes progressively less practical to count orbits by ordinary itemization. However, systematic exploitation of graph symmetries often reduces the work. For a small graph and a small number of colors, it is possible to count the orbits of vertex- and edge-colorings by drawing a list of representatives of classes.