35 citations · 100 across the 34 of their papers we have counts for
15 papers · 1 filter
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 the Kernel and Related Problems in Interval Digraphs
Mathew C. Francis, Pavol Hell, Dalu Jacob
Given a digraph , a set is said to be absorbing set (resp. dominating set) if every vertex in the graph is either in or is an in-neighbour (resp. out-neigh…
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…
Interval-Like Graphs and Digraphs
Pavol Hell, Jing Huang, Ross M. McConnell +1
We unify several seemingly different graph and digraph classes under one umbrella. These classes are all broadly speaking different generalizations of interval graphs, and include,…
Complexity of Correspondence Homomorphisms
Tomas Feder, Pavol Hell
Correspondence homomorphisms are both a generalization of standard homomorphisms and a generalization of correspondence colourings. For a fixed target graph , the problem is to…
The complexity of signed graph and edge-coloured graph homomorphisms
Richard C. Brewster, Florent Foucaud, Pavol Hell +1
We study homomorphism problems of signed graphs from a computational point of view. A signed graph is a graph where each edge is given a sign, positive or negative; $Σ\…