ISR conjecture for line graphs of simple bipartite graphs

Let HH be a simple bipartite graph, let L(H)L(H) be its line graph, and let V1,,VmV_1,\ldots,V_m be a partition of the edge set of L(H)L(H). An independent system of representatives (ISR) is an independent set meeting each ViV_i in at most one vertex. Bipartite line-graph ISR conjecture. If

Vi>Δ(H)+1|V_i|>\Delta(H)+1

for every ii, then the system has an ISR. This proposes a stronger ISR property for line graphs of bipartite graphs than for general graphs; the source provides no evidence of a resolution.

Sources & referencesView supporting material

Primary source

Ron Aharoni, Eli Berger, Dani Kotlar and Ran Ziv, “On a conjecture of Stein”, arXiv:1605.01982 (2016).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.