Jesper Torp Kristensen, Peter Bro Miltersen

We present an efficient reduction mapping undirected graphs

G with n = 2^k vertices for integers k

to tables of partially specified Boolean functions

g: {0,1}^(4k+1) -> {0,1,*} so that for any integer m,

G has a vertex colouring using m colours if and only if g ...
more >>>