17 citations · 50 across the 13 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.DS2017★ 15 cited
Algorithms and hardness results for happy coloring problems
N. R. Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare +1
In a vertex-colored graph, an edge is happy if its endpoints have the same color. Similarly, a vertex is happy if all its incident edges are happy. Motivated by the computation of…
cs.CC2017
On the Complexity of Restoring Corrupted Colorings
Marzio De Biasi, Juho Lauri
In the \probrFix problem, we are given a graph , a (non-proper) vertex-coloring , and a positive integer . The goal is to decide whether a proper -colori…