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 has a consistent ordered binary
decision diagram with at most (2m + 2)n^2 + 4n decision nodes.
From this it follows that the problem of finding a minimum-sized
consistent OBDD for an incompletely specified truth table is
NP-hard and also hard to approximate.