Clique Joins

A $k$-clique-join of $G=(V,E)$ is a set of pairs $\{(A_0,B_0), (A_1,B_1), \ldots, (A_k,B_k)\}$, where $\{A_0,B_0\}$ is a partition of $V$, both $A_0$ and $B_0$ contain at least one $\omega$-clique, and $A_i\subseteq A_0$, $B_i\subseteq B_0$ $(i=1,\ldots , k)$ (not necessarily disjoint), moreover

(i) If $x\in A_i$ and $y\in B_i$, then $xy\in E$

(ii) If $K$ is an $\omega$-clique of $G$ that meets both $A_0$ and $B_0$, then there exists $i$ so that $K\subseteq A_i\cup B_i$.

A partitionable graph does not contain a $k$-clique-join for $k< 2(\omega -1)$, on the other hand odd holes, odd antiholes do all contain $2(\omega -1)$-clique-joins.

Could the minimum of $k$ for which a $k$-clique-join exists be computed (or well-characterized)? For Berge-graphs? Is there a variant of this operation that would allow to compose perfect graphs and keep perfectness ?

Contributed by András Sebo

Back to the main index for Perfect Graphs.