A conflict-free coloring of a graph $G$ is a (partial) coloring of its vertices such that every vertex $u$ has a neighbor whose assigned color is unique in the neighborhood of $u$. There are two variants of this coloring, one defined using the open …
Given an undirected graph $G = (V,E)$, a conflict-free coloring with respect to open neighborhoods (CFON coloring) is a vertex coloring such that every vertex has a uniquely colored vertex in its open neighborhood. 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.
Let $H$ be a fixed …
A _Conflict-Free Open Neighborhood coloring_, abbreviated CFON* coloring, of a graph $G = (V,E)$ using $k$ colors is an assignment of colors from a set of $k$ colors to a subset of vertices of $V(G)$ such that every vertex sees some color exactly …
In an undirected graph $G$, a conflict-free coloring with respect to open neighborhoods (denoted by CFON coloring) is an assignment of colors to the vertices such that every vertex has a uniquely colored vertex in its open neighborhood. The minimum …
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 …
Given an undirected graph, a conflict-free coloring (CFON*) is an assignment of colors to a subset of the vertices of the graph such that for every vertex there exists a color that is assigned to exactly one vertex in its open neighborhood. The …
The _closed neighborhood conflict-free chromatic number_ of a graph $G$, denoted by $\chi_{CN}(G)$, is the minimum number of colors required to color the vertices of $G$ such that for every vertex, there is a color that appears exactly once in its …
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 …
In an undirected graph $G$, a conflict-free coloring with respect to open neighborhoods (denoted by CFON coloring) is an assignment of colors to the vertices such that every vertex has a uniquely colored vertex in its open neighborhood. The minimum …