I am not an expert on Chromatic polynomials, Tutte polynomials, etc., but a I understand it these graph polynomials tell how many colorings of a certain type the graph has, but do not compute specific colorings. Of course it may be useful to know when no coloring exists. However, they are difficult to compute for large graphs. There has I think been some work on computing Tutte polynomials for defective colorings.
