DP color functions versus chromatic polynomials.

For any graph G , the chromatic polynomial of G is the function P (G , m) which counts the number of proper m -colorings of G for each positive integer m. The DP color function P D P (G , m) of G , introduced by Kaul and Mudrock in 2019, is a generalization of P (G , m) with P D P (G , m) ≤ P (G , m) for each positive integer m. Let P D P (G) ≈ P (G) (resp. P D P (G) < P (G)) denote the property that P D P (G , m) = P (G , m) (resp. P D P (G , m) < P (G , m)) holds for sufficiently large integers m. It is an interesting problem of finding graphs G for which P D P (G) ≈ P (G) (resp. P D P (G , m) < P (G , m)) holds. Kaul and Mudrock showed that if G has an even girth, then P D P (G) < P (G) and Mudrock and Thomason recently proved that P D P (G) ≈ P (G) holds for each graph G which has a dominating vertex. We shall generalize their results in this article. For each edge e in G , let ℓ (e) = ∞ if e is a bridge of G , and let ℓ (e) be the length of a shortest cycle in G containing e otherwise. We first show that if ℓ (e) is even for some edge e in G , then P D P (G) < P (G) holds. However, the converse statement of this conclusion fails with infinitely many counterexamples. We then prove that P D P (G) ≈ P (G) holds for every graph G that contains a spanning tree T such that for each e ∈ E (G) ∖ E (T) , ℓ (e) is odd and e is contained in a cycle C of length ℓ (e) with the property that ℓ (e ′) < ℓ (e) for each e ′ ∈ E (C) ∖ (E (T) ∪ { e }). Some open problems are proposed in this article. [ABSTRACT FROM AUTHOR]