Graph polynomials and paintability of plane graphs

DOI10.1016/J.DAM.2022.02.006MaRDI QIDQ6338076arXivFDO

Authors Jarosław Grytczuk, Stanislav Jendroľ, Mariusz Zając

Publication date 5 April 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DAM.2022.02.006

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31)

arXiv classification

math.CO

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

This page was built for publication: Graph polynomials and paintability of plane graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6338076)