Chromatic Polynomials at Articulation Vertices

Why Joining Graphs Requires a Correction

When two graphs meet at one vertex and otherwise have no vertices or edges in common, a proper coloring of their union can be built by coloring each graph separately. But multiplying the two chromatic polynomials counts each possible color of the shared vertex twice: once in each graph’s coloring count. The correct product therefore includes a factor of $1/q$.

All graphs below are finite and simple. For a positive integer $q$, a proper $q$-coloring of $G=(V,E)$ assigns each vertex a color from $\{1,\ldots,q\}$, with different colors at the endpoints of every edge. The chromatic polynomial $P_G(q)$ is the polynomial whose value at each positive integer $q$ is the number of proper $q$-colorings. In formulas, $q$ is treated as a variable.

Definition: A vertex $v$ of a connected graph $G$ is an articulation vertex if deleting $v$ and all its incident edges increases the number of connected components. In the setting of this tutorial, two connected graphs $G_1,G_2$, each with at least one vertex other than $v$, meet only at $v$. Their union then has $v$ as an articulation vertex.

For the product formula, the precise assumptions are $V(G_1)\cap V(G_2)=\{v\}$, with no shared edges. Write $G=G_1\cup G_2$; the union has the vertices and edges of both graphs and no additional edges between them. If each graph is connected and has more than one vertex, then deleting $v$ separates the two sides. The counting argument itself also works when either graph is not connected, as long as both contain $v$ and the intersection is exactly $\{v\}$.

The Articulation-Vertex Formula

Theorem: If $G_1,G_2$ meet exactly at the vertex $v$, have no other shared vertices or edges, and $G=G_1\cup G_2$, then $$ P_G(q)=\frac{P_{G_1}(q)P_{G_2}(q)}{q}. $$ The quotient is a polynomial; the identity is a polynomial identity.

