10 papers
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
Robert Ganian, Thekla Hamm, Viktoriia Korchemna +2
The generic homomorphism problem, which asks whether an input graph admits a homomorphism into a fixed target graph , has been widely studied in the literature. In this arti…
Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws
Michał Dębski, Zbigniew Lonc, Karolina Okrasa +2
For graphs and , an -coloring of is an edge-preserving mapping from to . In the -Coloring problem the graph is fixed and we ask whether an instanc…
Computing list homomorphisms in geometric intersection graphs
Sándor Kisfaludi-Bak, Karolina Okrasa, Paweł Rzążewski
A homomorphism from a graph to a graph is an edge-preserving mapping from to . Let be a fixed graph with possible loops. In the list homomorphism problem,…
Vertex deletion into bipartite permutation graphs
Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk +2
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines and , one on each. A bipartite permutation graph is a p…
The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
Thomas Bellitto, Shaohua Li, Karolina Okrasa +2
The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is…
Sparsification Lower Bounds for List -Coloring
Hubie Chen, Bart M. P. Jansen, Karolina Okrasa +2
We investigate the List -Coloring problem, the generalization of graph coloring that asks whether an input graph admits a homomorphism to the undirected graph (possibly…