Equivalence of edge bicolored graphs on surfaces (Q1753027)

In this work, the authors count the number of equivalence classes of edge bicolorings of a graph that is cellulary embedded in an orientable surface under two relations: reversing colors around a face and reversing colors around a vertex, which are automorphisms. As they remark, this is well studied in the case of the plane, but for other surfaces, the computation is more subtle. While this question can be stated purely graph theoretically, it has interesting applications in knot theory. The authors give their explanations by means of two graphs embedded in a torus, which is the easiest non-planar surface. In Section 3, they use the Bollobás-Riordan-Tutte (BRT) polynomial to obtain the number of components of the medial graph. In Section 4, they discuss the case of plane graphs.