\(\sigma\)-polynomials (Q1877681): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 12:53, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(\sigma\)-polynomials |
scientific article |
Statements
\(\sigma\)-polynomials (English)
0 references
19 August 2004
0 references
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.
0 references
\(\sigma\)-polynomial
0 references
chromatic polynomial
0 references
chromatic equivalence, bipartite complement
0 references