Questions tagged [chromatic-polynomial]

The tag has no usage guidance.

11 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
13 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 ...
Douglas S. Stones's user avatar
7 votes
0 answers
265 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 ...
Matthew Levy's user avatar
6 votes
0 answers
257 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 $$\...
Rebecca J. Stones's user avatar
5 votes
0 answers
293 views

Which coefficient of a chromatic polynomial is the largest?

Let $\chi_G(q)$ be the chromatic polynomial of a graph $G$ with $n$ vertices. (More generally, $\chi_{\mathcal{A}}(q)$ can be the characteristic polynomial of a finite hyperplane arrangement $\mathcal{...
Richard Stanley's user avatar
4 votes
0 answers
131 views

Chromatic number of rectangle tilings

Suppose we have a region of the plane tiled by finitely many rectangles. We want to color the rectangles so that two rectangles have different colors if they share a part of an edge or if they share ...
Adam Chalcraft's user avatar
2 votes
0 answers
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 ...
GA316's user avatar
  • 1,219
1 vote
0 answers
132 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 ...
vidyarthi's user avatar
  • 2,007
1 vote
0 answers
137 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 ...
GA316's user avatar
  • 1,219
1 vote
0 answers
110 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 ...
Learnmore's user avatar
  • 135
0 votes
0 answers
464 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,...
vidyarthi's user avatar
  • 2,007
0 votes
0 answers
91 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 ...
GA316's user avatar
  • 1,219