
























We consider the following list coloring with separation problem of graphs: Given a graph $G$ and integers $a,b$, find the largest integer $c$ such that for any list assignment $L$ of $G$ with $|L(v)|\le a$ for any vertex $v$ and $|L(u)\cap L(v)|\le c$ for any edge $uv$ of $G$, there exists an assignment $\varphi$ of sets of integers to the vertices of $G$ such that $\varphi(u)\subset L(u)$ and $|\varphi(v)|=b$ for any vertex $v$ and $\varphi(u)\cap \varphi(v)=\emptyset$ for any edge $uv$. Such a value of $c$ is called the separation number of $(G,a,b)$. We also study the variant called the free-separation number which is defined analogously but assuming that one arbitrary vertex is precolored. We determine the separation number and free-separation number of the cycle and derive from them the free-separation number of a cactus. We also present a lower bound for the separation and free-separation numbers of outerplanar graphs of girth $g\ge 5$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。