论文标题
与平面图分离的可调节性和可选性的注释
A note on adaptable choosability and choosability with separation of planar graphs
论文作者
论文摘要
令$ f $为图$ g $的（可能不当的）边缘色； $ g $的顶点着色是\ emph {适用于} $ f $，如果没有颜色同时出现在边缘和两个端点上。如果对于某些整数$ k $，则图$ g $是给定$ g $的任何列表分配$ l $，带有$ | l（v）|所有$ v $的\ ge k $，以及任何边彩色$ f $ $ g $，$ g $，$ g $ pollying $ c $适用于$ f $，其中$ c（v）\ in l（v）in l（v）$ in l（v）$ in l（v）$，然后$ g $ the $ g $ the the $ g $ the the the $ g $ the the the be \ emph \ emph {audaptable $ k $ - $ - $ choosable}。 a {\ em $（k，d）$ - 图$ g $的列表分配}是一张地图，该地图分配给每个顶点$ v $ a List $ l（v）$ l（v）至少$ k $颜色，以便$ | l（x）\ cap l（y）| \ Leq D $每当$ x $和$ y $相邻时。图形为{\ em $（k，d）$ - choosable}，如果对于每个$（k，d）$ - 列表分配$ l $，则有$ l $ - 颜色为$ g $。已经猜想平面图为$（3,1）$ - 可chosable。我们通过给出足够的条件使平面图可适应3美元的$ 3 $可兑换，从而给予了一些进展。由于$（k，1）$ - 可用性是适应性$ k $ -CHOOSABLITY的特殊情况，因此这意味着满足这些条件的平面图为$（3,1）$ - 可衡量。
Let $F$ be a (possibly improper) edge-coloring of a graph $G$; a vertex coloring of $G$ is \emph{adapted to} $F$ if no color appears at the same time on an edge and on its two endpoints. If for some integer $k$, a graph $G$ is such that given any list assignment $L$ to the vertices of $G$, with $|L(v)| \ge k$ for all $v$, and any edge-coloring $F$ of $G$, $G$ admits a coloring $c$ adapted to $F$ where $c(v) \in L(v)$ for all $v$, then $G$ is said to be \emph{adaptably $k$-choosable}. A {\em $(k,d)$-list assignment} for a graph $G$ is a map that assigns to each vertex $v$ a list $L(v)$ of at least $k$ colors such that $|L(x) \cap L(y)| \leq d$ whenever $x$ and $y$ are adjacent. A graph is {\em $(k,d)$-choosable} if for every $(k,d)$-list assignment $L$ there is an $L$-coloring of $G$. It has been conjectured that planar graphs are $(3,1)$-choosable. We give some progress on this conjecture by giving sufficient conditions for a planar graph to be adaptably $3$-choosable. Since $(k,1)$-choosability is a special case of adaptable $k$-choosablity, this implies that a planar graph satisfying these conditions is $(3,1)$-choosable.
