A scope trichotomy for the balanced-skew-partition class problem
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
- Source
- Added
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.