UP - logo
E-resources
Full text
Peer reviewed Open access
  • Adaptable and conflict colo...
    Aliaj, Jurgen; Molloy, Michael

    Journal of graph theory, September 2023, Volume: 104, Issue: 1
    Journal Article

    The adaptable choosability of a multigraph G $G$, denoted cha(G) ${\text{ch}}_{a}(G)$, is the smallest integer k $k$ such that any edge labelling, τ $\tau $, of G $G$ and any assignment of lists of size k $k$ to the vertices of G $G$ permits a list colouring, σ $\sigma $, of G $G$ such that there is no edge e=uv $e=uv$ where τ(e)=σ(u)=σ(v) $\tau (e)=\sigma (u)=\sigma (v)$. Here we show that for a multigraph G $G$ with maximum degree Δ ${\rm{\Delta }}$ and no cycles of length 3 or 4, cha(G)≤(22+o(1))Δ∕ln Δ ${\text{ch}}_{a}(G)\,\le (2\sqrt{2}+o(1))\sqrt{{\rm{\Delta }}\unicode{x02215}\mathrm{ln}\unicode{x0200A}{\rm{\Delta }}}$. Under natural restrictions we can show that the same bound holds for the conflict choosability of G $G$, which is a closely related parameter recently defined by Dvořák, Esperet, Kang and Ozeki.