Timeline for Existence of bipartite subgraphs satisfying degree and edge cardinality constraints
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28, 2018 at 6:36 | comment | added | Fedor Petrov | if $d_G^{\max}=2k+1$ is odd, we get at least $\frac{k}{2k+1}|E|=\frac12|E|-\frac1{2(2k+1)}|E|$, and since $|E|\leqslant (2k+1)\min(|V_1|,|V_2|)$ this yields at least $\frac12(|E|-\min(|V_1|,|V_2|))$ edges. | |
| Feb 27, 2018 at 16:33 | vote | accept | Penelope Benenati | ||
| Feb 27, 2018 at 16:32 | comment | added | Penelope Benenati | Great! It is correct to say that if $d^{\max}_G$ is not necessarily even, using this approach would yield to replace condition (1) with the inequality $|E'| \ge \frac{1}{2}|E|-|V_1|-|V_2|$? | |
| Feb 27, 2018 at 8:13 | comment | added | Fedor Petrov | No, I mean $k$ most presented (or popular, or how do you call it) colors. | |
| Feb 27, 2018 at 5:27 | history | answered | Fedor Petrov | CC BY-SA 3.0 |