Symmetry conjecture for graphs with edge-disjoint cycles

The conjecture is false, already for a connected graph with six vertices and just one cycle.

In Colmenarejo and Klein, Conjecture 3.14, the function in question is

$$\begin{aligned} T_G(\mathbf x;q)&= \sum_{\gamma\in\Gamma(G)}\sum_{\kappa\text{ proper}}\\ &\qquad q^{\operatorname{asc}_{\gamma}(\kappa)} \prod_{v\in V(G)}x_{\kappa(v)}, \end{aligned}$$

where $\Gamma(G)$ consists of all acyclic orientations, $\kappa$ is a proper coloring by positive integers, and an oriented edge $u\to v$ is an ascent when $\kappa(u)<\kappa(v)$. We use this orientation sum, not the distinct variant that sums over vertex labelings.

Take $V(G)=\{1,2,3,4,5,6\}$ and

$$E(G)=\{12,23,34,41,15,26\}.$$

Here $uv$ denotes the undirected edge $\{u,v\}$. Thus $1,2,3,4$ form a four-cycle, and $5,6$ are leaves attached to $1,2$, respectively. The only cycle is the four-cycle, so the hypothesis that no two cycles share an edge is satisfied.

We will prove

$$\begin{aligned} [q\,x_1x_2x_3^2x_4^2]T_G&=374,\\ [q\,x_1x_2^2x_3x_4^2]T_G&=376. \end{aligned}$$

These two monomials are interchanged by $x_2\leftrightarrow x_3$, so the unequal coefficients disprove symmetry.

1. Counting orientations with one ascent

For a proper coloring $\kappa$, let $a(\kappa)$ be the number of ascents around the fixed direction

$$1\longrightarrow2\longrightarrow3\longrightarrow4\longrightarrow1.$$

Among all orientations of the six edges, exactly six have one ascent: choose the ascending edge, and orient each other edge from its larger-colored endpoint to its smaller-colored endpoint.

An orientation is cyclic precisely when the four-cycle is coherently directed. Therefore, among those six orientations, exactly one must be discarded if $a(\kappa)=1$ or $a(\kappa)=3$, and none otherwise. In the discarded orientation both leaf edges point in the descending direction. Consequently, for a fixed color multiplicity profile, its coefficient at $q$ is

$$6N-N_1-N_3,$$

where $N$ counts proper colorings with that profile and $N_j$ counts those with $a(\kappa)=j$.

2. The number of proper colorings

For either profile, $N=64$. It suffices to count the profile $(1,1,2,2)$, in which colors $3,4$ occur twice: swapping colors $2,3$ gives a bijection to the other profile.

If the four cycle colors are distinct, the two leaf colors must be $3,4$. For either ordering of these leaf colors, inclusion-exclusion gives $24-6-6+2=14$ permissible cycle permutations. This contributes $28$.

If exactly three cycle colors occur, the repeated color is either $3$ or $4$ and occupies opposite vertices. Fix that repeated color. If the other doubled color is absent from the cycle, there are four cycle arrangements, each with one leaf extension. Otherwise, one of colors $1,2$ is absent. For each of these two choices there are four cycle arrangements: two have one leaf extension and two have two leaf extensions. This contributes

$$2\bigl(4+(2+4)+(2+4)\bigr)=32.$$

If exactly two cycle colors occur, they must be the alternating colors $3,4$. There are two cycle arrangements and two orders for leaf colors $1,2$, contributing $4$. Thus $N=28+32+4=64$.

3. The exceptional cycle colorings

If a color repeats on the four-cycle, it repeats at opposite vertices. Each two-edge route between those vertices has one ascent and one descent, so $a(\kappa)=2$.

Thus $a(\kappa)=3$ requires all four colors to be distinct. The ordered cycle colors $(\kappa(1),\kappa(2),\kappa(3),\kappa(4))$ must be one of the four cyclic rotations of $(1,2,3,4)$. The following table lists every possible leaf-color pair $(\kappa(5),\kappa(6))$ for these rotations.

Cycle colors	Profile $(1,1,2,2)$	Profile $(1,2,1,2)$
$(1,2,3,4)$	$(3,4)$ or $(4,3)$	$(2,4)$
$(2,3,4,1)$	$(3,4)$	$(4,2)$
$(3,4,1,2)$	$(4,3)$	$(4,2)$
$(4,1,2,3)$	$(3,4)$	$(2,4)$

Hence $N_3=5$ for the first profile and $N_3=4$ for the second.

The graph automorphism $(1\ 2)(3\ 4)(5\ 6)$ reverses the direction of the four-cycle and preserves each color multiplicity profile. It takes $a(\kappa)$ to $4-a(\kappa)$, so $N_1=N_3$ for each profile.

The two coefficients are therefore

$$\begin{aligned} 6\cdot64-5-5&=374,\\ 6\cdot64-4-4&=376. \end{aligned}$$

They are different. Thus $T_G(\mathbf x;q)$ is not symmetric, although $G$ has only one cycle, disproving Conjecture 3.14.