Adaptable and conflict colouring multigraphs with no cycles of length three or four
share
The adaptable choosability of a multigraph G, denoted ch_a(G), is the smallest integer k such that any edge labelling, τ, of G and any assignment of lists of size k to the vertices of G permits a list colouring, σ, of G such that there is no edge e = uv where τ(e) = σ(u) = σ(v). Here we show that for a multigraph G with maximum degree Δ and no cycles of length 3 or 4, ch_a(G) ≤ (2√(2)+o(1))√(Δ/lnΔ). Under natural restrictions we can show that the same bound holds for the conflict choosability of G, which is a closely related parameter defined by Dvořák, Esperet, Kang and Ozeki [arXiv:1803.10962].
READ FULL TEXT