3 papers
cs.DM2026
Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width
Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer
We prove that every class of Eulerian directed graphs of bounded carving width (equivalently of bounded degree and treewidth) is well-quasi-ordered by strong immersion. In fact, we…
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…