Search

For any connected graph G $G$, let P(G,m) $P(G,m)$ and PDP(G,m) ${P}_{DP}(G,m)$ denote the chromatic polynomial and Dvořák and Postle (DP) color function of G $G$, respectively. It is known that PDP(G,m)≤P(G,m) ${P}_{DP}(G,m)\le P(G,m)$ holds for every positive integer m $m$. Let DP≈ $D{P}_{\approx }$ (resp., DP< $D{P}_{\lt }$) be the set of graphs G $G$ for which there exists an integer M $M$ such that PDP(G,m)=P(G,m) ${P}_{DP}(G,m)=P(G,m)$ (resp., PDP(G,m)

Let G = (V , E) be a simple graph with n vertices and m edges, P (G , k) be the chromatic polynomial of G , and P (G , L) be the number of L -colorings of G for any k -assignment L. In this article, we show that when k ≥ m − 1 ≥ 3 , P (G , L) − P (G , k) is bounded below by ((k − m + 1) k n − 3 + (k − m + 3) c 3 k n − 5) ∑ u v ∈ E | L (u) ∖ L (v) | , where c ≥ (m − 1) (m − 3) 8 , and in particular, if G is K 3 -free, then c ≥ ( m − 2 2 ) + 2 m − 3. Consequently, P (G , L) ≥ P (G , k) whenever k ≥ m − 1. [ABSTRACT FROM AUTHOR]

For any r -uniform hypergraph H with m (≥2) edges, let P (H , k) and P l (H , k) be the chromatic polynomial and the list-color function of H respectively, and let ρ (H) denote the minimum value of | e ∖ e ′ | among all pairs of distinct edges e , e ′ in H. We will show that if r ≥ 3 , ρ (H) ≥ 2 and m ≥ ρ (H) 3 2 + 1 , then P l (H , k) = P (H , k) holds for all integers k ≥ 2.4 (m − 1) ρ (H) log ⁡ (m − 1). [ABSTRACT FROM AUTHOR]

The chromatic polynomial P(G,x) of a graph G of order n can be expressed as ∑i=1n(−1)n−iaixi, where ai is interpreted as the number of broken‐cycle‐free spanning subgraphs of G with exactly i components. The parameter ϵ(G)=∑i=1n(n−i)ai∕∑i=1nai is the mean size of a broken‐cycle‐free spanning subgraph of G. In this article, we confirm and strengthen a conjecture proposed by Lundow and Markström in 2006 that ϵ(Tn)<ϵ(G)<ϵ(Kn) holds for any connected graph G of order n which is neither the complete graph Kn nor a tree Tn of order n. The most crucial step of our proof is to obtain the interpretation of all ai's by the number of acyclic orientations of G. [ABSTRACT FROM AUTHOR]

Let G=(V,E) be a simple graph with V={1,2,...,n} and χ(G,x) be its chromatic polynomial. For an ordering π=(v1,v2,...,vn) of elements of V, let δG(π) be the number of integers i, where 1≤i≤n−1, with either vi

In this paper, we present some properties on chromatic polynomials of hypergraphs which do not hold for chromatic polynomials of graphs. We first show that chromatic polynomials of hypergraphs have all integers as their zeros and contain dense real zeros in the set of real numbers. We then prove that for any multigraph G = ( V , E ) , the number of totally cyclic orientations of G is equal to the value of | P ( H G , − 1 ) | , where P ( H G , λ ) is the chromatic polynomial of a hypergraph H G which is constructed from G . Finally we show that the multiplicity of root “ 0 ” of P ( H , λ ) may be at least 2 for some connected hypergraphs H , and the multiplicity of root “ 1 ” of P ( H , λ ) may be 1 for some connected and separable hypergraphs H and may be 2 for some connected and non-separable hypergraphs H . [ABSTRACT FROM AUTHOR]

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]

A mixed hypergraph H is a triple (X , C , D) , where X is a finite set and each of C and D is a family of subsets of X. For any positive integer λ , a proper λ -coloring of H is an assignment of λ colors to vertices in H such that each member in C contains at least two vertices assigned the same color and each member in D contains at least two vertices assigned different colors. The chromatic polynomial of H is the graph-function counting the number of distinct proper λ -colorings of H whenever λ is a positive integer. In this article, we show that chromatic polynomials of mixed hypergraphs under certain conditions are zero-free in the intervals (− ∞ , 0) and (0 , 1) , which extends known results on zero-free intervals of chromatic polynomials of graphs and hypergraphs. [ABSTRACT FROM AUTHOR]

In this paper, we prove that (− ∞ , 0) is a zero-free interval for chromatic polynomials of a family L 0 of hypergraphs and (0 , 1) is a zero-free interval for chromatic polynomials of a subfamily L 0 ′ of L 0 of hypergraphs. These results extend known results on zero-free intervals of chromatic polynomials of graphs and hypergraphs. [ABSTRACT FROM AUTHOR]