On the number of precolouring extensions (Q1590211)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the number of precolouring extensions |
scientific article |
Statements
On the number of precolouring extensions (English)
0 references
19 December 2000
0 references
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.
0 references
precolouring
0 references
hypergraph
0 references
colouring
0 references
Whitney's broken circuit theorem
0 references
inclusion-exclusion principle
0 references