List Price:
$17.00
Add to Cart
www.dharwadker.org

The Vertex Coloring Algorithm
Authored by
Ashay Dharwadker
We present a new polynomialtime algorithm for finding proper mcolorings of the vertices of a graph. We prove that every graph with n vertices and maximum vertex degree Delta must have chromatic number Chi(G) less than or equal to Delta+1 and that the algorithm will always find a proper mcoloring of the vertices of G with m less than or equal to Delta+1. Furthermore, we prove that this condition is the best possible in terms of n and Delta by explicitly constructing graphs for which the chromatic number is exactly Delta+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 mcoloring of the vertices of G with m less than or equal to Delta. 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 mcoloring of the vertices of the graph G for m equal to the chromatic number Chi(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 mcoloring of the vertices of G with m equal to the chromatic number Chi(G)? The algorithm is demonstrated with several examples of famous graphs, including a proper fourcoloring 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 for Microsoft Windows.
 Publication Date:
 20111002
 ISBN/EAN13:
 1466391324 / 9781466391321
 Page Count:
 54
 Binding Type:
 US Trade Paper
 Trim Size:
 8.5" x 11"
 Language:
 English
 Color:
 Full Color
 Related Categories:
 Computers / Computer Science
