ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Conjecture 4. For a graph G and a non-negative integer g the following are equivalent (1) There exists a drawing of G on an orientable surface of genus g such that cr(M ) is even for every perfect matching M of G. (2) G is 4g -Pfaffian. (3) G is (4g+1 − 1)-Pfaffian. In [11] we generalize Pfaffian orientations to Pfaffian labelings. Let Γ be an Abelian group, denote by 1 an identity of Γ and denote by −1 some element of order two in Γ. Let G be a graph with V (G) = {1, 2, . . . , 2n}. We say that l : E(G) \to Γ is a Pfaffian labeling of G if for every perfect matching M = {u1 v1 , u2 v2 , . . . , uk vk }, such that ui < vi for every 1 \leq i \leq k we have Y 1 2 3 4 . . . 2k − 1 2k l(e) = sgn . u1 v1 u2 v2 . . . uk vk e\inM The definition of Pfaffian labelings is motivated by the list-edge coloring con- jecture. In a k-regular multigraph one can define a sign for every k-edge coloring (see [1]). A powerful algebraic technique developed by Alon and Tarsi [2] implies that if in a k-edge-colorable k-regular multigraph G all k-edge colorings have the same sign then G is k-list-edge-colorable. In [11] we prove the following theorem, which generalizes a theorem by Ellingham and Goddyn [3] and settles a conjecture by Goddyn. Theorem 5. A multigraph G admits a Pfaffian labeling if and only if for all k all the k-edge colorings of every k-regular multigraph G′ with the same underlying simple graph as G have the same sign. We also give two characterizations of graphs that admit a Pfaffian labeling.

Record

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.