21 citations · 64 across the 26 of their papers we have counts for
30 papers
Odd Cycle Transversal in -Free Graphs
Akramah Faizi, Arash Rafiey
The Odd Cycle Transversal (OCT) problem, which asks for a minimum subset of vertices whose removal renders a graph bipartite, is a central problem in algorithmic graph theory. It i…
Interval H-graphs : Recognition and forbidden obstructions
Haiko Müller, Arash Rafiey
We introduce the class of interval -graphs, which is the generalization of interval graphs, particularly interval bigraphs. For a fixed graph with vertices $a_1,a_2,\dots,a_…
Min orderings and list homomorphism dichotomies for signed and unsigned graphs
Jan Bok, Richard Brewster, Pavol Hell +2
The CSP dichotomy conjecture has been recently established, but a number of other dichotomy questions remain open, including the dichotomy classification of list homomorphism probl…
Digraph homomorphism problem and weak near unanimity polymorphism
Tomas Feder, Jeff Kinne, Ashwin Murali +1
We consider the problem of finding a homomorphism from an input digraph to a fixed digraph . We show that if admits a weak near unanimity polymorphism then deciding…
Digraphs Homomorphism Problems with Maltsev Condition
Jeff Kinne, Ashwin Murali, Arash Rafiey
We consider a generalization of finding a homomorphism from an input digraph to a fixed digraph , HOM(). In this setting, we are given an input digraph together with…
Toward a Dichotomy for Approximation of -coloring
Akbar Rafiey, Arash Rafiey, Thiago Santos
Given two (di)graphs G, H and a cost function , in the minimum cost homomorphism problem, MinHOM(H), goal is finding a hom…