×

Defective chromatic polynomials. (English) Zbl 0955.05040

Summary: The (ordinary) chromatic polynomial enumerates the number of proper vertex colorings of a graph \(G\) using \(k\) colors, where in any proper vertex coloring, the subgraph induced by any monochromatic set of vertices is an independent set. In this article, we consider the generalization to what are called improper, or defective colorings, whereby monochromatic sets of vertices induce subgraphs of maximum degree \(d\), and commence an investigation of the defective chromatic polynomial. Both the standard defective coloring, where \(d\) is constant, and a local version, similar to that suggested by Woodall in [D. Woodall, Pitman Res. Notes Math. Ser. 218, 45-63 (1990; Zbl 0693.05028)] which we term vector defective coloring (where the threshold \(d\) tolerated is specified independently for each vertex) are considered. We produce a generalization of the standard edge-delection recurrence for the chromatic polynomial, for vector defective coloring in the restricted case of \(\{0,1\}\) weights. Several open problems are suggested.

MSC:

05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 0693.05028
PDFBibTeX XMLCite