Given a graph G, the dominator coloring problem seeks a proper coloring of G with the additional property that every vertex in the graph dominates an entire color class. The safe clique partition problem seeks a partition of the vertices of a graph into cliques with the additional property that for each vertex v, there is a clique that has no element in the open neighborhood of v. We typically seek to minimize the number of color classes or cliques used, respectively. In this paper, we study these two problems and consider the relationship between them.
展开▼
