The Multiorbital Bivariate Chromatic Polynomial

Source abstract

We introduce the multiorbital bivariate chromatic polynomial $F_Γ(G;x,y)=\sum_{H\le G}\frac{1}{|H|}\sum_{h\in H}P_{Γ/h}(x,y)$, which aggregates orbital bivariate chromatic polynomials over the subgroup lattice of a finite group acting on a graph. We derive an equivalent element-wise representation $F_Γ(G;x,y)=\sum_{g\in G}c_G(g)P_{Γ/g}(x,y)$ with $c_G(g)=\sum_{H\le G,\,g\in H}\frac{1}{|H|}$. The coefficient function depends only on the cyclic subgroup generated by the group element and is constant on conjugacy classes. This yields corresponding decompositions by cyclic subgroups and conjugacy classes, as well as a natural Möbius-theoretic interpretation. After normalization, the coefficients define a probability distribution on the acting group, giving a probabilistic interpretation of the multiorbital polynomial as an expected quotient polynomial. We further investigate its behaviour under disjoint unions and its specialization to edgeless graphs, where a weighted cycle-index expression is obtained.