Closure Under Disjoint Union and Join

Two Ways to Combine Graphs

Combining graphs can affect their cliques and colorings in different ways. In a disjoint union, there are no edges between the two vertex sets, so vertices in separate graphs can reuse colors. In a join, every vertex of one graph is adjacent to every vertex of the other, so the two sides must use disjoint sets of colors. These differences lead to maximum formulas for disjoint unions and sum formulas for joins.

All graphs here are finite and simple. A proper coloring assigns colors to vertices so that adjacent vertices receive different colors; the chromatic number $\chi(G)$ is the least number of colors in such a coloring. A clique is a set of pairwise adjacent vertices; the clique number $\omega(G)$ is the largest size of a clique. We use $\chi(G)=\omega(G)=0$ for the graph with no vertices.

Definition: A graph $G$ is perfect if every induced subgraph $G[S]$, for every $S\subseteq V(G)$, satisfies $\chi(G[S])=\omega(G[S])$. Here $G[S]$ has vertex set $S$ and contains exactly the edges of $G$ whose endpoints both lie in $S$.

Let $G$ and $H$ have disjoint vertex sets. Their disjoint union, denoted $G\cup H$, keeps all edges of $G$ and $H$ and adds no edges between their vertex sets. Their join, denoted $G\vee H$, keeps those edges and also adds every edge $uv$ with $u\in V(G)$ and $v\in V(H)$. If the original vertex sets overlap, first relabel one graph so that they are disjoint.

Formulas for Disjoint Union

Theorem: For finite simple graphs $G,H$ on disjoint vertex sets, $$ \omega(G\cup H)=\max\{\omega(G),\omega(H)\},\qquad \chi(G\cup H)=\max\{\chi(G),\chi(H)\}. $$

Proof. A clique in $G\cup H$ cannot contain a vertex from each side: there are no edges between the sides. Thus each clique lies wholly in $G$ or wholly in $H$, and a largest clique has size $\max\{\omega(G),\omega(H)\}$. This also holds when one or both graphs are empty, since their clique number is zero.

Any proper coloring of $G\cup H$ restricts to proper colorings of both $G$ and $H$. Therefore it uses at least $\max\{\chi(G),\chi(H)\}$ colors. Conversely, take a coloring of each graph using at most $k=\max\{\chi(G),\chi(H)\}$ colors. Rename colors on one side if necessary so that both color sets are subsets of the same set of $k$ colors. Since no edge joins the sides, these colorings combine to a proper coloring of the union using at most $k$ colors. The two bounds give the claimed equality, including the empty-graph case $k=0$. $\square$

Worked Example: A Disjoint Union of a Path and an Edge

Let $G$ have $V(G)=\{a,b,c\}$ and $E(G)=\{ab,bc\}$, so $G=P_3$. Let $H$ have $V(H)=\{d,e\}$ and $E(H)=\{de\}$, so $H=K_2$. Consider $G\cup H$, with no edges between $\{a,b,c\}$ and $\{d,e\}$.

In $G$, the edge $ab$ is a clique of size $2$, and there is no triangle, so $\omega(G)=2$. Coloring $a,c$ with color 1 and $b$ with color 2 shows $\chi(G)\le2$; the edge $ab$ requires two colors, so $\chi(G)=2$. In $H$, the edge $de$ gives $\omega(H)=2$ and requires two colors, so $\chi(H)=2$.

The formulas give $\omega(G\cup H)=\max\{2,2\}=2$ and $\chi(G\cup H)=\max\{2,2\}=2$. Explicitly, color $\{a,c,d\}$ with color 1 and $\{b,e\}$ with color 2. Every edge $ab,bc,de$ has endpoints of different colors; the edge $ab$ shows one color cannot suffice. A largest clique has size 2, witnessed by $ab$, and no larger clique can cross between the two sides.

Check: The degrees in the union are $1,2,1,1,1$ at $a,b,c,d,e$, respectively; the only edges are $ab,bc,de$. Thus the exhibited coloring and clique calculation use exactly the defined graph.

Formulas for Join

Theorem: For finite simple graphs $G,H$ on disjoint vertex sets, $$ \omega(G\vee H)=\omega(G)+\omega(H),\qquad \chi(G\vee H)=\chi(G)+\chi(H). $$

Proof. A clique in $G\vee H$ consists of a clique from $G$ and a clique from $H$, possibly with either part empty: vertices on opposite sides are all adjacent, and vertices within each side must be pairwise adjacent. Consequently, every clique has size at most $\omega(G)+\omega(H)$. Taking a largest clique in each graph and combining them gives a clique of exactly that size. The argument includes an empty side, whose clique number is zero.

In any proper coloring of the join, no color can appear on both sides, because every vertex of $G$ is adjacent to every vertex of $H$. The colors used on $G$ and $H$ are therefore disjoint, so at least $\chi(G)+\chi(H)$ colors are required. Conversely, color $G$ with $\chi(G)$ colors and $H$ with a separate set of $\chi(H)$ colors. Edges within either side are properly colored by construction, and edges between the sides have differently colored endpoints because the color sets are disjoint. This gives a coloring with $\chi(G)+\chi(H)$ colors. If one side is empty, the same argument reduces to the formula for the other side; if both are empty, both sides of the equality are zero. $\square$

Worked Example: Joining Two Isolated Vertices to an Edge

Let $G$ have $V(G)=\{a,b\}$ and $E(G)=\varnothing$, and let $H$ have $V(H)=\{c,d\}$ and $E(H)=\{cd\}$. The join has vertex set $\{a,b,c,d\}$ and edge set $\{ac,ad,bc,bd,cd\}$.

