Complete the subtree rooted under CHROMATIC NUMBERS in Karp's 21 problems - Githubissues

wimmers / poly-reductions

Polynomial-time reductions in Isabelle/HOL

2 stars 13 forks source link

Complete the subtree rooted under CHROMATIC NUMBERS in Karp's 21 problems #3

Open wimmers opened 4 years ago

wimmers commented 4 years ago

This includes the reduction 3-SAT <= Chromatic numbers. The tree can be found here: https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems