论文标题
列表平面图的重新上色
List recoloring of planar graphs
论文作者
论文摘要
图$ g $的列表分配$ l $是将每个顶点$ v $ g $ g $ a seet $ l（v）$的颜色分配的函数。如果$ g $的$ g $ $ g $的适当着色为$ g $的$ l $颜色，则在v（g）$中的每个$ v \ in l（v）$中的$α（v）\。对于列表分配$ g $的$ l $，$ l $ - recoloring图$ \ nathcal {g，l）$ g $的$ g $是一个图形，其顶点对应于$ g $的$ l $ colorings $ g $和两个$ \ mathcal {g}（g，l）的$ l $ l $ l $ l $ l $ g cy g cc cc cycc cycc cycect night-mathcal {g}（g，l）平面图中的$ d $ - 面是长度$ d $的面孔。 dvo夏克和Feghali猜想了平面图$ g $和列表分配$ l $ g $，that：（i）如果$ | l（v）| \ geq 10 $ in v（g）$中的每个$ v \，则为$ \ \ m natercal {g}（g，l）$（g，l）$ o（v（g）$ o（v（g）$）。 （ii）如果$ g $是三角形的，而$ | l（v）| \ geq 7 $对于v（g）$中的每个$ v \，则$ \ mathcal {g，l）$的直径为$ o（| v（g）|）$。在最近的一篇论文中，克兰斯顿（欧洲J. Combin。（2022））已证明（ii）。在本文中，我们证明了以下结果。令$ g $为平面图，$ l $为$ g $的列表分配。 $ \ bullet $如果对于$ g $的每个$ 3 $ face，则最多有两个与之相邻的$ 3 $ faces，$ | l（v）| \ geq 10 $对于v（g）$中的每个$ v \ in v（g）$中，然后是$ \ nathcal {g，l）$的直径，最多是$ 190 $ 190 | v（g）| $。 $ \ bullet $如果对于$ g $的每一个$ 3 $ -face，则最多有一个$ 3 $ -face与之相邻的$ 3 $ face，$ | l（v）| \ geq 9 $对于v（g）$中的每个$ v \ for v（g）$，则是$ \ nathcal {g}（g，l）$的直径，最多是$ 13 | v（g）| $。 $ \ bullet $如果与任何$ 3 $ -face相邻的面孔至少具有$ 6 $，$ | l（v）| \ geq 7 $对于v（g）$中的每个$ v \，则$ \ mathcal {g}（g，g，l）$的直径最多是$ 242 | v（g）| $。该结果增强了克兰斯顿（II）的结果。
A list assignment $L$ of a graph $G$ is a function that assigns to every vertex $v$ of $G$ a set $L(v)$ of colors. A proper coloring $α$ of $G$ is called an $L$-coloring of $G$ if $α(v)\in L(v)$ for every $v\in V(G)$. For a list assignment $L$ of $G$, the $L$-recoloring graph $\mathcal{G}(G,L)$ of $G$ is a graph whose vertices correspond to the $L$-colorings of $G$ and two vertices of $\mathcal{G}(G,L)$ are adjacent if their corresponding $L$-colorings differ at exactly one vertex of $G$. A $d$-face in a plane graph is a face of length $d$. Dvořák and Feghali conjectured for a planar graph $G$ and a list assignment $L$ of $G$, that: (i) If $|L(v)|\geq 10$ for every $v\in V(G)$, then the diameter of $\mathcal{G}(G,L)$ is $O(|V(G)|)$. (ii) If $G$ is triangle-free and $|L(v)|\geq 7$ for every $v\in V(G)$, then the diameter of $\mathcal{G}(G,L)$ is $O(|V(G)|)$. In a recent paper, Cranston (European J. Combin. (2022)) has proved (ii). In this paper, we prove the following results. Let $G$ be a plane graph and $L$ be a list assignment of $G$. $\bullet$ If for every $3$-face of $G$, there are at most two $3$-faces adjacent to it and $|L(v)|\geq 10$ for every $v\in V(G)$, then the diameter of $\mathcal{G}(G,L)$ is at most $190|V(G)|$. $\bullet$ If for every $3$-face of $G$, there is at most one $3$-face adjacent to it and $|L(v)|\geq 9$ for every $v\in V(G)$, then the diameter of $\mathcal{G}(G,L)$ is at most $13|V(G)|$. $\bullet$ If the faces adjacent to any $3$-face have length at least $6$ and $|L(v)|\geq 7$ for every $v\in V(G)$, then the diameter of $\mathcal{G}(G,L)$ is at most $242|V(G)|$. This result strengthens the Cranston's result on (ii).
