PreprintarXiv licencearXiv
The forced colouring function of a graph
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.
Related
- A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph
- An upper bound on the number of relevant variables in a bounded degree Boolean function on the Hamming graph
- An explicit bound on the extremal function for complete graph minors
- The List Total Colouring Conjecture is False
- The Partial List Colouring Conjecture is False
BibTeX
@misc{farr2026forced,
title = {{The forced colouring function of a graph}},
author = {G. E. Farr},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17108},
eprint = {2609.17108},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17108},
}
RIS
TY - UNPB
TI - The forced colouring function of a graph
AU - G. E. Farr
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17108
UR - https://arxiv.org/abs/2609.17108
AB - 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.
ER -