Let be a Field.
Let be a graph on vertices.
The graph polynomial is defined as
Lemma
Let .
Let be a Graph on
Then is -List Colourable if and only if
for some .
Lemma
Let be a Graph on vertices.
Then is -colourable
if and only if
The graph polynomial is not in the Ideal generated by
for
Proof
Let .
Suppose is in the above Ideal.
Then for all .
Thus is not -colourable.
Suppose is not -colourable.
Then for all .
By Combinatorial Nullstellensatz, we find that is in the above Ideal.