3-Coloring on Regular, Planar, and Ordered Hamiltonian Graphs

2021/04/17 by Dario Cavallaro, Till Fluschnik, Cavallaro, Dario +1
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2104.08470

openalex publication_date 2021/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that 3-Coloring remains NP-hard on 4- and 5-regular planar Hamiltonian graphs, strengthening the results of Dailey [Disc. Math.'80] and Fleischner and Sabidussi [J. Graph. Theor.'02]. Moreover, we prove that 3-Coloring remains NP-hard on p-regular Hamiltonian graphs for every p≥ 6 and p-ordered regular Hamiltonian graphs for every p≥ 3.

Related

• Polyhedra with few 3-cuts are hamiltonian
• 3-Colouring Planar Graphs
• Three coloring via triangle counting
• Multiple 3-Coloring, an Approach to 4-Coloring of Planar Graphs
• DP-3-coloring of some planar graphs