Proof of minimal colour in vertex colouring problem
in [Theory]
|
Prev: LIVE PROJECTS FOR FINAL YEAR STUDENTS FOR B.E(CSE/ISE/ECE)/M.Tech/BCA/MCA/M.SC/B.SC
Next: Shared Semantics for Dynamic Interface Discovery
From: Joojle on 31 Jan 2008 13:00 I am doing a research about Graph colouring problem. As I known this problem is in NP-Complete, so I want to find the proof that show this problem is np-complete by show it is NP and it has reduce problem in NP problem as the definition said. Any suggestions are welcome where to find it or guideline to let me proof by myself Thank you
From: Esteban Arcaute on 1 Feb 2008 22:42
Graph colouring is one of the original first 21 NP-complete problems (proved by Karp). http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems There is a link to the original paper by Karp there. Esteban "Joojle" <jjlowing(a)gmail.com> wrote in message news:f76749b8-cda2-4269-b2a3-c76769a5b400(a)e25g2000prg.googlegroups.com... >I am doing a research about Graph colouring problem. As I known this > problem is in NP-Complete, so I want to find the proof that show this > problem is np-complete by show it is NP and it has reduce problem in > NP problem as the definition said. > Any suggestions are welcome where to find it or guideline to let me > proof by myself > > Thank you |