Forced colouring function measures how local rules extend partial graph colourings
The forced colouring function of a graph
Discrete Mathematics
Summary
Colouring a graph means assigning colors to points so connected points have different colors. The paper looks at a special function that calculates how likely it is to finish a proper coloring from a partial random assignment using simple local rules called forcing. The authors show basic properties of this function, explain what its derivatives mean in simple combinatorial terms, and prove that calculating the function in some cases is very hard. This helps understand both the behavior and the complexity of extending partial colorings in graphs.
What this means in practice
- •For graph algorithm designers: Assess the computational limits when extending partial colourings in graph colouring algorithms.
- •For complexity theorists: Use the hardness result to rule out efficient general algorithms for calculating forced colouring probabilities.
A theory result. No direct application yet.
Authors
G. E. Farr
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.