\(\sigma\)-polynomials
type: Item
instance of: scholarly article
title: \(\sigma\)-polynomials
zbMATH Open document ID: 1049.05037
author: Haicheng Ma
author: Haizhen Ren
published in: Discrete Mathematics
publication date: 2004-08-19T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 2092850
zbMATH Keywords: \(\sigma\)-polynomial
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: chromatic equivalence, bipartite complement
reviewed by: Gabriel Semanišin
MaRDI profile type: Publication
full work available at URL: j.disc.2004.02.014
OpenAlex ID: W4206485160
cites work: Q5422499
cites work: Expansions of Chromatic Polynomials and Log-Concavity
cites work: Location of Zeros of Chromatic and Related Polynomials of Graphs
cites work: \(\sigma\)-polynomials and graph coloring
cites work: The partition polynomial of a finite set system
DOI: 10.1016/J.DISC.2004.02.014
description: scientific article; zbMATH DE number 2092850