An introduction to the k-defect polynomials

Abstract

The 0-defect polynomial of a graph is just the chromatic polynomial. This polynomial has been widely studied in the literature. Yet little is known about the properties of k-defect polynomials of graphs in general, when 0 < k ≤ |E(G)|. In this survey we give some properties of k-defect polynomials, in particular we highlight the properties of chromatic polynomials which also apply to k-defect polynomials. We discuss further research which can be done on the k-defect polynomials.

Mathematics Subject Classification (2010): 05C15, 05C31.

Keywords: Chromatic polynomial, k-defect polynomial, tutte polynomial, coboundary polynomial