P4-structure and Its Relatives

The $P_4$-structure of a graph $G$ is the 4-uniform hypergraph whose vertex-set $V$ is the vertex-set of $G$ and whose hyperedges are the subsets of $V$ that induce $P_{4}$'s (chordless paths on four vertices) in $G$. The graph property of being Berge can be formulated directly in terms of $P_4$-structure: a graph is Berge if and only if its $P_{4}$-structure contains no induced odd ring, meaning a 4-uniform hypergraph with vertices

$$u_{0}, u_{1}, \ldots , u_{k-1},$$

where $k$ is odd and at least five, and with the $k$ hyperedges

$$\{u_{i+1}, u_{i+2}, u_{i+3}, u_{i+4}\},$$

where the subscripts are taken modulo $k$. (The ``if'' part is trivial and the ``only if'' part is easy, even though a little tedious; see [ MR 86j:05119] for a sketch of the argument.)

Can the Chudnovsky-Robertson-Seymour-Thomas decomposition theorem for Berge graphs be reformulated directly in terms of $P_4$-structure?

The five classes of basic graphs featured in the theorem lend themselves nicely to such reformulations: there are classes C of 4-uniform hypergraphs such that

• the $P_{4}$-structure of every basic graph belongs to C,
• no 4-uniform hypergraph in C contains an induced odd ring,
• membership in C can be tested in polynomial time.

One such class is defined in terms of a certain directed graph, $D_{6}(H)$, associated with every 4-uniform hypergraph $H$: C consists of all 4-uniform hypergraphs $H$ such that

• $H$ contains no induced ring with five vertices and
• all strongly connected components of $D_{6}(H)$ are bipartite.

The vertices of $D_{6}(H)$ are all the ordered 6-tuples

$$(u_{1},u_{2},u_{3},u_{4},u_{5},u_{6})$$

of distinct vertices of $H$ such that the sub-hypergraph of $H$ induced by the set

$$\{u_{1},u_{2},u_{3},u_{4},u_{5},u_{6}\}$$

consists of the three hyperedges

$$\{u_{1},u_{2},u_{3},u_{4}\},\; \{u_{2},u_{3},u_{4},u_{5}\},\; \{u_{3},u_{4},u_{5},u_{6}\};$$

there is a directed edge from vertex

$$(u_{1},u_{2},u_{3},u_{4},u_{5},u_{6})$$

of $D_{6}(H)$ to vertex

$$(v_{1},v_{2},v_{3},v_{4},v_{5},v_{6})$$

of $D_{6}(H)$ if and only if

$$v_{1}=u_{2},\; v_{2}=u_{3},\; v_{3}=u_{4},\; v_{4}=u_{5},\; v_{5}=u_{6}.$$

Trivially, membership in C can be tested in polynomial time; trivially, no 4-uniform hypergraph in C contains an induced odd ring; a proof that the $P_{4}$-structure of every basic graph belongs to C is easy, even though a little tedious ([here] is a sketch of the argument).

The four kinds of structural faults featured in the decomposition theorem suggest the following three problems.

Problem 1: Find a class ${\bf C}_{1}$ of 4-uniform hypergraphs such that

• the $P_{4}$-structure of every graph with a 2-join belongs to ${\bf C}_{1}$,
• no odd ring belongs to ${\bf C}_{1}$,
• ${\bf C}_{1}$ belongs to NP.

Problem 2: Find a class ${\bf C}_{2}$ of 4-uniform hypergraphs such that

• the $P_{4}$-structure of every graph with an M-join belongs to ${\bf C}_{2}$,
• no odd ring belongs to ${\bf C}_{2}$,
• ${\bf C}_{2}$ belongs to NP.

Problem 3: Find a class ${\bf C}_{3}$ of 4-uniform hypergraphs such that

• the $P_{4}$-structure of every graph with a balanced skew partition belongs to ${\bf C}_{3}$,
• no odd ring belongs to ${\bf C}_{3}$,
• ${\bf C}_{3}$ belongs to NP.

Chính Hoàng introduced additional graph functions that are invariant under complementation and determine whether or not a graph is Berge: these are the co-paw-structure ([ MR 2001a:05065]), the co-$C_4$-structure (Discrete Math. 252 (2002), 141-159), and the co-$P_3$-structure (to appear in SIAM J. Discrete Math.). Can the decomposition theorem be reformulated directly in terms of one of Hoàng's invariants?

Contributed by Vašek Chvátal

Back to the main index for Perfect Graphs.