Questions tagged [chromatic-polynomial]
The chromatic-polynomial tag has no usage guidance.
11
questions with no upvoted or accepted answers
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 ...
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 ...
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 $$\...
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{...
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 ...
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 ...
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 ...
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 ...
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 ...
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,...
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 ...