Timeline for Are all infinite graphs $3$-weak-edge colorable?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 8, 2017 at 0:59 | comment | added | bof | @DominicvanderZypen By the way, HYL's proof actually shows that every graph is $3$-weak-edge list colorable: obviously, instead of using a global palette of $2k+1$ colors, you can color each edge $e$ with a color from its assigned list $L(e)$ of $2k+1$ colors. | |
| Nov 8, 2017 at 0:58 | comment | added | bof | @DominicvanderZypen But my involvement with the crime was only as an "accessory after the fact"; my contributions were the kind of suggestions I might have made if I were refereeing a paper. In the publication by HYL & Van der Zypen, you may acknowledge suggestions of "the anonymous Stack Exchange user bof" in the same way as you would acknowledge a referee's suggestions. | |
| Nov 7, 2017 at 14:32 | comment | added | Dominic van der Zypen | ... and @HYL solved it (and I asked the question). If any of you thinks this is worthwhile, drop me an e-mail at [my christian name].zypen at gmail | |
| Nov 7, 2017 at 14:29 | comment | added | Dominic van der Zypen | How about the 3 of us then? You added value to this thing with your remarks, @bof... | |
| Nov 7, 2017 at 11:25 | comment | added | bof | @DominicvanderZypen Perhaps it could be published somewhere. Not by me, of course; it was HYL's idea, not mine. | |
| Nov 7, 2017 at 11:01 | comment | added | Dominic van der Zypen | @bof that's actually right! Beautiful observation. I'm wondering whether your remark could be made into a short note to be published somewhere (seriously!) | |
| Nov 7, 2017 at 10:22 | comment | added | bof | @DominicvanderZypen This construction shows that, for any integer $k\ge0,$ the edges of any graph $G$ can be colored with $2k+1$ colors so that, for each vertex $v,$ there are edges of at least $\min\{\deg(v),\ k+1\}$ different colors incident with $v.$ | |
| Nov 5, 2017 at 21:32 | comment | added | bof | @DominicvanderZypen Doesn't this nice argument prove more: that the edges of any graph (finite or infinite, countable or uncountable) can be colored with three colors so that for any vertex $v:$ (1) if $v$ has finite degree $d$ then no color occurs on more than $\lceil d/2\rceil$ of the edges incident with $v;$ and (2) if $v$ has infinite degree than at least two colors occur on infinitely many of the edges incident with $v?$ | |
| Nov 5, 2017 at 15:38 | comment | added | Dominic van der Zypen | Thanks to both of you! I think with HYL's argument and @Wojowu's remark I can carry through the transfinite induction. | |
| Nov 5, 2017 at 15:38 | vote | accept | Dominic van der Zypen | ||
| Nov 5, 2017 at 11:33 | comment | added | Wojowu | I think this argument can be generalized to transfinite induction. The only thing we could possibly have to take care of is that at limit stages we won't have all edges around one vertex colored the same, but this is guaranteed by the construction: if there are two or more edges already colored, there will be two of different colors. | |
| Nov 5, 2017 at 11:21 | comment | added | HYL | Then there's no $i_v$. | |
| Nov 5, 2017 at 10:59 | history | answered | HYL | CC BY-SA 3.0 |