7
$\begingroup$

Given a simple, finite, directed graph $G$, let's call a $2$-coloring of the vertices of $G$ is friendly if every vertex has an out-neighbour of the same color (while not all vertices are same-colored).

Broadly speaking, I wonder what graphs admit a friendly coloring. To be more specific:

Is it true that every simple, finite, directed graph with the minimum outdegree $3$ has a friendly coloring? If this is false, does there exist an integer $k\ge 4$ such that every directed graph with the minimum outdegree $k$ has a friendly coloring? If so, what is the smallest $k$ with this property?

The case $k=2$ is easy, but already the case $k=3$ seems nontrivial to me.

The same questions can also be asked for three or more colors.

$\endgroup$
0

1 Answer 1

8
$\begingroup$

Carsten Thomassen (1983) proved that a digraph with minimal out-degree at least 3 has two vertex-disjoint cycles, call them $C_1$, $C_2$ and color black and white respectively. Then proceed as follows: on each step we have some vertices already colored, and from each colored vertex there exists an edge to a vertex of the same color. Take a non-colored vertex, and start a path from it until you get a cycle or go to an already colored vertex, say to a white one. Color all this path (or cycle) white. So finally you get a friendly coloring.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .