MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Maximal Induced Matchings in Triangle-Free Graphs

Reza Saei
University of Bergen
AG1 Mittagsseminar (own work)

An induced matching in a graph is a set of edges whose endpoints induce a 1-regular subgraph. It is known that every n-vertex graph has at most 10^(n/5) ≈ 1.5849^n maximal induced matchings, and this bound is best possible. We prove that every n-vertex triangle-free graph has at most 3^(n/3) ≈ 1.4423^n maximal induced matchings, and this bound is attained by every disjoint union of copies of the complete bipartite graph K_{3,3}.
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Tuesday, 10 February 2015
13:00
30 Minutes
E1 4
024
Saarbrücken

Contact

Erik Jan van Leeuwen
--email hidden
passcode not visible
logged in users only

Erik Jan van Leeuwen, 02/03/2015 11:31
Erik Jan van Leeuwen, 01/29/2015 09:47 -- Created document.