Asymmetric list sizes in bipartite graphs

DOI10.1007/S00026-021-00552-5zbMATH Open1479.05087arXiv2004.07457OpenAlexW3197870094MaRDI QIDQ825958FDOQ825958

Authors: Stijn Cambie, Ross J. Kang, Noga Alon

Publication date: 18 December 2021

Published in: Annals of Combinatorics (Search for Journal in Brave)

Abstract: Given a bipartite graph with parts

A

and

B

having maximum degrees at most

D e l t a_{A}

and

D e l t a_{B}

, respectively, consider a list assignment such that every vertex in

A

or

B

is given a list of colours of size

k_{A}

or

k_{B}

, respectively. We prove some general sufficient conditions in terms of

D e l t a_{A}

,

D e l t a_{B}

,

k_{A}

,

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

D e l t a_{A} = D e l t a_{B} = D e l t a

,

k_{A} = l o g D e l t a

and

k_{B} = (1 + o (1)) D e l t a / l o g D e l t a

as

D e l t a o i n f t y

. 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} g e D e l t a_{A}^{v} a r e p s i l o n

and

k_{B} g e D e l t a_{B}^{v} a r e p s i l o n

for any

v a r e p s i l o n > 0

provided

D e l t a_{A}

and

D e l t a_{B}

are large enough; * if

k_{A} g e C l o g D e l t a_{B}

and

k_{B} g e C l o g D e l t a_{A}

for some absolute constant

C > 1

; or * if

D e l t a_{A} = D e l t a_{B} = D e l t a

and

k_{B} g e C (D e l t a / l o g D e l t a)^{1 / k_{A}} l o g D e l t a

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.

Full work available at URL: https://arxiv.org/abs/2004.07457

Recommendations

zbMATH Keywords

graph coloring choice number L-colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

Cited In (6)

This page was built for publication: Asymmetric list sizes in bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q825958)