Recognition of Seymour graphs

Definitions and mathematical statement

Let $G=(V,E)$ be a finite loopless undirected graph, with parallel edges permitted. A circuit is the edge set of a simple cycle; two parallel edges can form a circuit of length two. For $X\subseteq V$, the cut $\delta(X)$ consists of the edges with exactly one endpoint in $X$.

Call $F\subseteq E$ cycle-sparse when \[ |F\cap C|\le|C\setminus F| \quad\text{for every circuit }C. \] The graph is a Seymour graph when every such $F$ admits a family $\delta(X_1),\ldots,\delta(X_{|F|})$ of pairwise edge-disjoint cuts satisfying \[ |\delta(X_i)\cap F|=1 \quad(1\le i\le|F|). \] The family is empty when $F=\varnothing$. Edge-disjointness and the number of cuts ensure that their unique selected edges exhaust $F$.

Is there a polynomial-time algorithm deciding whether an input graph is a Seymour graph? The input is only $G$: the universal quantifier over cycle-sparse sets is part of the property being recognized. Testing or constructing a packing for one supplied $F$ is therefore not the whole task. The cuts need not be bonds, their vertex sides may overlap, and it is the cut edge sets that must be disjoint. A structural characterization can help, but its existence alone does not establish an effective polynomial-time recognition algorithm.

Short English statement

Can Seymour graphs, defined by their cycle-sparse-set cut-packing property, be recognized in polynomial time?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000070 (AMR-029-0070), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Recognition of Seymour graphs. Original source indexed by AMR-029-0070. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Recognition of Seymour graphs. Individual source statement and remarks. https://lemon.cs.elte.hu/egres/open/Recognition_of_Seymour_graphs.