2
$\begingroup$

Let $G=(V,E)$ be a directed graph. For $v\in V$ set $\text{In}(v)=\{x\in V: (x,v)\in E\}$.

Is it possible to find a partition $P_1,P_2,P_3$ of $V$ such that for every $P_i$ and every vertex $v\in P_i$ we have $$|\text{In}(v)\cap P_i| \leq |\text{In}(v)\cap(V\setminus P_i)|$$?

$\endgroup$
4
  • 3
    $\begingroup$ It is very similar to your previous question on majority colouring, yes? $\endgroup$ Apr 2, 2016 at 19:29
  • 1
    $\begingroup$ How may this hold when $In(v)$ is empty? Maybe, $\leqslant$ sign is more reasonable? $\endgroup$ Apr 2, 2016 at 21:13
  • $\begingroup$ @Fedor it is very similar but now specifically asks for the number of $3$. $\endgroup$ Apr 3, 2016 at 6:27
  • $\begingroup$ Right about your comment on empy in-sets, will modify question. $\endgroup$ Apr 3, 2016 at 6:28

1 Answer 1

1
$\begingroup$

Suppose you have a edge (A,B), and B has at most two incoming edges. Then A and B must get different colors in order for the inequality to be preserved. Now have C get an edge from each of A and B. With no other incoming edges to C or B, this "mini-tournament" must get three colors.

Now add D, E, F so that B and C lead to D, C and D to E, D and E to F. With no other edges involved, we get a repeated coloring with A and D getting the same color, as do B and E, and C and F.

Now have the snake come and bite its own tail. Make a bracelet of these vertices. If we have the number of vertices be a multiple of 3, then a coloring exists. Otherwise not.

Gerhard "Or Oroubourous Or Orrery Or..." Paseman, 2016.04.02.

$\endgroup$
8
  • $\begingroup$ If a snail bites its tail, $B$ gets more than two in-edges, so the whole machinery does not work, does it? $\endgroup$ Apr 2, 2016 at 21:57
  • $\begingroup$ @Ilya, I think you are hooking it up wrong. Try this though: have 7 vertices 0 through 6, with (using mod 7 notation) edges (i,i+1) and (i,i+2). Let me know when you find a coloring for Dominic of this graph. Gerhard "Do Snails Even Have Tails?" Paseman, 2016.04.02. $\endgroup$ Apr 3, 2016 at 4:17
  • $\begingroup$ Did you see Fedor's comment about empty $In(v)$? This happens when the indegree is zero. $\endgroup$
    – joro
    Apr 3, 2016 at 6:30
  • $\begingroup$ Thanks Gerhard, I am trying to see the intuition and partially succeeding, but still have trouble with the snake tail part. $\endgroup$ Apr 3, 2016 at 7:35
  • $\begingroup$ I do not say your example is wrong; just the reasoning looks strange. Also, the example on 7 vertices does not work (for the new formulation)... $\endgroup$ Apr 4, 2016 at 10:25

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.