# Questions tagged [chromatic-polynomial]

The tag has no usage guidance.

25 questions
Filter by
Sorted by
Tagged with
204 views

### Sum of squares of chromatic roots of a bipartite graph

Given a graph $G = (V, E)$, we can calculate its chromatic polynomial $P(G, k)$, and it has $n$ (complex) roots, also known as chromatic roots. It is a well-known fact that the sum of chromatic roots ...
275 views

• 93
1 vote
124 views

### The chromatic polynomial of a line graph

Is there a way to obtain the chromatic polynomial of the line graph of a regular simple graph, having known the chromatic polynomial of the graph? There already exist characterizations of line graph ...
• 1,841
85 views

### chromatic class of graphs of order $n$

Let $\mathcal{G}(n)$ be the isomorphism class of simple graphs of order $n$. We say two graphs in $\mathcal{G}(n)$ are chromatic equivalent if their chromatic polynomials have an equal linear ...
• 1,209
129 views

### Chromatic Polynomial when two disjoint graphs are joined at $2$ distinct points [closed]

Consider a graph with chromatic polynomial $P(x)$ joined to a clique of order $k$ in two distinct points (joining here just means interesection of points). Then, what is the chromatic polynomial of ...
• 1,841
444 views

### Chromatic polynomial of a bipartite graph replaced by a new graph

Consider a semi-regular bipartite graph $C$ consisting of two parts $A$ (having each vertex of degree $\Delta$) and $B$ (having each vertex of degree $2$). Let its chromatic polynomial be $C(x)$. Now,...
• 1,841
1 vote
123 views

### Linear coefficient of chromatic polynomial

I am interested in the combinatorics of the linear coefficient of the chromatic polynomials. I have the following questions. What are some class of graphs for which it is possible to calculate this ...
• 1,209
1 vote
104 views

### Bounds on spectral radius using chromatic number

I am struggling with this question: If I have a connected graph $G$ on $n$ vertices and $m$ edges with chromatic number $d$ then how can I give a bound(lower and upper) on its spectral radius in ...
• 135
260 views

### Chromatic polynomial and the circle

In https://arxiv.org/pdf/1208.5781.pdf It is proved that there is spectral sequence converging to $H^*(M^G,R)$ with the E1 page given by the graph cohomology complex $C_A(G)$ where $A:=H^*(M,R)$. My ...
• 507
1 vote
141 views

### Extension of chromatic polynomial to multi graphs

Let $G$ be a multigraph, i.e, there can be more than one edge between a pair of vertices. It is clear that the chromatic polynomial cannot capture these multi-edges. Because chromatic polynomial just ...
• 1,209
122 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 ...
357 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
• 17
89 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 ...
• 1,209
643 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, ...
• 4,819
731 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 '...
• 1,209
256 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 \...
• 1,317
476 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, ...
• 11.7k
757 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 ...
• 4,738
1 vote
129 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 ...
• 1,307
1k 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 ...
• 1,307
794 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/~...
• 1,440