Bounds for mean colour numbers of graphs
type: Item
instance of: scholarly article
title: Bounds for mean colour numbers of graphs
zbMATH Open document ID: 1027.05041
DOI: 10.1016/S0095-8956(02)00023-0
author: D. Massart
published in: Journal of Combinatorial Theory. Series B
publication date: 2003-08-25T00:00:00Z
review text: Let \(G\) be a graph of order \(n\). For any \(n\)-colouring \(C\) of \(G\) let \(\ell(C)\) denote the actual number of colours used. By the mean colour number \(\mu(G)\) of \(G\) we mean the average of the \(\ell(C)\)'s over all \(n\)-colourings of \(C\). It is shown that if \(H\) is a subgraph of \(G\), then \(\mu(H)\leq \mu(G)\) under the condition that either \(G\) is a chordal graph or \(H\) is a graph which can be obtained from a tree by replacing a vertex by a clique. This result gives a method to find upper bounds and lower bounds for the mean colour number of any graph. Some unsolved problems are proposed, too.
reviewed by: Jozef Fiamčík
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1970696
zbMATH Keywords: chromatic polynomial
MaRDI profile type: Publication
cites work: The Markov chain of colourings
cites work: Q4003555
cites work: Proof of a chromatic polynomial conjecture
cites work: Some inequalities on chromatic polynomials
cites work: Removing Edges Can Increase the Average Number of Colours in the Colourings of a Graph
cites work: Q3819084
cites work: Graph minors. III. Planar tree-width
full work available at URL: s0095-8956(02)00023-0
OpenAlex ID: W2135081210
Recommended article: Bounds for the chromatic number of a graph
Recommended article: Q5121928
Recommended article: Upper bounds on the average number of colors in the non-equivalent colorings of a graph
Recommended article: Colouring graphs with bounded generalized colouring number
Recommended article: Mean color numbers of some graphs
Recommended article: Further results on the lower bounds of mean color numbers
Recommended article: Lower bounds and properties for the average number of colors in the non-equivalent colorings of a graph
Recommended article: Bounded vertex colorings of graphs
Recommended article: An upper bound for total colouring of graphs
Recommended article: A new upper bound for total colourings of graphs
description: scientific article; zbMATH DE number 1970696