论文标题
平面图的多项式和油漆性
Graph polynomials and paintability of plane graphs
论文作者
论文摘要
在所有可能的组合中，都存在各种平面图的着色问题，涉及顶点，边缘和面。例如，在平面图的\ emph {整个着色}中，我们要着色这三组，以便任何相邻或事件元素都会获得不同的颜色。我们在这里从代数角度研究了这种类型的一些问题，重点是\ emph {facial}变体。我们获得了有关从平面嵌入的各种图的\ emph {alon-tarsi编号}的几个结果。这允许将这些图的\ emph {Chosobility}的某些先前结果扩展到游戏理论变体中，称为\ emph {paintability}。例如，我们证明每个平面图在面部完全\ emph {$ 8 $ - 绘制}，这意味着（隐喻地）即使是一个色盲的人也可以面部颜色整个尺寸$ 8 $的图形列表。
There exists a variety of coloring problems for plane graphs, involving vertices, edges, and faces in all possible combinations. For instance, in the \emph{entire coloring} of a plane graph we are to color these three sets so that any pair of adjacent or incident elements get different colors. We study here some problems of this type from algebraic perspective, focusing on the \emph{facial} variant. We obtain several results concerning the \emph{Alon-Tarsi number} of various graphs derived from plane embeddings. This allows for extensions of some previous results for \emph{choosability} of these graphs to the game theoretic variant, know as \emph{paintability}. For instance, we prove that every plane graph is facially entirely \emph{$8$-paintable}, which means (metaphorically) that even a color-blind person can facially color the entire graph form lists of size $8$.
