# Questions tagged [chromatic-polynomial]

The chromatic-polynomial tag has no usage guidance.

**0**

votes

**1**answer

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

**1**answer

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

**0**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**2**answers

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

**0**answers

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 ...