Proof. First take a positive integer $q$. For each color $c\in\{1,\ldots,q\}$, let $A_i(c)$ be the number of proper $q$-colorings of $G_i$ that assign color $c$ to $v$, for $i=1,2$. Permuting the color names gives a bijection between colorings counted by $A_i(c)$ and those counted by $A_i(c')$, for any colors $c,c'$. Thus all $q$ values $A_i(c)$ are equal. Since their sum is $P_{G_i}(q)$, each equals $P_{G_i}(q)/q$.

To color $G$, choose the color $c$ of $v$, then choose a coloring of each graph that gives $v$ that same color. There are no other shared vertices or edges, so these choices combine into exactly one proper coloring of the union. Consequently, the number of colorings is $$ \sum_{c=1}^{q} A_1(c)A_2(c) =q\left(\frac{P_{G_1}(q)}{q}\right)\left(\frac{P_{G_2}(q)}{q}\right) =\frac{P_{G_1}(q)P_{G_2}(q)}{q}. $$ This proves the formula for every positive integer $q$. Equivalently, $qP_G(q)=P_{G_1}(q)P_{G_2}(q)$ for every positive integer $q$. Both sides are polynomials, and polynomials agreeing at infinitely many values are identical: a nonzero polynomial of finite degree has at most that many roots. Hence the identity holds as a polynomial identity, and the product on the right is divisible by $q$. $\square$

The division by $q$ removes exactly one repeated choice: the color assigned to $v$. It does not mean the formula should only be evaluated at nonzero values of $q$. The quotient is a polynomial, so its value at $q=0$, for example, is defined by that polynomial.

Worked Example: Two Triangles Sharing One Vertex

Let $G_1$ have vertex set $\{v,a,b\}$ and edge set $\{va,vb,ab\}$. Let $G_2$ have vertex set $\{v,c,d\}$ and edge set $\{vc,vd,cd\}$. They meet only at $v$, and each is a triangle $K_3$.

A triangle’s three vertices must receive distinct colors, so $P_{G_1}(q)=P_{G_2}(q)=q(q-1)(q-2)$. Applying the theorem gives $$ P_G(q)=\frac{\bigl(q(q-1)(q-2)\bigr)^2}{q} =q(q-1)^2(q-2)^2. $$

Check: At $q=3$, each triangle has $3\cdot2\cdot1=6$ colorings, so the product formula gives $6\cdot6/3=12$. Directly, choose one of $3$ colors for $v$. In each triangle, the other two vertices can be colored in $2\cdot1=2$ ways using the remaining colors. The total is $3\cdot2\cdot2=12$, in agreement with the formula. Substitution also gives $3(3-1)^2(3-2)^2=3\cdot4\cdot1=12$.

Using Known Polynomials for the Pieces

The formula is particularly useful when each piece has a known chromatic polynomial. From the earlier material on cycles, for $n\geq 3$, $$ P_{C_n}(q)=(q-1)^n+(-1)^n(q-1). $$ We can apply that result to graphs made by identifying one vertex of two cycles. The cycles’ other vertices must remain distinct, so that their intersection really is just the shared vertex.

Worked Example: A 4-Cycle and a 5-Cycle

Let $G_1$ have vertex set $\{v,a,b,c\}$ and edge set $\{va,ab,bc,cv\}$, so $G_1$ is a 4-cycle. Let $G_2$ have vertex set $\{v,d,e,f,g\}$ and edge set $\{vd,de,ef,fg,gv\}$, so $G_2$ is a 5-cycle. The graphs meet only at $v$.

For the 4-cycle, the cycle formula gives $$ P_{G_1}(q)=(q-1)^4+(q-1) =(q-1)\bigl((q-1)^3+1\bigr) =q(q-1)(q^2-3q+3). $$ Here $(q-1)^3+1=q(q^2-3q+3)$, by expansion.

For the 5-cycle, it gives $$ P_{G_2}(q)=(q-1)^5-(q-1) =(q-1)\bigl((q-1)^4-1\bigr) =q(q-1)(q-2)(q^2-2q+2). $$ The final factorization follows by applying $x^4-1=(x-1)(x+1)(x^2+1)$ with $x=q-1$. Dividing the product of these two polynomials by $q$ yields $$ P_G(q)=q(q-1)^2(q^2-3q+3)(q-2)(q^2-2q+2). $$

Check: At $q=3$, the 4-cycle has $2^4+2=18$ colorings, and the 5-cycle has $2^5-2=30$ colorings. The formula gives $18\cdot30/3=180$. Alternatively, with the shared vertex’s color fixed, the 4-cycle has $18/3=6$ colorings and the 5-cycle has $30/3=10$; choosing that shared color gives $3\cdot6\cdot10=180$. Substitution in the factored result gives $3\cdot4\cdot3\cdot1\cdot5=180$.

Worked Example: Attaching an Edge and a Path to a Cycle

Let $G_1$ have vertex set $\{v,a\}$ and edge set $\{va\}$. Let $G_2$ have vertex set $\{v,b,c,d\}$ and edge set $\{vb,bc,cd,dv\}$, a 4-cycle. Let $G_3$ have vertex set $\{v,x,y\}$ and edge set $\{vx,xy\}$, a path on three vertices. The three graphs meet pairwise only at $v$, and have no shared edges.

For $k$ graphs that pairwise meet exactly at one common vertex $v$, with no shared edges, the same counting argument gives $$ P_{\bigcup_{i=1}^{k}G_i}(q)=\frac{\prod_{i=1}^{k}P_{G_i}(q)}{q^{k-1}}. $$ Indeed, for a fixed color of $v$, the number of colorings of $G_i$ is $P_{G_i}(q)/q$. Multiply these counts across the $k$ graphs, then multiply by $q$ choices for the color of $v$. This gives $q\prod_i(P_{G_i}(q)/q)=\prod_iP_{G_i}(q)/q^{k-1}$ for each positive integer $q$, and the polynomial identity follows by the same infinite-values argument as in the theorem.

An edge has polynomial $q(q-1)$, and a path on three vertices has polynomial $q(q-1)^2$, since its first vertex has $q$ choices and each next vertex has $q-1$. The 4-cycle polynomial, computed above, is $q(q-1)(q^2-3q+3)$. Therefore $$ P_{G_1\cup G_2\cup G_3}(q) =\frac{q(q-1)\cdot q(q-1)(q^2-3q+3)\cdot q(q-1)^2}{q^2} =q(q-1)^4(q^2-3q+3). $$

Check: At $q=3$, the edge has $3\cdot2=6$ colorings, the 4-cycle has $18$, and the path has $3\cdot2^2=12$. The formula gives $6\cdot18\cdot12/3^2=1296/9=144$. Fixing the color of $v$, the three pieces have respectively $2$, $18/3=6$, and $12/3=4$ colorings. The total is $3\cdot2\cdot6\cdot4=144$. The factored polynomial gives $3\cdot2^4\cdot(9-9+3)=3\cdot16\cdot3=144$ as well.

Common Pitfall: Forgetting the Shared Color

A common error is to multiply the two chromatic polynomials without dividing by $q$. For the two-triangle example, this incorrect calculation gives $$ P_{G_1}(q)P_{G_2}(q)=q^2(q-1)^2(q-2)^2, $$ which is too large by a factor of $q$. At $q=3$, it gives $6\cdot6=36$, whereas the union has only $12$ proper colorings. The error is that the first triangle and the second triangle were allowed to choose the color of $v$ independently. Their choices must agree; dividing by $q$ corrects the overcount.

The formula depends on the pieces sharing exactly the specified vertex. If they also share another vertex, their color choices must agree there too, and dividing by $q$ alone does not account for those additional constraints. Likewise, if an extra edge is added between vertices on opposite sides, the independent coloring choices need not combine into a proper coloring of the resulting graph.

Articulation vertices are useful because they let a graph be split into smaller coloring problems. Once the pieces are understood, their polynomials can be combined one at a time, with one factor of $q$ removed each time a new piece is attached at a single shared vertex.

Check Your Understanding

Use the hypotheses carefully: identify the shared vertices before applying a product formula.

Two copies of $K_2$ meet only at $v$. What is the chromatic polynomial of their union?
Why do color permutations imply that exactly $P_{G_i}(q)/q$ colorings of $G_i$ assign any specified color to $v$, for positive integer $q$?
Three graphs meet pairwise only at one common vertex $v$. What power of $q$ divides the product of their chromatic polynomials in the union formula?
For two triangles sharing exactly one vertex, compute the number of proper colorings with $q=4$ and verify it by fixing the color of the shared vertex.
Explain why the articulation-vertex formula cannot be applied unchanged if the two pieces also share another vertex.

Chromatic Polynomials at Articulation Vertices

What You'll Learn