A note on the largest induced matching in graphs avoiding a fixed bipartite graph
Ben LundDaniel Reichman
所有作者
Ben LundDaniel Reichman
文献摘要
We give a simple proof that every n-vertex graph d-regular graph that
does not contain a fixed bipartite graph as a subgraph has an induced matching
of size Ω((n/d)(logd)).