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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.