All Questions
Tagged with chromatic-polynomial graph-theory
21 questions
17
votes
1
answer
366
views
A new basis for chromatic polynomials
Given a graph $G$ on $n$ vertices, its chromatic polynomial $P(G,x)$ is a function that gives the number of proper colorings of G using $x$ colors.
When $P(G,x)$ is written using the basis $\{x, \...
- 171
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
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
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
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
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
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
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
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
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
0
votes
1
answer
136
views
Chromatic Polynomials of Circulant Graph With Two Parameters
I have been working with the chromatic polynomials of circulant graphs of prime order $p$ with two distinct parameters, i.e.
$P_{p,i,j}(x):= P(C_{p}(i,j),x)$ with $1 \leq i \neq j \leq \ n/2.$
In ...
- 13
0
votes
1
answer
381
views
Chromatic polynomial for hyper cube [closed]
Does anyone know the chromatic polynomial of the hyper cube graph Q4?
I need this to verify that my listing of a subset of all DAG's on the 4-cube is correct.
Any help greatly appreciated,
JC
- 17
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
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 '...
- 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
9
votes
1
answer
480
views
Has anyone seen this sort of graph property used before?
Consider the following property of a graph $G$:
The graph $G$ has no independent cutset of vertices, $S$, such that the number of components of $G-S$ is more than $|S|$ (the size of $S$).
(That is, ...
- 12.7k
3
votes
1
answer
788
views
Graphical representation of chromatic polynomial
Suppose $c(G,u)$ is chromatic polynomial of connected simple graph $G$. We know that
$|c(G,-1)|$, as Stanley proved, is the total number of directed graph on $G$, without any cycle.
Also, we know ...
- 4,784
1
vote
1
answer
136
views
Non-alternating chromatic factors?
It is well-known that the coefficients of a chromatic polynomial alternate in sign. But is it possible for a chromatic polynomial to have a factor (over $\mathbb{Q}$) with coefficients which do not ...
- 1,327
5
votes
2
answers
1k
views
polynomials with the same discriminant
Let $p(x)$ be the chromatic polynomial of a special graph. Performing a certain type of operation on the graph changes $p$ by shifting it and adding a constant, say to: $q(x)=p(x+a) + b$.
I have ...
- 1,327
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