A randomised heuristical algorithm for estimating the chromatic number of a graph (Q1262784)

We define a class of randomised heuristical algorithms for colouring the vertices of a graph. The problem of graph colouring is known to be NP- complete unless a graph is bipartite. If \(P\neq NP\), then an algorithm for solving an NP-complete or NP-hard problem runs in time which is not bounded by a polynomial function of the problem size. This is the reason for the search of heuristic approaches, which may give (practically) usable results in reasonable time also for larger instances of a particular NP-hard problem. We propose some generalizations of the antivoter algorithm and in this way define a class of algorithms. The essential difference between the original and our algorithms is that our algorithms instead of answering the decision problem: ``Is given graph G k-colourable?'' rather give an estimate for an upper bound of \(\chi\) (G), the chromatic number of G. Comparative experiments led us to believe that for suitably tuned parameters this can be achieved in a time comparable with the time which is needed for the antivoter algorithm. On the other hand, if we try to estimate \(\chi\) (G) with the antivoter algorithm, we would probably need more time. First, we need a reliable upper bound for \(\chi\) (G), say \(u\geq \chi (G)\). Then we repeatedly run the antivoter algorithm with the number of colours u, u-1, u-2, etc. until one of the runs will give a negative answer. We outline a (surprisingly) elementary proof of a kind of weak convergence property that holds for our algorithms. We prove that there is a positive probability to find a \(\chi\) (G)-colouring in finitely many steps with our algorithms. Moreover, it does not matter with which colouring we start. In other words, no initial colouring is hopeless for our algorithms.