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.
General
Is the information for this product incomplete, wrong or inappropriate?
Let us know about it.
Does this product have an incorrect or missing image?
Send us a new image.
Is this product missing categories?
Add more categories.
Review This Product
No reviews yet - be the first to create one!
Welcome to Loot.co.za!
Sign in / Register |Wishlists & Gift Vouchers |Help | Advanced search
