\(\sigma\)-polynomials (Q1877681): Difference between revisions

If \(G\) is a spanning subgraph of the complete bipartite graph \(K_{n,n}\) then \(G^c\) denotes the complement of \(G\) (in the usual sense) and \(\overline{G}\) stands for the complement of \(G\) in \(K_{n,n}\) (called the {bipartite complement of \(G\)}). The {\(\sigma\)-polynomial} of \(G^c\) is defined as \(\sigma(G^c,x)=\sum_{i=1}^n a_i x^i\), where \(a_i\) is the number of distinct ways of partitioning \(V(G^c)\) into \(i\) colour classes (i.e. independent sets). Two graphs \(G\) and \(H\) are called chromatically equivalent if \(\sigma(G,x)=\sigma(H,x)\). Using a recurrent and integral formula for \(a_i\) it is shown that there is a formula relating \(G^c\) to \(\overline{G}^c\) in the following manner: If \(G,H\) are two spanning subgraphs of \(K_{n,n}\), then \(G^c\) and \(H^c\) are chromatically equivalent if and only if \(\overline{G}^c\) and \(\overline{H}^c\) are chromatically equivalent.