All Questions
Tagged with co.combinatorics chromatic-polynomial
18 questions
10
votes
2
answers
912
views
Status of the Stanley–Stembridge conjecture
As mentioned in the post on Stanley's 25 positivity problems, Tatsuyuki Hikita posted a preprint on October 16, 2024 purporting to prove Problem 21, the Stanley–Stembridge conjecture about e-...
1
vote
0
answers
182
views
+50
A question relates to edge chromatic-polynomial
Properly colored graph (edge has color) means that any two adjacent edges have distinct colors.
The edge chromatic polynomial $ech(G, k)$ gives the number of proper edge coloring of the $G$ with $k$ ...
- 91
4
votes
1
answer
229
views
Minimum number of possible proper colorings
Properly colored graph (edge has color) means that any two adjacent edges have distinct colors.
For any graph with $2k-2$ edges such that it can be properly colored using $k$ colors. What is the ...
- 91
3
votes
1
answer
255
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 ...
- 75
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
6
votes
1
answer
178
views
On a limit involving a transform of the chromatic polynomial
I was playing around with the chromatic polynomial (denoted here by $\chi_G(x)$) and I have made the following conjecture.
Let $(G_n)_{n \ge 1}$ be a sequence of graphs with $v(G_n) \to \infty$ ($v(...
- 93
1
vote
0
answers
147
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
2
votes
0
answers
86
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
0
votes
1
answer
145
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 ...
- 2,089
0
votes
0
answers
552
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
1
vote
0
answers
159
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
114
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
1
vote
1
answer
169
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,269
11
votes
2
answers
659
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,949
3
votes
1
answer
842
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,269
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
11
votes
2
answers
838
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,500
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