TY - JOUR

T1 - Asymmetric List Sizes in Bipartite Graphs

AU - Alon, Noga

AU - Cambie, Stijn

AU - Kang, Ross J.

N1 - Funding Information:
S. Cambie and R. J. Kang: Supported by a Vidi grant (639.032.614) of The Netherlands Organisation for Scientific Research (NWO).
Funding Information:
N. Alon: Supported in part by NSF grant DMS-1855464, BSF grant 2018267 and the Simons Foundation
Publisher Copyright:
© 2021, The Author(s).

PY - 2021/12

Y1 - 2021/12

N2 - Given a bipartite graph with parts A and B having maximum degrees at most Δ A and Δ B, respectively, consider a list assignment such that every vertex in A or B is given a list of colours of size kA or kB, respectively. We prove some general sufficient conditions in terms of Δ A, Δ B, kA, kB 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 Δ A= Δ B= Δ , kA= log Δ and kB= (1 + o(1)) Δ / log Δ as Δ → ∞. 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 guaranteedif kA≥ΔAε and kB≥ΔBε for any ε> 0 provided Δ A and Δ B are large enough;if kA≥ Clog Δ B and kB≥ Clog Δ A for some absolute constant C> 1 ; orif Δ A= Δ B= Δ and kB≥C(Δ/logΔ)1/kAlogΔ for some absolute constant 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.

AB - Given a bipartite graph with parts A and B having maximum degrees at most Δ A and Δ B, respectively, consider a list assignment such that every vertex in A or B is given a list of colours of size kA or kB, respectively. We prove some general sufficient conditions in terms of Δ A, Δ B, kA, kB 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 Δ A= Δ B= Δ , kA= log Δ and kB= (1 + o(1)) Δ / log Δ as Δ → ∞. 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 guaranteedif kA≥ΔAε and kB≥ΔBε for any ε> 0 provided Δ A and Δ B are large enough;if kA≥ Clog Δ B and kB≥ Clog Δ A for some absolute constant C> 1 ; orif Δ A= Δ B= Δ and kB≥C(Δ/logΔ)1/kAlogΔ for some absolute constant 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.

UR - http://www.scopus.com/inward/record.url?scp=85114015498&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85114015498&partnerID=8YFLogxK

U2 - 10.1007/s00026-021-00552-5

DO - 10.1007/s00026-021-00552-5

M3 - Article

AN - SCOPUS:85114015498

SN - 0218-0006

VL - 25

SP - 913

EP - 933

JO - Annals of Combinatorics

JF - Annals of Combinatorics

IS - 4

ER -