ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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=n−1.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

∣M∩Mi∣=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.

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.