Back to Search Start Over

Graph polynomials and paintability of plane graphs

Authors :
Grytczuk, Jarosław
Jendrol', Stanislav
Zając, Mariusz
Publication Year :
2020

Abstract

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$.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2004.02159
Document Type :
Working Paper