Asymmetric List Sizes in Bipartite Graphs

Source abstract

Abstract Given a bipartite graph with parts A and B having maximum degrees at most $$\Delta _A$$ Δ A and $$\Delta _B$$ Δ B , respectively, consider a list assignment such that every vertex in A or B is given a list of colours of size $$k_A$$ k A or $$k_B$$ k B , respectively. We prove some general sufficient conditions in terms of $$\Delta _A$$ Δ A , $$\Delta _B$$ Δ B , $$k_A$$ k A , $$k_B$$ k B to be guaranteed a proper colouring such that each vertex is coloured using only a colour from its list. These are asymptotically nearly sharp in the very asymmetric cases. We establish one sufficient condition in particular, where $$\Delta _A=\Delta _B=\Delta$$ Δ A = Δ B = Δ , $$k_A=\log \Delta$$ k A = log Δ and $$k_B=(1+o(1))\Delta /\log \Delta$$ k B = ( 1 + o ( 1 ) ) Δ / log Δ as $$\Delta \rightarrow \infty$$ Δ → ∞ . This amounts to partial progress towards a conjecture from 1998 of Krivelevich and the first author. We also derive some necessary conditions through an intriguing connection between the complete case and the extremal size of approximate Steiner systems. We show that for complete bipartite graphs these conditions are asymptotically nearly sharp in a large part of the parameter space. This has provoked the following. In the setup above, we conjecture that a proper list colouring is always guaranteed if $$k_A \ge \Delta _A^\varepsilon$$ k A ≥ Δ A ε and $$k_B \ge \Delta _B^\varepsilon$$ k B ≥ Δ B ε for any $$\varepsilon >0$$ ε > 0 provided $$\Delta _A$$ Δ A and $$\Delta _B$$ Δ B are large enough; if $$k_A \ge C \log \Delta _B$$ k A ≥ C log Δ B and $$k_B \ge C \log \Delta _A$$ k B ≥ C log Δ A for some absolute constant $$C>1$$ C > 1 ; or if $$\Delta _A=\Delta _B = \Delta$$ Δ A = Δ B = Δ and $$k_B \ge C (\Delta /\log \Delta )^{1/k_A}\log \Delta$$ k B ≥ C ( Δ / log Δ ) 1 / k A log Δ for some absolute constant $$C>0$$ C > 0 . These are asymmetric generalisations of the above-mentioned conjecture of Krivelevich and the first author, and if true are close to best possible. Our general sufficient conditions provide partial progress towards these conjectures.