Timeline for Partitioning finite directed graphs into 3 "incoming-sparse" sets
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 20, 2017 at 13:05 | vote | accept | Dominic van der Zypen | ||
| Apr 4, 2016 at 15:39 | comment | added | Gerhard Paseman | @DominicvanderZypen, when the strict inequality holds, one can have a chain x_0, x_1,... of vertices with edges (x_i,x_i+1) and (x_i,x_i+2) and as a result this limits the permissible partitions to residue classes mod 3. Turn it into a cycle, and then no or one permissible partitions result, depending on the number mod 3 of vertices. Unfortunately I don't know how to show the same claim with the weak inequality. Gerhard "Permissible Partitions Are Strictly Sensitive" Paseman, 2016.04.04. | |
| Apr 4, 2016 at 15:31 | comment | added | Gerhard Paseman | Yes, when the inequality is relaxed, I am having trouble finding an uncolorable example. The closest I have is various pendants coming off a 4-cycle, where one can get some pendants restricted to two colors. However, connecting these pendants to one another throws things off. Gerhard "Pendant Dependence Leaves Me Hanging" Paseman, 2016.04.04. | |
| Apr 4, 2016 at 11:37 | comment | added | Dominic van der Zypen | Does anyone see how to make a full blown answer out of Gerhard's thoughts? I can't see his proof yet... | |
| Apr 4, 2016 at 10:25 | comment | added | Ilya Bogdanov | 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)... | |
| Apr 3, 2016 at 7:35 | comment | added | Dominic van der Zypen | Thanks Gerhard, I am trying to see the intuition and partially succeeding, but still have trouble with the snake tail part. | |
| Apr 3, 2016 at 6:30 | comment | added | joro | Did you see Fedor's comment about empty $In(v)$? This happens when the indegree is zero. | |
| Apr 3, 2016 at 4:17 | comment | added | Gerhard Paseman | @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. | |
| Apr 2, 2016 at 21:57 | comment | added | Ilya Bogdanov | If a snail bites its tail, $B$ gets more than two in-edges, so the whole machinery does not work, does it? | |
| Apr 2, 2016 at 20:53 | history | answered | Gerhard Paseman | CC BY-SA 3.0 |