The three-colour exception conjecture for split matchings

From papers

Let GG be a graph on 2n2n vertices whose edge set is decomposed into perfect matchings M1M_1, M2M_2, and M3M_3, and let a1a_1, a2a_2, and a3a_3 be non-negative integers satisfying

a1+a2+a3=n1.a_1+a_2+a_3=n-1.

A component of GG is assumed not to be isomorphic to K4K_4. The three-colour exception conjecture. There exists a matching MM in GG such that

MMi=aifor each i{1,2,3}.|M\cap M_i|=a_i\qquad\text{for each }i\in\{1,2,3\}.

The preceding construction shows that disjoint unions of copies of K4K_4 can obstruct such a matching when all three multiplicities are odd. A positive answer would resolve the three-colour case of the question of Arman, Rödl, and Sales, and would in particular guarantee a matching whenever at least one of the aia_i is even, as well as whenever nn is odd. The conjecture is open in the source.

Progress summary

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

Sources & referencesView supporting material

Primary source

Michael Anastos, David Fabian, Alp Müyesser and Tibor Szabó, “Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets”, arXiv:2212.03100 (2023).

Solutions 0

No solutions have been posted yet.