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…
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.