论文标题
与周期和外平面图分离的可选性
Choosability with Separation of Cycles and Outerplanar Graphs
论文作者
论文摘要
我们考虑以下列表的颜色，包括图形的分离问题：图$ g $和Integers $ a，b $，找到最大的整数$ c $，以使任何列表分配$ l $ g $ a $ g $带有$ | l（v）| \ le a $ a $ for vertex $ v $ and $ | l（u c $ c $ g $ g $ g $ c $ g $ c $ uv $ uv $ uv $ uv $ uv $ uv $ uv $ uv $ uv $ uv $ uv $ uv $ uv $ uv $ $ g $的顶点的一组整数，以使任何顶点$ v $和$φv $和$φ（u）和$φ（u）\capφ（v）= \ emptyset $ for Any Edge $ uv $ for Anevertex $ v $和$φ（u）\capφ（v）的$φ（u）\ subset l（u）和$ |φ（v）| = b $。这样的$ c $的值称为$（g，a，b）$的分离数。我们还研究称为自由分离数的变体，该变体类似地定义，但假设一个任意顶点是先进的。我们确定循环的分离数和自由分离数，并从仙人掌的自由分离数中得出。我们还提出了一个下限，用于围墙$ g \ ge 5 $的外平面图的分离和自由分离数。
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 $φ$ of sets of integers to the vertices of $G$ such that $φ(u)\subset L(u)$ and $|φ(v)|=b$ for any vertex $v$ and $φ(u)\cap φ(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$.
