On the number of precolouring extensions
type: Item
instance of: scholarly article
title: On the number of precolouring extensions
zbMATH Open document ID: 0968.05031
author: Klaus Dohmen
published in: European Journal of Combinatorics
publication date: 2000-12-19T00:00:00Z
review text: A precolouring of a hypergraph \(H\) is a partial mapping of the vertex set of \(H\) into the natural numbers. A colouring of \(H\) is a precolouring that is defined on the entire vertex set of \(H\). A colouring or precolouring is proper if it induces no monochromatic edges apart from loops. The author proves that the number of proper \(\lambda\)-colourings of a hypergraph extending a given proper precolouring agrees with a polynomial \(\lambda\) for any sufficiently large \(\lambda\). He then establishes a generalization of Whitney's broken circuit theorem [see \textit{H. Whitney}, Bull. Am. Math. Soc. 38, 572-579 (1932; Zbl 0005.14602)], by using an improved version of the inclusion-exclusion principle.
reviewed by: Marietjie Frick
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1545621
zbMATH Keywords: precolouring
zbMATH Keywords: hypergraph
zbMATH Keywords: colouring
zbMATH Keywords: Whitney's broken circuit theorem
zbMATH Keywords: inclusion-exclusion principle
MaRDI profile type: Publication
OpenAlex ID: W2054552471
cites work: Q3941433
cites work: Precoloring extension. I: Interval graphs
cites work: A broken-circuits-theorem for hypergraphs
cites work: Q4383383
cites work: An improvement of the inclusion-exclusion principle
cites work: Q4838466
cites work: Precoloring Extension III: Classes of Perfect Graphs
DOI: 10.1006/EUJC.1999.0411
Recommended article: Precoloring Extensions of Brooks' Theorem
Recommended article: A precolouring extension of Vizing's theorem
Recommended article: Q3424784
Recommended article: Extending fractional precolorings
Recommended article: Precoloring extension of co-Meyniel graphs
Recommended article: Extension from precoloured sets of edges
Recommended article: The Generalised Colouring Numbers on Classes of Bounded Expansion
Recommended article: Extending precolorings to circular colorings
Recommended article: Precoloring Extension for 2‐connected Graphs
Recommended article: Precoloring Extension III: Classes of Perfect Graphs
description: scientific article; zbMATH DE number 1545621