On partial sums of chromatic polynomials
type: Item
instance of: scholarly article
zbMATH Open document ID: 0977.05049
author: Klaus Dohmen
publication date: 2001-12-17T00:00:00Z
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1682806
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: Bonferroni inequality
zbMATH Keywords: graph coloring
MaRDI profile type: Publication
title: On partial sums of chromatic polynomials
published in: Ars Combinatoria
review text: Inequalities of the Bonferroni type are proved for \(P_{G}(\lambda)\), the chromatic polynomial of the graph \(G\). If \(P_{G}(\lambda)=\lambda ^n+a_1\lambda ^{n-1}+\cdots +a_n\) (\(n\) is the number of vertices of \(G\) and \(P_{G}(\lambda)\) is defined, of course, as the number of the proper vertex colorings of \(G\) by the colors \(\{1,2,\ldots ,\lambda \}\)) and \(\lambda \) is a positive integer, then \(P_{G}(\lambda)\leq \lambda ^n+a_1\lambda ^{n-1}+\cdots +a_q\lambda ^{n-q}\) for each even \(q\) such that \(0\leq q\leq n\). For odd \(q\) the opposite inequality holds.
reviewed by: Martin Klazar
description: scientific article; zbMATH DE number 1682806