ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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

• the P4-structure of every graph with a balanced skew partition belongs to C3,

• no odd ring belongs to C3,

• C3 belongs to NP.

6http://www.cs.rutgers.edu/ ∼chvatal/perfect/problems.html#basic 21

Ch´ ınh Ho` ang introduced additional graph functions that are invariant under comple-mentation and determine whether or not a graph is Berge: these are the co-paw-structure

([MR 2001a:05065]), the co-C4-structure (Discrete Math. 252 (2002), 141-159), and the

co-P3-structure (to appear in SIAM J. Discrete Math.). Can the decomposition theorem be reformulated directly in terms of one of Ho` ang's invariants? Contributed by Vaˇ sek Chv´ atal

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.