A note on the largest induced matching in graphs avoiding a fixed bipartite graph

preprint2020arXivOpen access

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)(\log d))$ .

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Write a reviewWrite

No reviews yet.

Add a commentWrite

No comments yet.

A note on the largest induced matching in graphs avoiding a fixed bipartite graph

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0