An Investigation of Several Branching Functions in a Branch and Bound Algorithm for the Chromatic Number Problem

摘要

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)