The forced colouring function of a graph
G. E. Farr
Source abstract
The forced colouring function of a graph gives the probability that a random assignment of colours to a random subset of vertices can be extended, by a simple local process called forcing, to give a proper colouring of the whole graph using the same set of available colours. This is a polynomial for each fixed number of colours, and was introduced as a subject for research on the general theory of graph polynomials. In this paper we establish its fundamental properties and give combinatorial interpretations of its derivatives at two particular points. We also prove that the problem of computing its value at any specific point in a certain interval is #P-hard.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.