{"product_id":"the-vertex-coloring-algorithm-ashay-dharwadker-9781466391321","title":"The Vertex Coloring Algorithm","description":"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 Delta must have chromatic number Chi(G) less than or equal to Delta+1 and that the algorithm will always find a proper m-coloring 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 m-coloring 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 m-coloring 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 m-coloring 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 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 for Microsoft Windows.\u003cbr\u003e\u003cbr\u003e\u003cb\u003eAuthor:\u003c\/b\u003e Ashay Dharwadker\u003cbr\u003e\u003cb\u003eISBN-10:\u003c\/b\u003e 1466391324\u003cbr\u003e\u003cb\u003eISBN-13:\u003c\/b\u003e 9781466391321\u003cbr\u003e\u003cb\u003ePublisher:\u003c\/b\u003e Createspace Independent Publishing Platform\u003cbr\u003e\u003cb\u003eLanguage:\u003c\/b\u003e English\u003cbr\u003e\u003cb\u003ePublished:\u003c\/b\u003e 10\/02\/2011\u003cbr\u003e\u003cb\u003ePages:\u003c\/b\u003e 54\u003cbr\u003e\u003cb\u003eFormat:\u003c\/b\u003e Paperback\u003cbr\u003e\u003cb\u003eWeight:\u003c\/b\u003e 0.33lbs\u003cbr\u003e\u003cb\u003eSize:\u003c\/b\u003e 11.00h x 8.50w x 0.14d","brand":"Ashay Dharwadker","offers":[{"title":"Paperback","offer_id":48217377767679,"sku":"9781466391321","price":17.0,"currency_code":"USD","in_stock":true}],"thumbnail_url":"\/\/cdn.shopify.com\/s\/files\/1\/0662\/2982\/9887\/files\/img_ed0cd9ec-5e3a-4feb-9cc0-2e407b11fd6b.jpg?v=1771996839","url":"https:\/\/www.whiterainbookhouse.com\/products\/the-vertex-coloring-algorithm-ashay-dharwadker-9781466391321","provider":"WR Book House","version":"1.0","type":"link"}