Face counting in 3-edge-colored graphs [Source Code]

<p>This C++ program enumerates certain 3-regular 3-edge-colored graphs <i>G</i> on <i>2n</i> vertices. Let the colors of the graph edges be called 1, 2, and 3. A face is a bicolored cycle whose edges alternate between two fixed and distinct colors. Now, consider that the original 3-colored graph <i>G</i> is combined with a perfect matching (pairing) <i>M</i> of its vertices. Assign to <i>M</i> a new color 0 and think of the combination of <i>G</i> and <i>M</i> as a new (3+1)-edge-colored graph. We are particularly interested in the total number of faces with colors (0,1), (0,2) and (0,3). Denote this number by <i>F(M,G)</i>. </p>

<p>The program computes the maximum of <i>F(M,G)</i> over all perfect matchings <i>M</i> on <i>2n</i> vertices, and identifies those graphs <i>G</i> where this maximum is <i><span>≤</span> 3n/2</i>. For <i>n <span>≤ </span>9</i>, this happens only for <i>n=8</i>.
It also counts the number of 3-edge-colored maximally single-trace graphs, i.e., edge-colored graphs with a single face for each pair of colors. </p>

<p>This is relevant to the research on random tensors. In this context, the 3-edge-colored graphs encode tensor model observables (trace invariants). The face counting is relevant for determining the expectation value of these observables, and crucially their scaling with the size N of the tensors.</p>

</p>The program only scans 3-edge colored-graphs that have a single face for one pair of colors<span>—</span>say colors (1,2): The vertices are labeled 0,1, ..., 2n-1. Color 1 is fixed to: {0,1} {2,3} ... {2n-2,2n-1}; color 2 is fixed to: {1,2} {3,4} ... {2n-1,0}; and only color 3 is varied.
It uses the nauty library (McKay, B.D. and Piperno, A., "Practical Graph Isomorphism, II", Journal of Symbolic Computation, 60 (2014), pp. 94-112. <a href="https://doi.org/10.1016/j.jsc.2013.09.003">doi:10.1016/j.jsc.2013.09.003</a>. <a href="https://pallini.di.uniroma1.it">https://pallini.di.uniroma1.it</a>) to identify isomorphic graphs. This significantly reduces redundant work for larger <i>n</i>. </p>

<p>For more details, see the related publication. For usage instructions, see the readme file.</p>