Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProperties of chromatic polynomials of hypergraphs not held for chromatic polynomials of graphs
122
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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,-1)|$, where $P(H,lambda)$ is the chromatic polynomial of a hypergraph $H$ which is constructed from $G$. Finally we show that the multiplicity of root $0$ of $P(H,lambda)$ may be at least $2$ for some connected hypergraphs $H$, and the multiplicity of root $1$ of $P(H,lambda)$ may be $1$ for some connected and separable hypergraphs $H$ and may be $2$ for some connected and non-separable hypergraphs $H$.
rate research
Read More
Motivated by the study of Macdonald polynomials, J. Haglund and A. Wilson introduced a nonsymmetric polynomial analogue of the chromatic quasisymmetric function called the emph{chromatic nonsymmetric polynomial} of a Dyck graph. We give a positive expansion for this polynomial in the basis of fundamental slide polynomials using recent work of Assaf-Bergeron on flagged $(P,rho)$-partitions. We then derive the known expansion for the chromatic quasisymmetric function of Dyck graphs in terms of Gessels fundamental basis by taking a backstable limit of our expansion.
J. Makowsky and B. Zilber (2004) showed that many variations of graph colorings, called CP-colorings in the sequel, give rise to graph polynomials. This is true in particular for harmonious colorings, convex colorings, mcc_t-colorings, and rainbow colorings, and many more. N. Linial (1986) showed that the chromatic polynomial $chi(G;X)$ is #P-hard to evaluate for all but three values X=0,1,2, where evaluation is in P. This dichotomy includes evaluation at real or complex values, and has the further property that the set of points for which evaluation is in P is finite. We investigate how the complexity of evaluating univariate graph polynomials that arise from CP-colorings varies for different evaluation points. We show that for some CP-colorings (harmonious, convex) the complexity of evaluation follows a similar pattern to the chromatic polynomial. However, in other cases (proper edge colorings, mcc_t-colorings, H-free colorings) we could only obtain a dichotomy for evaluations at non-negative integer points. We also discuss some CP-colorings where we only have very partial results.
We establish a set of recursion relations for the coefficients in the chromatic polynomial of a graph or a hypergraph. As an application we provide a generalization of Whitneys broken cycle theorem for hypergraphs, as well as deriving an explicit formula for the linear coefficient of the chromatic polynomial of the $r$-complete hypergraph in terms of roots of the Taylor polynomials for the exponential function.
The Euler characteristic of a semialgebraic set can be considered as a generalization of the cardinality of a finite set. An advantage of semialgebraic sets is that we can define negative sets to be the sets with negative Euler characteristics. Applying this idea to posets, we introduce the notion of semialgebraic posets. Using negative posets, we establish Stanleys reciprocity theorems for order polynomials at the level of Euler characteristics. We also formulate the Euler characteristic reciprocities for chromatic and flow polynomials.
The purpose of this paper is twofold. Firstly, we generalize the notion of characteristic polynomials of hyperplane and toric arrangements to those of certain abelian Lie group arrangements. Secondly, we give two interpretations for the chromatic quasi-polynomials and their constituents through subspace and toric viewpoints.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
