Exponentially many Z₅-colorings in simple planar graphs

DOI10.1016/J.DISC.2021.112474MaRDI QIDQ2037549zbMATH OpenOpenAlexFDO

Authors Rikke Langhede, Carsten Thomassen

Publication date 8 July 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.12163

zbMATH Keywords

group coloringgroup connectivitylist coloring

Mathematics Subject Classification ID

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

Abstract: Every planar simple graph with n vertices has at least 2^(n/9) Z5-colorings.

Cites work

• A note on group colorings
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Every planar graph is 5-choosable
• Exponentially many 5-list-colorings of planar graphs
• Exponentially many nowhere-zero \(\mathbb{Z}_3\)-, \(\mathbb{Z}_4\)-, and \(\mathbb{Z}_6\)-flows
• Graphs on surfaces
• Group connectivity and group coloring: small groups versus large groups
• Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties
• Many 3-colorings of triangle-free planar graphs
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• The weak 3-flow conjecture and the weak circular flow conjecture

Cited in

(2)

• Graph polynomials and group coloring of graphs
• Hyperbolicity theorems for correspondence colouring

This page was built for publication: Exponentially many \(\mathbb{Z}_5\)-colorings in simple planar graphs

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