Liang's matching and node-disjoint link conjecture for subcubic bipartite graphs
Liang's matching and node-disjoint link conjecture for subcubic bipartite graphs
Let be a bipartite graph. An -link is a path of length whose two endpoints lie in , and a family of -links is node-disjoint if no two links share a node. A matching is a set of pairwise nonincident edges.
Liang's conjecture. If every node in has degree at most and every node in has degree at most , then has a matching and a family of node-disjoint -links such that every node of degree is covered by an edge in
The conjecture was proposed as a tool toward antimagic edge labelings: it was known to imply that every -regular graph is antimagic. It is proved in the source, so the conjecture is solved.
Sources & referencesView supporting material
Primary source
Kristóf Bérczi, Attila Bernáth and Máté Vizer, “A note on V-free 2-matchings”, arXiv:1505.03717 (2015).
Additional references
2 papers in this index state this conjecture (2015). The statement above is taken from the most recent of them; the others are arXiv:1504.08146.
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.