3
$\begingroup$

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 'join' (in the sense of graph theory) two of such complete graphs if the corresponding vertices are adjacent in $G$. Is there name for this graph $G^{\wedge }$ associated to the Graph $G$?

I think this is known as G-join graph. if any body can tell me the name this notion, I can look back in literature also.

By joining of two graphs $G_1$ and $G_2$, I mean introducing edges from all the vertices of $G_1$ to all the vertices of $G_2$ and vice versa, keeping the original edges as is.

My question is what is the chromatic polynomial of $G^{\wedge}$ (may be interms of the chromatic polynomial of $G$) ?

Thanks for your valuable time.

Thanks a lot

$\endgroup$
5
  • 2
    $\begingroup$ On the terminology question, what you have done is "blow up each vertex $i$ to a clique of order $m_i$". $\endgroup$
    – Ben Barber
    Commented Apr 26, 2016 at 9:29
  • 1
    $\begingroup$ You might want to look into Stanleys symmetric chromatic polynomial, which generalizes the chromatic polynomial. Perhaps you can make a stronger statement? $\endgroup$ Commented Apr 27, 2016 at 13:58
  • 1
    $\begingroup$ @PerAlexandersson do you mean chromatic symmetric function or there is symmetric chromatic function? can you plz suggest me some references? $\endgroup$
    – GA316
    Commented May 2, 2016 at 9:15
  • $\begingroup$ @GA316: The chromatic symmetric function is what I mean, see e.g. www-math.mit.edu/~rstan/transparencies/3plus1.pdf $\endgroup$ Commented May 2, 2016 at 12:10
  • 1
    $\begingroup$ this somewhat resembles the vertex corona of the graph $G$ with $K_{m_i}$ $\endgroup$
    – vidyarthi
    Commented Aug 8, 2019 at 15:03

1 Answer 1

2
$\begingroup$

To me it seems hard to me describe $\chi(G^{\wedge})$ in general, but in the case of chordal graphs we can say something. For a chordal graph $G$ we have a perfect elimination order on the vertices which means we can order the vertices $v_1 < v_2 < \cdots < v_n$ such that for each $i$ the neighbors of $v_i$ occurring before $v_i$ form a clique. The perfect elimination order allows us to describe $\chi(G^{\wedge})$ in terms on $\chi(G)$ and $\{m_1, \dots, m_n\}$. The chromatic polynomials of a chordal graph factors in linear factors and can be computed by visiting vertices in the the order specified by a perfect elimination order. We can computed the chromatic polynomial of $G^{\wedge}$ by visiting the cliques in the order specified by the partial elimination order. The linear factors of $\chi(G)$ will be replaced by falling factorials in $\chi(G^{\wedge})$ (see example at end). Note if $G$ is chordal the a perfect elimination order and $\chi(G)$ can both be found efficiently.

As an example let's look at trees. Let $T$ be a tree on $n$ vertices and assume $m_i = m$ for for $1 \leq i \leq n$. Then I claim $$\chi(T^{\wedge}) = (t)_m (t-m)_m^{n-1}$$ where $(t)_m = t(t-1) \cdots (t-m+1)$ is the falling factorial. We induct on $n$ similar to how we would prove $\chi(T) = t(t-1)^{n-1}$. If $n=1$, then $T^{\wedge} = K_m$ and the result holds. If $n > 1$, then $T$ must have leaf. Let $T'$ be $T$ with the leaf removed. By Induction $\chi((T')^{\wedge}) = (t)_m (t-m)_m^{n-2}$. Consider coloring $T^{\wedge}$ with $t$ colors by first coloring $(T')^{\wedge}$ in $(t)_m (t-m)_m^{n-2}$ possible ways and then coloring the $K_m$ associated to the leaf vertex in $(t-m)_m$ possible ways.

For arbitrary $m_i$ for any tree it will matter which $m_i$ is connected to which $m_j$, that is we need to first find a perfect elimination order. For example if $P$ is the path on $n$ vertices and we have $\{m_1, \dots, m_n\}$ we get $$\chi(P^{\wedge}) = (t)_{m_{1}} (t-m_1)_{m_{2}} \cdots (t-{m_{n-1}})_{m_n}.$$

Also we can compute for $K_{n}$ since $K_n^{\wedge} = K_{m_1 + \cdots + m_n}$. We can express the chromatic polynomials as $$\chi(K_n) = t(t-1)\cdots(t-n+1) = (t)_n$$ $$\chi(K_n^{\wedge}) = (t)_{m_1} (t-m_1)_{m_2} \cdots (t-m_1 -\cdots - m_{n-1})_{m_n} = (t)_{m_1 + \cdots + m_n}$$ and see that linear factors get replaced falling factorials. This example is easy because of the symmetry of a complete graph. For the complete graph any ordering of the vertices is a perfect elimination ordering.

Update: Here is an example of computing $\chi(G)$ and $\chi(G^{\wedge})$ from a perfect elimination order on a graph. Let $G$ be the graph pictured below. $$\chi(G) = t(t-1)(t-2)(t-1)$$ $$\chi(G^{\wedge}) = (t)_{m_1}(t-m_1)_{m_2}(t-m_1-m_2)_{m_3}(t-m_1)_{m_4}$$

$\hskip 2.5in$ graph

$\endgroup$
1
  • $\begingroup$ Frankly speaking, for all my computation purposes, this much is more than sufficient. Thanks a lot. thanks to point out the difficulty in finding the general polynomial. again thanks for your time. $\endgroup$
    – GA316
    Commented Apr 27, 2016 at 4:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .