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$
  • 1
    $\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 Apr 26 '16 at 9:29
  • 1
    $\begingroup$ @MartinSleziak it was easier to fix it with $G^{\wedge }$. $\endgroup$ – Amir Sagiv Apr 26 '16 at 12:42
  • 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$ – Per Alexandersson Apr 27 '16 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 May 2 '16 at 9:15
  • 1
    $\begingroup$ this somewhat resembles the vertex corona of the graph $G$ with $K_{m_i}$ $\endgroup$ – vidyarthi Aug 8 at 15:03
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$
  • $\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 Apr 27 '16 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.