Search

In 2018, Dvořák and Postle introduced a generalization of proper coloring, the so‐called DP‐coloring. For any graph G $G$, the DP‐chromatic number χDP(G) ${\chi }_{DP}(G)$ of G $G$ is defined analogously with the chromatic number χ(G) $\chi (G)$ of G $G$. In this article, we show that χDP(G∨Ks)=χ(G∨Ks) ${\chi }_{DP}(G\vee {K}_{s})=\chi (G\vee {K}_{s})$ holds for s=4(χ(G)+1)|E(G)|2χ(G)+1 $s=\unicode{x02308}\frac{4(\chi (G)+1)|E(G)|}{2\chi (G)+1}\unicode{x02309}$, where G∨Ks $G\vee {K}_{s}$ is the join of G $G$ and a complete graph with s $s$ vertices. As a result, ZDP(n)≤n2−(n+3)∕2 ${Z}_{DP}(n)\le {n}^{2}-(n+3)\unicode{x02215}2$ holds for every integer n≥2 $n\ge 2$, where ZDP(n) ${Z}_{DP}(n)$ is the minimum nonnegative integer s $s$ such that χDP(G∨Ks)=χ(G∨Ks) ${\chi }_{DP}(G\vee {K}_{s})=\chi (G\vee {K}_{s})$ holds for every graph G $G$ with n $n$ vertices. Our result improves the best current upper bound 1.5n2 $1.5{n}^{2}$ of ZDP(n) ${Z}_{DP}(n)$ due to Bernshteyn, Kostochka, and Zhu. [ABSTRACT FROM AUTHOR]

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)

In 2013, Ku and Wong showed that for any partitions μ and μ ′ of a positive integer n with the same first part u and the lexicographic order μ ◃ μ ′ , the eigenvalues ξ μ and ξ μ ′ of the derangement graph Γ n have the property | ξ μ | ≤ | ξ μ ′ | , where the equality holds if and only if u = 3 and all other parts are less than 3. In this article, we obtain an analogous conclusion on the eigenvalues of the perfect matching derangement graph M 2 n of K 2 n by finding a new recurrence formula for the eigenvalues of M 2 n. [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]

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

For a bridgeless graph G, its flow polynomial is defined to be the function F(G,q), which counts the number of nonwhere‐zero Γ‐flows on an orientation of G whenever q is a positive integer and Γ is an additive Abelian group of order q. It was introduced by Tutte in 1950, and the locations of zeros of this polynomial have been studied by many researchers. This paper gives a survey on the results and problems on the study of real zeros of flow polynomials. [ABSTRACT FROM AUTHOR]

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]