Graph polynomials and paintability of plane graphs

被引:1
|
作者
Grytczuk, Jaroslaw [1 ]
Jendrol, Stanislav [2 ]
Zajac, Mariusz [1 ]
机构
[1] Warsaw Univ Technol, Fac Math & Informat Sci, PL-00662 Warsaw, Poland
[2] PJ Safarik Univ Kosice, Fac Sci, Inst Math, Kosice, Slovakia
关键词
Graph coloring; Plane graphs; Graph polynomials; Paintability; ALON-TARSI NUMBER; LIST COLORINGS;
D O I
10.1016/j.dam.2022.02.006
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
There exists a variety of coloring problems for plane graphs, involving vertices, edges, and faces in all possible combinations. For instance, in the 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 facial variant. We obtain several results concerning the Alon-Tarsi number of various graphs derived from plane embeddings. This allows for extensions of some previous results for choosability of these graphs to the game theoretic variant, known as paintability. For instance, we prove that every plane graph is facially entirely 8-paintable, which means (metaphorically) that even a color-blind person can facially color the entire graph from lists of size 8. (c) 2022 Elsevier B.V. All rights reserved.
引用
收藏
页码:71 / 79
页数:9
相关论文
共 50 条