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.
Thanks for the interesting article - can the Tutte polynomial be used to calculate defective vertex colourings?
-- you have earned Featured Contributor Badge
Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!