Skip to main content

All Questions

Filter by
Sorted by
Tagged with
10 votes
2 answers
884 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-...
Joshua P. Swanson's user avatar
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 ...
Yuhang Bai's user avatar
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 ...
Jing Guo's user avatar
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{...
Richard Stanley's user avatar
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(...
mtsecco's user avatar
  • 93
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 ...
vidyarthi's user avatar
  • 2,089
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,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 ...
vidyarthi's user avatar
  • 2,089
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,...
vidyarthi's user avatar
  • 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 ...
GA316's user avatar
  • 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 ...
Learnmore's user avatar
  • 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 ...
GA316's user avatar
  • 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, ...
David Treumann's user avatar
3 votes
1 answer
840 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 '...
GA316's user avatar
  • 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 $$\...
Rebecca J. Stones's user avatar
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/~...
Jeremy Martin's user avatar
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