5-list coloring toroidal 6-regular triangulations in linear time

DOI10.1007/978-3-031-25211-2_10arXiv2106.01634OpenAlexW3168200238MaRDI QIDQ6132529FDOQ6132529

Authors: Niranjan Balachandran, Brahadeesh Sankarnarayanan 

Publication date: 17 August 2023

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We give an explicit procedure for $5$-list-coloring a large class of toroidal $6$-regular triangulations in linear time. We also show that these graphs are not $3$-choosable.

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

zbMATH Keywords

triangulationlist coloringtoroidal graphlinear time algorithmregular graph

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Title not available (Why is that?)
• Every planar graph is 5-choosable
• Color-critical graphs on a fixed surface
• Combinatorial Nullstellensatz
• Five-coloring graphs on the torus
• The list chromatic index of a bipartite multigraph
• Three-coloring triangle-free planar graphs in linear time
• Title not available (Why is that?)
• 6-Critical Graphs on the Klein Bottle
• Five-coloring graphs on the Klein bottle
• Title not available (Why is that?)
• 4-colorable 6-regular toroidal graphs.
• Colorings and orientations of graphs
• The complexity of planar graph choosability
• Construction and enumeration of regular maps on the torus
• Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface
• Hamiltonian circuits in some maps on the torus
• A solution to a colouring problem of P. Erdős
• The choice number versus the chromatic number for graphs embeddable on orientable surfaces
• Choosability of toroidal graphs without short cycles
• On the hardness of approximating the chromatic number
• Filling the complexity gaps for colouring planar and bounded degree graphs
• On Six-Chromatic Toroidal Graphs
• Title not available (Why is that?)
• Hyperbolic families and coloring graphs on surfaces
• List-coloring embedded graphs
• Note on 4-coloring 6-regular triangulations on the torus
• 5-list coloring toroidal 6-regular triangulations in linear time
• The Alon-Tarsi number of a toroidal grid

Cited In (2)

• 5-list coloring toroidal 6-regular triangulations in linear time
• Note on 4-coloring 6-regular triangulations on the torus

This page was built for publication: 5-list coloring toroidal 6-regular triangulations in linear time

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