# Perfectly Contractile Graphs and the Decomposition Method

The following conjecture, due to Everett and Reed attempts to characterize perfectly contractile graphs.

Perfectly Contractile Graph Conjecture (PCGC) A graph is perfectly contractile if and only if it does not contain an odd hole, an antihole nor an odd prism.

We propose to investigate the PCGC and a possible construction of a polynomial-time recognition algorithm for perfectly contractile graphs, through the decomposition method.

The decomposition method is based on a decomposition theorem of the following form, for the class of graphs we want to analyse.

Decomposition Theorem If , then is either basic or it contains certain types of cutsets.

Basic stands for a certain simple'' subclass of .

The idea of a decomposition based recognition algorithm for the class is as follows. In a connected graph , a node set (or an edge set or a combination of the two) is a cutset if its removal disconnects into two or more connected components. From these components blocks of decomposition are constructed by adding some more nodes and edges. A decomposition is -preserving if it satisfies the following: belongs to if and only if all the blocks of decomposition belong to . A decomposition based recognition algorithm takes an input graph and decomposes it using -preserving decompositions into a polynomial number of basic blocks, which are then checked, in polynomial time, whether they belong to .

Such a construction of blocks works nicely for clique cutsets. A node set is a star cutset of a graph if its removal disconnects and contains a node that is adjacent to all the other nodes of . With the usual construction of blocks for the node cutsets, the star cutset decomposition is not preserving for the class of perfectly contractile graphs.

A generalization of star cutsets is obtained as follows. 1-Amalgams are defined and used in for the construction of a recognition algorithm for Meyniel graphs. A graph has a 1-amalgam if its vertex set can be partitioned into sets , and (where is possibly empty) in such a way that:

• for , and contains a nonempty set ;
• every node of is adjacent to every node of and these are the only adjacencies between the nodes of and the nodes of ; and
• if , then it induces a clique, and every node of is adjacent to every node of .

A graph has a 2-join if its node set can be partitioned into sets and so that for , contains disjoint nonempty sets and , and the following properties hold:

• every node of (resp. ) is adjacent to every node of (resp. ), and these are the only adjacencies between the nodes of and the nodes of ;
• for , let be the set of all chordless paths in with one endnode in , the other endnode in , and no intermediate node in . For , and is not isomorphic to a path in .

Let denote the class of perfectly contractile graphs.

We have the following conjectures.

Conjecture 1-Amalgam decomposition is -preserving.

Conjecture 2-Join decomposition is -preserving.

Conjecture No minimal non perfectly contractile graph has a star cutset.

Note that the PCGC implies all three of these conjectures.

Contributed by Claudia Linhares Sales.

Back to the main index for Perfect Graphs.