The largest clique in $G$ has size $1$, since $a$ and $b$ are not adjacent; hence $\omega(G)=1$. One color suffices on $G$, so $\chi(G)=1$. The edge $cd$ gives $\omega(H)=2$ and $\chi(H)=2$. Thus the join formulas give $\omega(G\vee H)=1+2=3$ and $\chi(G\vee H)=1+2=3$.

For a direct check, $\{a,c,d\}$ is a clique: the edges $ac,ad,cd$ are all present, so at least three colors are necessary. There is no clique of size $4$, because $ab$ is not an edge. For a three-coloring, assign color 1 to $a$, color 2 to $b$, color 3 to $c$, and color 1 to $d$. The edge list verifies this: $ac$ has colors 1 and 3, $ad$ has 1 and 1—so this assignment is not proper. Instead, assign color 1 to $a$, color 2 to $b$, color 3 to $c$, and color 1 to $d$ cannot work because $ad$ is an edge. A valid coloring is color 1 on $a$, color 2 on $b$, and color 3 on both $c$ and $d$—but $cd$ is an edge, so that also fails. The correct assignment uses three colors on the join only if the two vertices $a,b$ can share a color and $c,d$ each use different colors: give $a,b$ color 1, $c$ color 2, and $d$ color 3. Every cross-edge has colors 1 and 2 or 1 and 3, and $cd$ has colors 2 and 3. This confirms $\chi=3$.

Why Both Operations Preserve Perfectness

The key point is that taking an induced subgraph commutes with either operation. If $S\subseteq V(G)\cup V(H)$, write $S_G=S\cap V(G)$ and $S_H=S\cap V(H)$. By the definitions of induced subgraph, disjoint union and join,

(G\cup H)[S]=G[S_G]\cup H[S_H], \qquad (G\vee H)[S]=G[S_G]\vee H[S_H].

For the union, an edge in the induced subgraph lies in one original side and is retained exactly when both endpoints are selected. For the join, the same within-side rule applies, and each selected vertex in $S_G$ remains adjacent to each selected vertex in $S_H$. These observations prove both identities, even if one selected side is empty.

Theorem: If $G$ and $H$ are perfect graphs on disjoint vertex sets, then $G\cup H$ and $G\vee H$ are perfect.

Proof. Let $S\subseteq V(G)\cup V(H)$, and put $G'=G[S_G]$ and $H'=H[S_H]$. Since $G,H$ are perfect, their induced subgraphs satisfy $\chi(G')=\omega(G')$ and $\chi(H')=\omega(H')$, including when either selected set is empty.

For the disjoint union, the induced-subgraph identity and the union formulas give $\chi((G\cup H)[S])=\max\{\chi(G'),\chi(H')\}=\max\{\omega(G'),\omega(H')\}=\omega((G\cup H)[S])$. For the join, they give $\chi((G\vee H)[S])=\chi(G')+\chi(H')=\omega(G')+\omega(H')=\omega((G\vee H)[S])$. Thus every induced subgraph of either combined graph has equal chromatic and clique numbers, which is precisely perfectness. $\square$

Worked Example: An Induced Subgraph of the Join

Use the join from the preceding example, whose edges are $ac,ad,bc,bd,cd$, and select $S=\{a,b,c\}$. The induced subgraph has vertex set $\{a,b,c\}$ and edge set $\{ac,bc\}$: the edge $cd$ is absent because $d\notin S$, and $ab$ was absent from the original graph.

This is the join of the edgeless graph on $\{a,b\}$ and the one-vertex graph on $\{c\}$. Their clique numbers are $1$ and $1$, and their chromatic numbers are $1$ and $1$. The join formulas give $\omega=1+1=2$ and $\chi=1+1=2$. Directly, $\{a,c\}$ is a two-vertex clique, while there is no triangle because $ab$ is missing. Color $a,b$ with color 1 and $c$ with color 2; the two listed edges both have endpoints of different colors. Since $ac$ is an edge, one color cannot suffice. This check illustrates the induced-subgraph step used in the perfectness proof.

Common Mistake: Reusing Colors Across a Join

For the join in the second example, a tempting but wrong calculation is $\chi(G\vee H)=\max\{\chi(G),\chi(H)\}=\max\{1,2\}=2$. That maximum formula belongs to disjoint union, not join. In the join, both $a$ and $b$ are adjacent to both $c$ and $d$, so a color used on either side cannot be reused on the other. Moreover, $a,c,d$ form a triangle, requiring at least three colors. The correct calculation is $\chi(G\vee H)=\chi(G)+\chi(H)=1+2=3$, and the explicit coloring above attains that bound.

The distinction also applies to cliques: a clique in a disjoint union must stay on one side, while a clique in a join can combine cliques from both sides. These structural facts explain the paired formulas and are what make the perfectness argument work for every induced subgraph, not merely for the original graphs.

Check Your Understanding

Use the definitions and formulas above; when checking perfectness, remember to consider induced subgraphs.

Let $G$ be an edgeless graph on three vertices and $H=K_2$. What are $\chi(G\cup H)$ and $\omega(G\cup H)$?
For the same $G,H$, what are $\chi(G\vee H)$ and $\omega(G\vee H)$? Explain why colors cannot be shared across the two sides.
Show directly that the graph on $\{x,y,z\}$ with edges $\{xy,yz\}$ is perfect by checking its possible induced subgraphs.
Why does a clique in a disjoint union have to lie in one of its two constituent graphs?
For $S\subseteq V(G)\cup V(H)$, explain why the induced subgraph of $G\vee H$ on $S$ is $G[S\cap V(G)]\vee H[S\cap V(H)]$.