Aharoni–Berger–Kotlar–Ziv degree-constrained matching conjecture
Aharoni–Berger–Kotlar–Ziv degree-constrained matching conjecture
Let be a simple -partite -graph with vertex classes , and . Suppose each vertex in has degree at least , and each vertex in has degree at most . Aharoni–Berger–Kotlar–Ziv conjecture.
This degree-asymmetric statement extends the regular case and gives a lower bound in terms of the size of one vertex class. For , it is among the conjectures that generalize the open Ryser–Brualdi–Stein problem on Latin transversals, so its full generality remains difficult.
Sources & referencesView supporting material
Primary source
Penny Haxell and Lothar Narins, “A Stability Theorem for Matchings in Tripartite 3-Graphs”, arXiv:1701.06451 (2017).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.