Nondeterministic Polynomial Characterization of Seymour Graphs

Definitions and mathematical statement

The supplied problem asks: "Can one find a nondeterministic polynomial-time characterization of Seymour graphs?" The record does not define a Seymour graph or specify the intended graph domain and input encoding. These omissions prevent a self-contained definition of the recognition problem.

The following gives a conditional complexity-theoretic formulation. Once the intended graph domain $\mathcal D$, its subclass $\mathcal S$ of Seymour graphs, and a finite binary encoding have been specified, let \[ L_{\mathcal S}=\{x\in\{0,1\}^{*}:x\text{ encodes a graph in }\mathcal S\}. \] Here $|x|$ denotes the length of a binary string $x$. A nondeterministic polynomial-time recognition criterion means that there exist a polynomial bound $p$ and a deterministic verifier $V$, running in time polynomial in $|x|+|w|$, such that \[ \forall x\in\{0,1\}^{*},\qquad x\in L_{\mathcal S} \iff \exists w\in\{0,1\}^{*}\; \left(|w|\le p(|x|)\ \land\ V(x,w)=1\right). \] Thus the question, under this interpretation of "characterization," is whether $L_{\mathcal S}\in\mathrm{NP}$.

The class $\mathcal S$, graph domain $\mathcal D$, and encoding remain unspecified by the supplied evidence; no choice of directedness, simplicity, loops, or parallel edges is imposed here. The record also does not explain whether "characterization" demands additional structural content beyond such a certificate criterion. This is therefore a conditional statement-only formulation requiring review against the cited source.

Short English statement

The problem asks whether membership in the intended class of Seymour graphs can be certified by polynomial-size witnesses checked in polynomial time. The supplied record does not define that class or its graph conventions, so the formal recognition problem remains conditional on those missing definitions. The supplied status is open; it is not independently verified here.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30001939$, exact source problem code catalogue entry, title "Nondeterministic Polynomial Characterization of Seymour Graphs." The record assigns proposed year $2011$ and names no proposer.
• Supplied source citation: Combinatorial Optimization (2012), Oberwolfach Reports, pp. 3003--3076, DOI 10.4171/owr/2011/53. Original OWR report: https://doi.org/10.4171/owr/2011/53. The supplied background describes these reports as records of mathematical workshops and their open-problem discussions. The registry labels the statement exact and reports that the official report states the question verbatim; this verification claim is supplied metadata and has not been independently checked here.
• Supplied literature reference, labeled "Seymour graph characterization": https://doi.org/10.1007/978-3-642-20807-2_1. No authors, full bibliographic citation, or relevant theorem statement are supplied.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and states that the report and later excluded-minor work give co-NP characterizations, while an NP characterization or equivalent resolution remains open. This is supplied dated curation, not an independently verified literature assessment. The supplied background explicitly requests independent verification of time-sensitive status and cited claims.