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

DOI10.1007/978-3-031-25211-2_10MaRDI QIDQ6132529zbMATH OpenOpenAlexFDO

Authors Niranjan Balachandran, Brahadeesh Sankarnarayanan

Publication date 17 August 2023

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

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)

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.

Cites work

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

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)