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

04/17/2021
by   Dario Cavallaro, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset