4 papers
Complexity of acyclic colorings of graphs and digraphs with degree and girth constraints
Tom\' as Feder, Pavol Hell, Carlos Subi
We consider acyclic r-colorings in graphs and digraphs: they color the vertices in r colors, each of which induces an acyclic graph or digraph. (This includes the dichromatic numbe…
Distance-Two Colorings of Barnette Graphs
Tomas Feder, Pavol Hell, Carlos Subi
Barnette identified two interesting classes of cubic polyhedral graphs for which he conjectured the existence of a Hamiltonian cycle. Goodey proved the conjecture for the intersect…
On the algorithmic complexity of finding hamiltonian cycles in special classes of planar cubic graphs
Behrooz Bagheri Gh., Tomas Feder, Herbert Fleischner +1
It is a well-known fact that hamiltonicity in planar cubic graphs is an NP-complete problem. This implies that the existence of an A-trail in plane eulerian graphs is also an NP-co…
Hamiltonian cycles in planar cubic graphs with facial 2-factors, and a new partial solution of Barnette's Conjecture
Behrooz Bagheri Gh., Tomas Feder, Herbert Fleischner +1
We study the existence of hamiltonian cycles in plane cubic graphs G having a facial 2-factor Q. Thus hamiltonicity in G is transformed into the existence of a (quasi) spanning tre…