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.