
We study extremal questions on induced matchings in several natural graph classes. We argue that these questions should be asked for twinless graphs, that is graphs not containing two vertices with the same neighborhood. We show that planar twinless graphs always contain an induced matching of size at least $n/40$ while there are planar twinless graphs that do not contain an induced matching of size $(n+10)/27$. We derive similar results for outerplanar graphs and graphs of bounded genus. These extremal results can be applied to the area of parameterized computation. For example, we show that the induced matching problem on planar graphs has a kernel of size at most $40k$ that is computable in linear time; this significantly improves the results of Moser and Sikdar (2007). We also show that we can decide in time $O(91^k + n)$ whether a planar graph contains an induced matching of size at least $k$.
Extremal problems in graph theory, Induced matching, parameterized algorithms, Outerplanar graphs, Computer Networks and Communications, Applied Mathematics, Twins, Planar graphs, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 004, Planar graphs; geometric and topological aspects of graph theory, Theoretical Computer Science, Kernel, Parameterized algorithms, Computational Theory and Mathematics, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), kernel, induced matchings, twinless graphs, bounded genus graphs, ddc: ddc:004
Extremal problems in graph theory, Induced matching, parameterized algorithms, Outerplanar graphs, Computer Networks and Communications, Applied Mathematics, Twins, Planar graphs, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 004, Planar graphs; geometric and topological aspects of graph theory, Theoretical Computer Science, Kernel, Parameterized algorithms, Computational Theory and Mathematics, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), kernel, induced matchings, twinless graphs, bounded genus graphs, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 56 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
