Line graph

Pure mathematics

Mathematical physics

Discrete mathematics

Voltage graph

Graph

Mathematics

Invariant (physics)

Combinatorics

Chromatic polynomial

Tutte polynomial

Enumerative Combinatorics and Applications

Given a graph property P, F. Harary introduced in 1985 P-colorings, graph colorings where each color class induces a graph in P. Let χ P (G; k) counts the number of P-colorings of G with at most k colors.It turns out that χ P (G; k) is a polynomial in Z[k] for each graph G. Graph polynomials of this form are called Harary polynomials.In this paper we investigate properties of Harary polynomials and compare them with properties of the classical chromatic polynomial χ(G; k).We show that the characteristic and the Laplacian polynomial, the matching, the independence and the domination polynomials are not Harary polynomials.We show that for various notions of sparse, non-trivial properties P, the polynomial χ P (G; k) is, in contrast to χ(G; k), not a chromatic, and even not an edge elimination invariant.Finally, we study whether the Harary polynomials are definable in monadic second-order Logic.

Harary polynomials