The solid Pfaffian graph matching-colouring conjecture

A matching covered graph is a graph in which every edge belongs to a perfect matching. A matching covered graph is solid if every non-trivial separating cut is tight, and Pfaffian if it has the Pfaffian property used in the paper. Let GG be a solid Pfaffian graph and let MM be a perfect matching of GG; write f0aMchromaticGMf0aMchromatic{G}{M} for the corresponding MM-chromatic number.

Solid Pfaffian conjecture.

\MchromaticGM2.\Mchromatic{G}{M}\leq 2.

This is proposed as an extension of the bipartite Pfaffian result to non-bipartite matching covered graphs. The relevant structural questions for solid graphs remain widely open.

Sources & referencesView supporting material

Primary source

Marcelo Garlet Millani, Raphael Steiner and Sebastian Wiederrecht, “Colouring Non-Even Digraphs”, arXiv:1903.02872 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.