In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The Matching Cut problem is the problem of deciding whether a given graph has a matching cut.
Let $H$ be a fixed …
In an undirected graph, a proper $(k,i)$-coloring is an assignment of a set of $k$ colors to each vertex such that any two adjacent vertices have at most $i$ common colors. The $(k,i)$-coloring problem is to compute the minimum number of colors …
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 …
Let $H$ be a fixed undirected graph. A vertex coloring of an undirected input graph $G$ is said to be an $H$-Free Coloring if none of the color classes contain $H$ as an induced subgraph. The $H$-Free Chromatic Number of $G$ is the minimum number of …
In an undirected graph, a proper $(k,i)$-coloring is an assignment of a set of $k$ colors to each vertex such that any two adjacent vertices have at most $i$ common colors. The $(k,i)$-coloring problem is to compute the minimum number of colors …
In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The matching cut problem is the problem of deciding whether a given graph has a matching cut. The matching cut …
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 …