How to minimize colors on graph Given an undirected graph on $n$ vertices, is there a way to determine the least number of colors necessary such that each clique of order three either


*

*shows a proper vertex coloring, or

*contains only one color,


given that we use at least three colors?
 A: We show the described coloring problem reduces to one in which the required minimum coloring is the same as a proper vertex coloring of a connected graph in which every edge belongs to a triangle ($3$-clique).
The problem is to "determine the least number of colors" which can be assigned to the $n$ vertices of a simple graph $G$ so that in each of its $3$-cliques, the three vertices are either monochromatic or properly colored (distinct colors for neighbors) provided that at least three colors are assigned.  Let's call this the Harry number of $G$, symbolically $H(G)$, and refer to the allowable colorings with at least three colors as Harry colorings.
If $n\lt 3$ it is impossible to assign three colors, so the Harry number $H(G)$ is technically undefined in those cases.  In view of this we assume hereafter $n\ge 3$.
Clearly $n$ colors always suffice in such a coloring (by assigning a different color to each vertex).  More precisely $H(G) \le \max(\chi(G),3)$, i.e. the Harry number is bounded above by the maximum of the chromatic number of $G$ and $3$.  An example of this bound being sharp is $G = K_n$, so $H(K_n) = \chi(K_n) = n$.  
Proposition  Let $G_0$ be the subgraph of $G$ with the same vertices but removing all edges that do not belong to any $3$-clique (triangle) of $G$.  Then $H(G_0) = H(G)$.
Proof By construction the $3$-cliques of $G$ and $G_0$ are the same.  Thus any Harry coloring of $G$ induces a Harry coloring of subgraph $G_0$, and $H(G_0) \le H(G)$.  On the other hand any Harry coloring of $G_0$ extends to a Harry coloring of $G$ since the edges added back are not part of any $3$-clique of $G$.  Therefore the reverse inequality holds, and $H(G_0) = H(G)$.
Note that if $G_0$ has at least three connected components, then $H(G) = H(G_0) = 3$ by choosing three distinct components and assigning a different monochromatic coloring to each of these (remaining components can also be colored mono-chromatically with any of the three colors).  Every $3$-clique is colored mono-chromatically, and exactly three colors are used.
If $G_0$ has two connected components, say $G_1$ and $G_2$, then at least one of them has enough vertices to admit a valid coloring (they cannot both be isolated nodes), and the number of colors required by $G_0$ is the minimum of the colors required by such validly colorable components.
Thus we can reduce consideration to a connected graph $G = G_0$ in which every edge belongs to a $3$-clique (triangle).  Note that in this simplified context the Harry number $H(G_0)$ is exactly the same as the chromatic number $\chi(G_0)$.
