8 citations · 36 across the 49 of their papers we have counts for
5 papers · 1 filter
Parameterized Orientable Deletion
Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis +2
A graph is -orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most . -orientability is a well-studied concept with close…
Token Sliding on Split Graphs
Rémy Belmonte, Eun Jung Kim, Michael Lampis +3
We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked i…
How Bad is the Freedom to Flood-It?
Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi +2
Fixed-Flood-It and Free-Flood-It are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is…
Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil +5
We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices ca…
Reconfiguration of Colorable Sets in Classes of Perfect Graphs
Takehiro Ito, Yota Otachi
A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c-coloring. In this paper, we study the problem of finding a step-by-step transformation…