论文标题
图形中双方独立数的caro-wei上的注释
A note on a Caro-Wei bound for the bipartite independence number in graphs
论文作者
论文摘要
两部分图$ g $中的大小$ t $的双孔是$ g $的$ k_ {t，t，t} $的副本。鉴于$ n \ times n $ a $ a $ a $ g $，让$β（g）$是最大的$ k $，$ g $具有$ k $的双孔。我们证明\ [β（g）\ geq \ left \ lfloor \ frac {1} {2} {2} \ cdot \ sum_ {v \ in V（g）} \ frac {1} {1} {d（v）+1} +1}+right \ right \ rfloor。 \]此外，我们证明了上述结果的以下概括。考虑到$ n \ times n $二键图$ g $，让$β_d（g）$是$ g $具有$ k \ times k $ $ d $ d $ d $ -degenerate子图的最大$ k $。我们证明\ [β_d（g）\ geq \ left \ lfloor \ frac {1} {2} {2} \ cdot \ cdot \ sum_ {v \ in v（g）} \ min \ min \ left（1，\ frac {d+1}} \]请注意，$β_0（g）=β（g）$。
A bi-hole of size $t$ in a bipartite graph $G$ is a copy of $K_{t,t}$ in the bipartite complement of $G$. Given an $n \times n$ bipartite graph $G$, let $β(G)$ be the largest $k$ for which $G$ has a bi-hole of size $k$. We prove that \[ β(G) \geq \left \lfloor \frac{1}{2} \cdot \sum_{v \in V(G)} \frac{1}{d(v)+1} \right \rfloor. \] Furthermore, we prove the following generalization of the result above. Given an $n \times n$ bipartite graph $G$, Let $β_d(G)$ be the largest $k$ for which $G$ has a $k \times k$ $d$-degenerate subgraph. We prove that \[ β_d(G) \geq \left \lfloor \frac{1}{2} \cdot \sum_{v \in V(G)} \min\left(1,\frac{d+1}{d(v)+1}\right) \right \rfloor. \] Notice that $β_0(G) = β(G)$.
