$F$-WORM colorings: Results for 2-connected graphs

Given two graphs $F$ and $G$, an $F$-WORM coloring of $G$ is an assignment of colors to its vertices in such a way that no $F$-subgraph of $G$ is monochromatic or rainbow. If $G$ has at least one such coloring, then it is called $F$-WORM colorable and $W^{-}(G,F)$ denotes the minimum possible number of colors. Here, we consider $F$-WORM colorings with a fixed 2-connected graph $F$ and prove the following three main results: (1) For every natural number $k$, there exists a graph $G$ which is $F$-WORM colorable and $W^{-}(G,F)=k$; (2) It is NP-complete to decide whether a graph is $F$-WORM colorable; (3) For each $k \ge |V(F)|-1$,itisNP-completetodecidewhetheragraph$G$satisfies$W^-(G,F) \le k$\mathrm{.}Thisremainsvalidontheclassof$F$-WORM colorable graphs of bounded maximum degree. For complete graphs $F=K_n$ with $n\ge 3$ we also prove: (4) For each $n\ge 3$ there exists a graph $G$ and integers $r$ and $s$ such that $s\ge r+2$, $G$ has $K_n$-WORM colorings with exactly $r$ and also with $s$ colors, but it admits no $K_n$-WORM colorings with exactly $r+1, \dots, s-1$colors\mathrm{.}Moreover,thedifference$s-r$ can be arbitrarily large.