A -clique-join of is a set of pairs , where is a partition of , both and contain at least one -clique, and , (not necessarily disjoint), moreover

(i) If and , then

(ii) If is an -clique of that meets both and , then there exists so that .

A partitionable graph does not contain a -clique-join for , on the other hand odd holes, odd antiholes do all contain -clique-joins.

*Could the minimum of for which a -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.