Induced matchings in graphs of degree at most 4

Autor:	Nguyen, Viet Hang
Rok vydání:	2014
Předmět:	Computer Science - Discrete Mathematics Mathematics - Combinatorics
Druh dokumentu:	Working Paper
Popis:	We show that if $G$ is a connected graph of maximum degree at most $4$, which is not $C_{2,5}$, then the strong matching number of $G$ is at least $\frac{1}{9}n(G)$. This bound is tight and the proof implies a polynomial time algorithm to find an induced matching of this size. Comment: 14 pages, 12 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1407.7604 Zobrazit plný text záznamu View this record from Arxiv