On the choosability with separation of planar graphs and its correspondence colouring analogue

Abstract

A list assignment $L$ for a graph $G$ is an $(\ell ,k)$-list assignment if $|L(v)|\ge \ell$ for each $v\in V(G)$ and $|L(u)\cap L(v)|\le k$ for each $uv\in E(G)$. We say $G$ is $(\ell ,k)$-choosable if it admits an $L$-colouring for every $(\ell ,k)$-list assignment $L$. We prove that if $G$ is a planar graph with $(4,2)$-list assignment $L$ and for every triangle $T\subseteq G$ we have that $|{\bigcap }_{v\in V(T)}L(v)|\ne 2$, then $G$ is $L$-colourable. In fact, we prove a slightly stronger result: if $G$ contains a clique $H$ such that $V(H)\cap V(T)\ne \varnothing$ for every triangle $T\subseteq G$ with $|{\bigcap }_{v\in V(T)}L(v)|=2$, then $G$ is $L$-colourable. Additionally, we give a counterexample to the correspondence colouring analogue of $(4,2)$-choosability for planar graphs.

8 pages, 1 figure. Removed a theorem that was already implied by an existing result