An investigation of several branching functions in a branch and bound algorithm for the chromatic number problem.
Ronald R. Rautenberg · Defense Technical Information Center (DTIC) · 1980
The chromatic number problem is to determine the minimum number of colors to assign to the vertices of a graph such that no connected vertices are assigned the same color. This paper presents a branch and bound solution to the chromatic number problem and investigates five different branching functions. Additionally, a method of coloring very sparse graphs is presented which divides a graph into biconnected components and reduces the time required to color the graph. (Author)