The Vertex Coloring Algorithm

We present a new polynomial-time algorithm for finding proper m-colorings of the vertices of a graph. We prove that every graph with n vertices and maximum vertex degree must have chromatic number (G) less than or equal to +1 and that the algorithm will always find a proper m-coloring of the vertices of G with m less than or equal to +1. Furthermore, we prove that this condition is the best possible in terms of n and by explicitly constructing graphs for which the chromatic number is exactly +1. In the special case when G is a connected simple graph and is neither an odd cycle nor a complete graph, we show that the algorithm will always find a proper m-coloring of the vertices of G with m less than or equal to . In the process, we obtain a new constructive proof of Brooks ' famous theorem of 1941. For all known examples of graphs, the algorithm finds a proper m-coloring of the vertices of the graph G for m equal to the chromatic number (G). In view of the importance of the P versus NP question, we ask: does there exist a graph G for which this algorithm cannot find a proper m-coloring of the vertices of G with m equal to the chromatic number (G)? The algorithm is demonstrated with several examples of famous graphs, including a proper four-coloring of the map of India and two large Mycielski benchmark graphs with hidden minimum vertex colorings. We implement the algorithm in C++ and provide a demonstration program fo