Timeline for "Drinking number" of a graph
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 24, 2021 at 9:05 | vote | accept | Dominic van der Zypen | ||
| Apr 22, 2021 at 23:56 | answer | added | user195625 | timeline score: 12 | |
| Apr 22, 2021 at 23:18 | comment | added | Timothy Chow | @bof You should spell out the details and post that as an answer. | |
| Apr 22, 2021 at 22:15 | comment | added | bof | In human language, you want to color the vertices of a graph so that, for each vertex $v$, at most half the neighbors of $v$ have the same color as $v$. For a finite graph it's quite easy to show that $2$ colors are enough: just tale a $2$-coloring which minimizes the number of edges joining vertices of the same color. (I'm sure this question has been answered more than once on math.stackexchange but I can't find it now.) The answer is probably the same for infinite graphs but I haven't thought about that. | |
| Apr 22, 2021 at 21:24 | comment | added | Timothy Chow | I found a paper, Integer programming approach to static monopolies in graphs, whose abstract says, "A subset $M$ of vertices of a graph is called a static monopoly, if any vertex $v$ outside $M$ has at least $\lceil{1\over 2}\deg(v)\rceil$ neighbors in $M$." So the statement that $\mathrm{dr}(G)\le 2$ for a finite graph $G$ is equivalent to the statement that the vertex set of $G$ can be partitioned into two disjoint static monopolies. | |
| Apr 22, 2021 at 20:16 | comment | added | Dominic van der Zypen | I don't have such an example and would think that $\text{dr}(G) \leq 2$ for finite graphs. I have no idea about infinite graphs concerning the drinking number. | |
| Apr 22, 2021 at 15:55 | comment | added | Timothy Chow | What's an example where $\mathrm{dr}(G)\ge 3$? | |
| Apr 22, 2021 at 15:02 | history | edited | Dominic van der Zypen | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Apr 22, 2021 at 14:50 | history | asked | Dominic van der Zypen | CC BY-SA 4.0 |