Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userChromatic nonsymmetric polynomials of Dyck graphs are slide-positive
107
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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$.
A {em k-generalized Dyck path} of length $n$ is a lattice path from $(0,0)$ to $(n,0)$ in the plane integer lattice $mathbb{Z}timesmathbb{Z}$ consisting of horizontal-steps $(k, 0)$ for a given integer $kgeq 0$, up-steps $(1,1)$, and down-steps $(1,-1)$, which never passes below the x-axis. The present paper studies three kinds of statistics on $k$-generalized Dyck paths: number of $u$-segments, number of internal $u$-segments and number of $(u,h)$-segments. The Lagrange inversion formula is used to represent the generating function for the number of $k$-generalized Dyck paths according to the statistics as a sum of the partial Bell polynomials or the potential polynomials. Many important special cases are considered leading to several surprising observations. Moreover, enumeration results related to $u$-segments and $(u,h)$-segments are also established, which produce many new combinatorial identities, and specially, two new expressions for Catalan numbers.
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.
The theme of this article is a reciprocity between bounded up-down paths and bounded alternating sequences. Roughly speaking, this ``reciprocity manifests itself by the fact that the extension of the sequence of numbers of paths of length $n$, consisting of diagonal up- and down-steps and being confined to a strip of bounded width, to negative $n$ produces numbers of alternating sequences of integers that are bounded from below and from above. We show that this reciprocity extends to families of non-intersecting bounded up-down paths and certain arrays of alternating sequences which we call alternating tableaux. We provide as well weight
A strong edge colouring of a graph is an assignment of colours to the edges of the graph such that for every colour, the set of edges that are given that colour form an induced matching in the graph. The strong chromatic index of a graph $G$, denoted by $chi_s(G)$, is the minimum number of colours needed in any strong edge colouring of $G$. A graph is said to be emph{chordless} if there is no cycle in the graph that has a chord. Faudree, Gyarfas, Schelp and Tuza~[The Strong Chromatic Index of Graphs, Ars Combin., 29B (1990), pp.~205--211] considered a particular subclass of chordless graphs, namely the class of graphs in which all the cycle lengths are multiples of four, and asked whether the strong chromatic index of these graphs can be bounded by a linear function of the maximum degree. Chang and Narayanan~[Strong Chromatic Index of 2-degenerate Graphs, J. Graph Theory, 73(2) (2013), pp.~119--126] answered this question in the affirmative by proving that if $G$ is a chordless graph with maximum degree $Delta$, then $chi_s(G) leq 8Delta -6$. We improve this result by showing that for every chordless graph $G$ with maximum degree $Delta$, $chi_s(G)leq 3Delta$. This bound is tight up to to an additive constant.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
