Questions tagged [chromatic-polynomial]
The chromatic-polynomial tag has no usage guidance.
12 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 ...
- 4,229
7
votes
0
answers
269
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 ...
- 527
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 $$\...
- 1,327
5
votes
0
answers
302
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{...
- 50.8k
4
votes
0
answers
134
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 ...
- 381
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,269
1
vote
0
answers
159
views
+50
A question relates to edge chromatic-polynomial
Properly colored graph (edge has color) means that any two adjacent edges have distinct colors.
For any graph with $m$ edges such that it can be properly colored using $k$ colors. What is the minimum ...
- 91
1
vote
0
answers
145
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 ...
- 2,089
1
vote
0
answers
158
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,269
1
vote
0
answers
113
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
0
votes
0
answers
548
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,...
- 2,089
0
votes
0
answers
97
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,269