The bipartite list-cover independent transversal conjecture

Let GG and HH be bipartite graphs, with bipartitions V(G)=AGBGV(G)=A_G\cup B_G and V(H)=AHBHV(H)=A_H\cup B_H. Let HH be a bipartite list-cover of GG with respect to a mapping LL, meaning that LL induces a partition of V(H)V(H) aligned with the two bipartitions, and call HH a kk-fold cover when L(v)=k|L(v)|=k for every vV(G)v\in V(G). An independent transversal is an independent set in HH intersecting every part of the partition induced by LL exactly once. The bipartite list-cover conjecture. There is some C1C\ge1 such that, for any bipartite graph GG of maximum degree Δ2\Delta\ge2, any

Clog2Δ\left\lceil C\log_2\Delta\right\rceil

-fold bipartite list-cover of GG admits an independent transversal. This is a cover-graph reformulation of the logarithmic list-colouring conjecture and remains open.

Sources & referencesView supporting material

Primary source

Stijn Cambie, Penny Haxell, Ross J. Kang and Ronen Wdowinski, “A precise condition for independent transversals in bipartite covers”, arXiv:2308.14778 (2024).

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.