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

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

where the subscripts are taken modulo . (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 -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 -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.

- contains no induced ring with five vertices and
- all strongly connected components of are bipartite.

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

consists of the three hyperedges

there is a directed edge from vertex

of to vertex

of if and only if

Trivially, membership in

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

**Problem 1:** Find a class of
4-uniform hypergraphs such that

- the -structure of every graph with a 2-join belongs to ,
- no odd ring belongs to ,
- belongs to
**NP**.

**Problem 2:** Find a class of
4-uniform hypergraphs such that

- the -structure of every graph with an M-join belongs to ,
- no odd ring belongs to ,
- belongs to
**NP**.

**Problem 3:** Find a class of
4-uniform hypergraphs such that

- the -structure of every graph with a balanced skew partition belongs to ,
- no odd ring belongs to ,
- 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--structure* (Discrete Math.
**252** (2002), 141-159), and the *co--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.