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)|$$?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Ilya Bogdanov
    Commented 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$
    – Gerhard Paseman
    Commented 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
    Commented 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$
    – Dominic van der Zypen
    Commented 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$
    – Ilya Bogdanov
    Commented Apr 4, 2016 at 10:25

You must log in to answer this question.

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