论文标题
图形多项式和图形的组着色
Graph Polynomials and Group Coloring of Graphs
论文作者
论文摘要
令$γ$为Abelian组，让$ G $成为一个简单的图表。我们说，如果对于$ g $的某些固定取向以及标记$ \ ell：e（g）\rightarrowγ$的每个边缘的固定取向，则存在$ c $ c $ $γ$的元素，从$ c（y）-c（x）$ e x $ x $ to（xy） $ y $）。 Langhede和Thomassen最近证明了$ N $ Vertices上的每个平面图至少具有$ 2^{n/9} $不同的$ \ Mathbb {z} _5 $ -Colorings。通过使用基于图形多项式的不同方法，我们将此结果扩展到$ k_5 $ -minor-fim-minor-fime-fime-minor-fime graphs在更通用的字段着色设置中。更具体地说，我们证明$ n $顶点上的每一个此类图是$ \ mathbb {f} $ - $ 5 $ - choosable，只要$ \ mathbb {f} $是一个任意字段，至少是$ 5 $元素。此外，颜色的数量（每个列表分配）至少为$ 5^{n/4} $。
Let $Γ$ be an Abelian group and let $G$ be a simple graph. We say that $G$ is $Γ$-colorable if for some fixed orientation of $G$ and every edge labeling $\ell:E(G)\rightarrow Γ$, there exists a vertex coloring $c$ by the elements of $Γ$ such that $c(y)-c(x)\neq \ell(e)$, for every edge $e=xy$ (oriented from $x$ to $y$). Langhede and Thomassen proved recently that every planar graph on $n$ vertices has at least $2^{n/9}$ different $\mathbb{Z}_5$-colorings. By using a different approach based on graph polynomials, we extend this result to $K_5$-minor-free graphs in the more general setting of field coloring. More specifically, we prove that every such graph on $n$ vertices is $\mathbb{F}$-$5$-choosable, whenever $\mathbb{F}$ is an arbitrary field with at least $5$ elements. Moreover, the number of colorings (for every list assignment) is at least $5^{n/4}$.
