Probabilistic analysis of a heuristic graph coloring algorithm
Tsuyoshi Kawaguchi, Hideo Nakano, Yoshiro Nakanishi · Electronics and Communications in Japan (Part I Communications) · 1982
Abstract In this paper a heuristic graph coloring algorithm as applied to random graphs is analyzed theoretically. The result obtained by expanding on the results of [4] is presented first: let x1(n, cnδ−1) be the random variable representing a solution obtained by applying the algorithm to a random n‐vertex graph having edges with probability p(n)=cnδ− (where c is a constant and 1/2≪δ≦1). Also let x1(n, cnδ−1) be the random variable representing the chromatic number of the graph. Then x1(n, cnδ−1)/x*(n, cnδ−1)≦(1+ϵ)2δ/(2δ−1)(pr.) holds. Here ϵ represents a value sufficiently smaller than 1. By contrast, it is important from the practical point of view to find an algorithm that is effective for an arbitrary random n‐vertex graph. In this paper the above‐mentioned algorithm is evaluated using models with p(n)≪ It is found that this algorithm is effective for all n less than N, where InInN is about the same as np(n).