21 citations · 31 across the 12 of their papers we have counts for
13 papers
List homomorphisms to separable signed graphs
Jan Bok, Richard Brewster, Tomás Feder +2
The complexity of the list homomorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees and refle…
On finding hamiltonian cycles in Barnette graphs
Behrooz Bagheri Gh., Tomas Feder, Herbert Fleischner +1
In this paper, we deal with hamiltonicity in planar cubic graphs G having a facial 2-factor Q via (quasi) spanning trees of faces in G/Q and study the algorithmic complexity of fin…
List homomorphism problems for signed trees
Jan Bok, Richard Brewster, Tomás Feder +2
We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph $…
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…