论文标题
关于与平面图的分离及其对应着色类似物的可选性
On the choosability with separation of planar graphs and its correspondence colouring analogue
论文作者
论文摘要
图$ g $的列表分配$ l $是$（\ ell，k）$ - 列表分配，如果$ | l（v）| \ geq \ ell $ for v（g）$ in v（g）$和$ | l（u）\ cap l（v）| \ e（g）$中的每个$ uv \ for \ leq k $。我们说$ g $是$（\ ell，k）$ - 如果承认每$（\ ell，k）$的$ l $颜色，则可以选择。我们证明，如果$ g $是带有$（4,2）$ - 列表分配$ l $的平面图，对于每个三角形$ t \ subseteq g $，我们都有$ | \ bigcap_ {v \ in V（t）} l（v）| \ neq 2 $，然后$ g $是$ l $ - 颜色。实际上，我们证明结果稍强：如果$ g $包含一个集团$ h $，则每个三角形$ v（h）\ cap v（t）\ neq \ embtySet $ for for for每个三角形$ t \ subseteq g $带有$ | \ bigCap_ = 2 $，然后$ g $是$ l $ - 颜色。此外，我们对$（4,2）$ - 平面图的可调性的对应着色类似物进行了反例。
A list assignment $L$ for a graph $G$ is an $(\ell,k)$-list assignment if $|L(v)|\geq \ell$ for each $v \in V(G)$ and $|L(u) \cap L(v)| \leq 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)| \neq 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) \neq \emptyset$ 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.
