Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [chromatic-polynomial]

The tag has no usage guidance.

0
votes
1answer
84 views

Chromatic Polynomials of Circulant Graph With Two Parameters

I have been working with the chromatic polynomials of circulant graphs of prime order $p$ with two distinct parameters, i.e. $P_{p,i,j}(x):= P(C_{p}(i,j),x)$ with $1 \leq i \neq j \leq \ n/2.$ In ...
0
votes
1answer
213 views

Chromatic polynomial for hyper cube [closed]

Does anyone know the chromatic polynomial of the hyper cube graph Q4? I need this to verify that my listing of a subset of all DAG's on the 4-cube is correct. Any help greatly appreciated, JC
0
votes
0answers
69 views

Expressions for the chromatic polynomial of a graph G

Chromatic polynomial of a graph $G$ is an important tool in Graph theory which has been studied extensively from graph theory perspective as well as through other area of Mathematics also. Hence it is ...
10
votes
2answers
575 views

How many chromatic polynomials of planar maps are there?

Let P(n) be the set of polynomials that can occur as the chromatic polynomial of a planar map with n countries. What is known or conjectured about the growth of |P(n)|? PS: Thanks Gerry and Noam, ...
3
votes
1answer
220 views

chromatic polynomial of G - Join graph

Given a connected graph $G$ with $n$ vertices and given set of $\{m_1,m_2,...,m_n\}$ $n$ integers, we form a new graph $G^{\wedge} $ by considering the complete graph $K_{m_i}$ for each vertex i and '...
5
votes
0answers
219 views

Are the roots of chromatic polynomials plus a fixed constant dense in $\mathbb{C}$?

Alan Sokal proved that chromatic roots are dense in the whole complex plane. I.e., if $P(G;z)$ denotes the chromatic polynomial of a finite simple graph $G$ evaluated at $z \in \mathbb{C}$, then $$\...
9
votes
1answer
462 views

Has anyone seen this sort of graph property used before?

Consider the following property of a graph $G$: The graph $G$ has no independent cutset of vertices, $S$, such that the number of components of $G-S$ is more than $|S|$ (the size of $S$). (That is, ...
3
votes
1answer
651 views

Graphical representation of chromatic polynomial

Suppose $c(G,u)$ is chromatic polynomial of connected simple graph $G$. We know that $|c(G,-1)|$, as Stanley proved, is the total number of directed graph on $G$, without any cycle. Also, we know ...
1
vote
1answer
120 views

Non-alternating chromatic factors?

It is well-known that the coefficients of a chromatic polynomial alternate in sign. But is it possible for a chromatic polynomial to have a factor (over $\mathbb{Q}$) with coefficients which do not ...
4
votes
2answers
832 views

polynomials with the same discriminant

Let $p(x)$ be the chromatic polynomial of a special graph. Performing a certain type of operation on the graph changes $p$ by shifting it and adding a constant, say to: $q(x)=p(x+a) + b$. I have ...
8
votes
2answers
596 views

Graphs with the same chromatic symmetric function

Does anyone know more examples of two nonisomorphic connected graphs with the same chromatic symmetric function? The only pair I know is the one in Stanley's paper on c.s.f.'s [http://math.mit.edu/~...
12
votes
0answers
1k views

Finding a chromatic polynomial by polynomial fitting

I would like to find the chromatic polynomial χ for the n by m rook's graph Gn,m for as many values of n and m possible. The rooks graph is also (a) the line graph of the complete bipartite graph ...