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 ${\mathcal C}$ we want to analyse.

Decomposition Theorem If $G \in {\mathcal C}$, then $G$ is either basic or it contains certain types of cutsets.

Basic stands for a certain ``simple'' subclass of ${\mathcal C}$.

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

Such a construction of blocks works nicely for clique cutsets. A node set $S$ is a star cutset of a graph $G$ if its removal disconnects $G$ and $S$ contains a node that is adjacent to all the other nodes of $S$. 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 $G$ has a 1-amalgam if its vertex set can be partitioned into sets $V_1$, $V_2$ and $K$ (where $K$ is possibly empty) in such a way that:

• for $i=1,2$, $\vert V_i\vert \geq 2$ and $V_i$ contains a nonempty set $A_i$;
• every node of $A_1$ is adjacent to every node of $A_2$ and these are the only adjacencies between the nodes of $V_1$ and the nodes of $V_2$; and
• if $K \neq \emptyset$, then it induces a clique, and every node of $K$ is adjacent to every node of $A_1 \cup A_2$.

A graph $G$ has a 2-join if its node set can be partitioned into sets $V_1$ and $V_2$ so that for $i=1,2$, $V_i$ contains disjoint nonempty sets $A_i$ and $B_i$, and the following properties hold:

• every node of $A_1$ (resp. $B_1$) is adjacent to every node of $A_2$ (resp. $B_2$), and these are the only adjacencies between the nodes of $V_1$ and the nodes of $V_2$;
• for $i=1,2$, let ${\mathcal P}_i$ be the set of all chordless paths in $G[V_i]$ with one endnode in $A_i$, the other endnode in $B_i$, and no intermediate node in $A_i \cup B_i$. For $i=1,2$, ${\mathcal P}_i \neq \emptyset$ and $G[V_i]$ is not isomorphic to a path in ${\mathcal P}_i$.

Let ${\mathcal C}^{pc}$ denote the class of perfectly contractile graphs.

We have the following conjectures.

Conjecture 1-Amalgam decomposition is ${\mathcal C}^{pc}$-preserving.

Conjecture 2-Join decomposition is ${\mathcal C}^{pc}$-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.