Is there a problem of graph coloring (and what is its name) defined as: If a node is colored with one color all adjacent nodes will have the same color. What is minimal number of colors to do that?
For example, for graph shown on Picture, the minimal number of colors is 4.
PS. When you start from one node (randomly) you color it and all adjacent nodes in the same color (for example red). When you do that, red cannot be used any more.
On
The answer depends on the graph.
Take long chain graph on $n$ vertices. Picking any vertex will not color more than $3$ vertices at any point in time, therefore it takes $\Theta(n)$ colors to color the graph.
In the star-graph on $n$ vertices, the probability to pick the central vertex is $\frac{1}{n}$, i.e. with high probability it is not picked in the first step. But any picked vertex will define the coloring of the central vertex, and it will not be candidate for further color-picking anymore, resulting in $n-1$ colors picked w.h.p.
In general graph, you color at most $\Delta + 1$ vertices by any one color, so it should be lower bounded by $\Omega\left(\frac{n}{\Delta}\right)$ colors.
The problem, as edited, is a reformulation of the dominating set problem (minimal number of vertices that need to be marked such that all other vertices are adjacent to a marked vertex), which is NP-complete.