Happy Coloring

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 homophily in social networks, we consider the algorithmic aspects …

Given an undirected graph $G=(V,E)$ with $|V|=n$ and a vertex coloring, a vertex $v$ is happy if $v$ and all its neighbors have the same color. An edge is happy if its end vertices have the same color. Given a partial coloring of the vertices of the …