The exceptional-line-graph rainbow matching conjecture
The exceptional-line-graph rainbow matching conjecture
Let denote the least number of independent -sets in a graph that guarantees a rainbow independent set of size . Exceptional-line-graph conjecture. If is the line graph of a graph and is not a graph as in Example, then
The source explains that the excluded construction is an obstruction to the stronger bipartite statement and that this conjecture would imply the general-graph full-matching conjecture.
Sources & referencesView supporting material
Primary source
Ron Aharoni, Joseph Briggs, Jinha Kim and Minki Kim, “Rainbow independent sets in certain classes of graphs”, arXiv:1909.13143 (2019).
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.