2 papers
cs.CC2021
3-Coloring on Regular, Planar, and Ordered Hamiltonian Graphs
Dario Cavallaro, Till Fluschnik
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.…
cs.CC2021
Feedback Vertex Set on Hamiltonian Graphs
Dario Cavallaro, Till Fluschnik
We study the computational complexity of Feedback Vertex Set on subclasses of Hamiltonian graphs. In particular, we consider Hamiltonian graphs that are regular or are planar and r…