Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the complexity of generalized chromatic polynomials
146
0
0.0
(
0
)
Added by
Johann Makowsky
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
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$.
We study the dynamic and complexity of the generalized Q2R automaton. We show the existence of non-polynomial cycles as well as its capability to simulate with the synchronous update the classical version of the automaton updated under a block sequential update scheme. Furthermore, we show that the decision problem consisting in determine if a given node in the network changes its state is textbf{P}-Hard.
In the present paper we find a simple algorithm for counting Jacobian group of the generalized Petersen graph GP(n,k). Also, we obtain a closed formula for the number of spanning trees of this graph in terms of Chebyshev polynomials.
The generalized Narayana polynomials $N_{n,m}(x)$ arose from the study of infinite log-concavity of the Boros-Moll polynomials. The real-rootedness of $N_{n,m}(x)$ had been proved by Chen, Yang and Zhang. They also showed that when $ngeq m+2$, each of the generalized Narayana polynomials has one and only one positive zero and $m$ negative zeros, where the negative zeros of $N_{n,m}(x)$ and $N_{n+1,m+1}(x)$ have interlacing relations. In this paper, we study the properties of the positive zeros of $N_{n,m}(x)$ for $ngeq m+2$. We first obtain a new recurrence relation for the generalized Narayana polynomials. Based on this recurrence relation, we prove upper and lower bounds for the positive zeros of $N_{n,m}(x)$. Moreover, the monotonicity of the positive zeros of $N_{n,m}(x)$ are also proved by using the new recurrence relation.
A class of simple graphs such as ${cal G}$ is said to be {it odd-girth-closed} if for any positive integer $g$ there exists a graph $G in {cal G}$ such that the odd-girth of $G$ is greater than or equal to $g$. An odd-girth-closed class of graphs ${cal G}$ is said to be {it odd-pentagonal} if there exists a positive integer $g^*$ depending on ${cal G}$ such that any graph $G in {cal G}$ whose odd-girth is greater than $g^*$ admits a homomorphism to the five cycle (i.e. is $C_{_{5}}$-colorable). In this article, we show that finding the odd girth of generalized Petersen graphs can be transformed to an integer programming problem, and using this we explicitly compute the odd girth of such graphs, showing that the class is odd-girth-closed. Also, motivated by showing that the class of generalized Petersen graphs is odd-pentagonal, we study the circular chromatic number of such graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
