Graph coloring problem?

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.

• Sorry, I edited it. Commented Jul 6, 2019 at 10:31
• In that picture there's a blue dot with 3 adjacent nodes not same color. Commented Jul 6, 2019 at 10:33
• Do you mean adjacent nodes same but not same as node starting it? Commented Jul 6, 2019 at 10:35
• Then in any graph can just color all nodes same. Then uses only 1 color. Commented Jul 6, 2019 at 10:39
• Each node just has one color, right? Commented Jul 6, 2019 at 10:41

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.

• Is it? Seems like this problem might have more constraints. To me, it seems likein the problem in OP's question, each vertex should be either a marked vertex or adjacent to exactly one marked vertex (though this is not entirely clear), whereas in the dominating set problem an unmarked vertex is allowed to be adjacent to any number of marked vertices. Commented Jul 6, 2019 at 11:42
• @Calle The picture implies that you can choose vertices, but in sequence, to minimise the colour count, and then one colour = one dominating vertex. Remember that no vertex can be left uncoloured, and that each vertex only gets one colour. Commented Jul 6, 2019 at 11:46
• Right, any solution to this problem is also a dominating set. However, not all dominating sets will be solutions to this problem. Commented Jul 6, 2019 at 11:48

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.

• It's asking for the minimum number of colours needed (see my answer). Commented Jul 6, 2019 at 11:30