A note on a Caro-Wei bound for the bipartite independence number in graphs

DOI10.1016/J.DISC.2020.112285MaRDI QIDQ2659196zbMATH OpenOpenAlexFDO

Authors Shimon Kogan

Publication date 25 March 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.03730

zbMATH Keywords

bi-holesindependent set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: 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 $nimesn$ bipartite graph $G$, let $$ be the largest $k$ for which $G$ has a bi-hole of size $k$. We prove that [ �eta(G) geq left lfloor frac{1}{2} cdot sum_{v in V(G)} frac{1}{d(v)+1} ight floor. ] Furthermore, we prove the following generalization of the result above. Given an $nimesn$ bipartite graph $G$, Let $$ be the largest $k$ for which $G$ has a $kimesk$ $d$-degenerate subgraph. We prove that [ �eta_d(G) geq left lfloor frac{1}{2} cdot sum_{v in V(G)} minleft(1,frac{d+1}{d(v)+1} ight) ight floor. ] Notice that $$.

Recommendations

• Bipartite independence number in graphs with bounded maximum degree
• A note on bipartite subgraphs of triangle-free regular graphs
• scientific article; zbMATH DE number 4008428
• Bipartite subgraphs
• Bipartite subgraphs of H-free graphs

Cites work

• Balanced coloring of bipartite graphs
• Large induced degenerate subgraphs

Cited in

(3)

• scientific article; zbMATH DE number 6808069 (Why is no real title available?)
• Bipartite independence number in graphs with bounded maximum degree
• Extremal bipartite independence number and balanced coloring

This page was built for publication: A note on a Caro-Wei bound for the bipartite independence number in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2659196)