Let $k\ge2$ be a fixed integer. Bollob\'as and Scott proved that every $3$-uniform hypergraph with $m$ edges admits a partition of its vertex set into $k$ parts such that each part spans at most $m/k^3+O_k(m^{6/7})$ edges. Scott later suggested that the error term should be $O_k(m^{2/3})$. In this paper, we show that e...
Fix an integer $d\ge1$. We prove that, for all sufficiently large $m$, every digraph $D$ with $m$ arcs and minimum semidegree at least $d$ admits a bisection $V(D)=V_1\cup V_2$ with $\bigl||V_1|-|V_2|\bigr|\le1$ such that \[ \min\{e(V_1,V_2),e(V_2,V_1)\} \ge \frac{d(m+d+1)}{2(2d+1)}. \] Here, for disjoint vertex sets $...
For a graph $G$, an odd induced subgraph of $G$ is an induced subgraph in which every vertex has odd degree (within the subgraph). Let $f_o(G)$ denote the maximum size of such a subgraph in $G$. Caro conjectured that there exists a positive constant $c$ such that $f_o(G)≥cn$ for any $n$-vertex graph without isolated ve...
Xin-Ru Yang, Qing-Hou Zeng· Annals of Applied Mathematic...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
