For a nontrivial connected graph $G$, let $c:V\left(G\right)\to \mathbb{N}$ be a vertex coloring of $G$ where adjacent vertices may be colored the same. For a vertex $v\in V\left(G\right)$, the neighborhood color set $\mathrm{NC}\left(v\right)$ is the set of colors of the neighbors of $v$. The coloring $c$ is called a set coloring if $\mathrm{NC}\left(u\right)\ne \mathrm{NC}\left(v\right)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum number of colors required of such a coloring is called the set chromatic number ${\chi }_{\mathrm{s}}\left(G\right)$. We show that the decision variant of determining ${\chi }_{\mathrm{s}}\left(G\right)$ is NP-complete in the general case, and show that ${\chi }_{\mathrm{s}}\left(G\right)$ can be...

We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k ≥ 2. Moreover, we provide a complete characterisation of (ψ2 − γ1)- perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure of graphs belonging...