Re: Coloring a graph with exact N colors

TOUATI Sid <touati@prism.uvsq.fr>
27 Sep 2005 09:50:19 -0400

          From comp.compilers

Related articles
Coloring a graph with exact N colors dot (tzuchienchiu <at> gmail <dot> com<tzuchien.chiu@gm) (2005-09-22)
Re: Coloring a graph with exact N colors touati@prism.uvsq.fr (TOUATI Sid) (2005-09-27)
Re: Coloring a graph with exact N colors nkavv@skiathos.physics.auth.gr (Uncle Noah) (2005-09-30)
Re: Coloring a graph with exact N colors touati@prism.uvsq.fr (TOUATI Sid) (2005-09-30)
| List of all articles for this month |

From: TOUATI Sid <touati@prism.uvsq.fr>
Newsgroups: comp.compilers
Date: 27 Sep 2005 09:50:19 -0400
Organization: Universite de Versailles Saint-Quentin-en-Yvelines
References: 05-09-084
Keywords: optimize, theory
Posted-Date: 27 Sep 2005 09:50:19 EDT

This is called q-coloring in graph theory (q=N in your message). The
complexity is not exponential as with optimal coloring, but the constant
of the complexity is high (=N!). In practice, N <= 12 is an observed limit.


S


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.