Pfaffian Conditions for Graphs on Orientable Surfaces

Definitions and mathematical statement

The main source is Norine's three-way conjecture. For the standard matching-polynomial formulation, let $G$ be a finite loopless graph of even order, with a fixed vertex order; multigraph and degenerate/no-perfect-matching conventions must be matched to the report. For an orientation $D$, write its weighted skew-adjacency Pfaffian as \[ \operatorname{Pf}(A_D)=\sum_{M\text{ perfect}}s_D(M)\prod_{e\in M}x_e, \] where $s_D(M)\in\{\pm1\}$ is the usual matching sign from the vertex order and oriented edges. The unsigned perfect-matching polynomial is $Z_G=\sum_M\prod_{e\in M}x_e$. In the usual "at most" convention, $G$ is $k$-Pfaffian if \[ Z_G=\sum_{i=1}^{r}c_i\operatorname{Pf}(A_{D_i}),\qquad r\leq k, \] for orientations $D_i$ and allowed scalar coefficients, conventionally real. This is a polynomial identity, not merely equality of the unweighted matching counts; the precise coefficient and padding conventions are not supplied by the excerpt.

For every nonnegative integer $g$, the conjecture asks whether the following are equivalent:

1. There is a drawing on an orientable surface of genus $g$ with $\operatorname{cr}(M)$ even for every perfect matching $M$.
2. $G$ is $4^g$-Pfaffian.
3. $G$ is $(4^{g+1}-1)$-Pfaffian.

In a general-position drawing, $\operatorname{cr}(M)$ counts crossings between the drawn matched edges, with the intended multiplicities. The drawing may have crossings; this is not a claim that it is an embedding. The constants are exponentials in $g$, correcting the source extraction's lost exponents.

The original record also includes distinct established-background claims about Pfaffian labelings. For $V(G)=\{1,\ldots,2n\}$, let $\Gamma$ be abelian with identity $1$ and a chosen element $-1$ of order two. A labeling $\ell:E(G)\to\Gamma$ is Pfaffian when, for every perfect matching $M=\{u_1v_1,\ldots,u_nv_n\}$, $u_i<v_i$, \[ \prod_{e\in M}\ell(e) =\operatorname{sgn}(u_1,v_1,\ldots,u_n,v_n), \] with the permutation sign interpreted as $1$ or the chosen $-1$. Reordering the two-element blocks does not alter that sign.

The source's Theorem 5 says that a multigraph admits a Pfaffian labeling, in its intended allowed-group convention, exactly when for every integer $r$ all $r$-edge-colorings of every $r$-regular multigraph with the same underlying simple graph have the same sign. The precise labeling-group quantifier and edge-coloring-sign definition require the missing references. The source attributes this to [11], generalizing Ellingham--Goddyn [3] and settling a Goddyn conjecture. Separately, its Alon--Tarsi implication [2] says that an $r$-edge-colorable $r$-regular multigraph whose proper $r$-edge-colorings all have the same sign is $r$-list-edge-colorable. The edge-colorability hypothesis is retained; the assertion is not used vacuously when no coloring exists. The report also mentions two further labeling characterizations without stating them.

These labeling/coloring claims are background, not a solution of the three-way genus conjecture. The supplied triage dated 21 August 2026 says the primary survey still presents that equivalence as Norine's conjecture, with partial cases and no general resolution located. This is a supplied dated assessment, not an independent proof or literature review.

Short English statement

The main question equates an even-crossing matching drawing with the two corrected Pfaffian bounds. The separate labeling and edge-coloring results are retained as source background. Exact Pfaffian conventions and graph edge cases need checking before mathematical review.

Sources

• Local UnsolvedMath registry, permanent ID $30000175$, exact source code catalogue entry, Oberwolfach Reports Open Problems, Conjecture 4. Statement status corrected_verified; supplied verification corrects the two lost exponents.
• "Graph Theory (2005)," Oberwolfach Reports, pp. 135--183, DOI 10.4171/owr/2005/03: https://doi.org/10.4171/owr/2005/03. Proposed year 2005.
• Supplied "Norine, survey of Pfaffian orientations": https://thomas.math.gatech.edu/PAP/pfafsurv.pdf. Full theorem conventions are not reproduced in the record.
• Source-local [11] supplies Pfaffian labelings and Theorem 5; [1] concerns edge-coloring signs; [2] is attributed to Alon--Tarsi; [3] to Ellingham--Goddyn. The source also credits Goddyn's conjecture. Complete bibliographic entries are absent.
• Literature checked 21 August 2026; supplied status open, with the three-way equivalence still conjectural in the checked survey. Registry created 25 August 2026 and updated 16 September 2026. This dated triage requires independent verification before citation.
• Registry curation attribution: Ulam AI / UnsolvedMath Contributors, CC BY 4.0. Underlying report and literature retain their supplied provenance; this statement-only draft requires human review.