Asymmetric list sizes in bipartite graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913693391912960 |
|---|---|
| author | Alon, Noga Cambie, Stijn Kang, Ross J. |
| author_facet | Alon, Noga Cambie, Stijn Kang, Ross J. |
| contents | 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 $k_A$ or $k_B$, respectively.
We prove some general sufficient conditions in terms of $Δ_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 $Δ_A=Δ_B=Δ$, $k_A=\log Δ$ and $k_B=(1+o(1))Δ/\logΔ$ as $Δ\to\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 Δ_A^\varepsilon$ and $k_B \ge Δ_B^\varepsilon$ for any $\varepsilon>0$ provided $Δ_A$ and $Δ_B$ are large enough;
* if $k_A \ge C \logΔ_B$ and $k_B \ge C \logΔ_A$ for some absolute constant $C>1$; or
* if $Δ_A=Δ_B = Δ$ and $ k_B \ge C (Δ/\logΔ)^{1/k_A}\log Δ$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2004_07457 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Asymmetric list sizes in bipartite graphs Alon, Noga Cambie, Stijn Kang, Ross J. Combinatorics 05C15, 05C35, 05D05 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 $k_A$ or $k_B$, respectively. We prove some general sufficient conditions in terms of $Δ_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 $Δ_A=Δ_B=Δ$, $k_A=\log Δ$ and $k_B=(1+o(1))Δ/\logΔ$ as $Δ\to\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 Δ_A^\varepsilon$ and $k_B \ge Δ_B^\varepsilon$ for any $\varepsilon>0$ provided $Δ_A$ and $Δ_B$ are large enough; * if $k_A \ge C \logΔ_B$ and $k_B \ge C \logΔ_A$ for some absolute constant $C>1$; or * if $Δ_A=Δ_B = Δ$ and $ k_B \ge C (Δ/\logΔ)^{1/k_A}\log Δ$ 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. |
| title | Asymmetric list sizes in bipartite graphs |
| topic | Combinatorics 05C15, 05C35, 05D05 |
| url | https://arxiv.org/abs/2004.07457 |