Maximal Induced Matchings in Triangle-Free Graphs

被引：7
|
作者：
Basavaraju, Manu [1 ]
Heggernes, Pinar [2 ]
van't Hof, Pim [3 ]
Saei, Reza [2 ]
Villanger, Yngve [2 ]
机构：
[1] Natl Inst Technol Karnataka, Dept Comp Sci & Engn, Mangalore 575025, India
[2] Univ Bergen, Dept Informat, Bergen, Norway
[3] Rotterdam Univ Appl Sci, Sch Built Environm, Rotterdam, Netherlands
来源：
JOURNAL OF GRAPH THEORY | 2016年 / 83卷 / 03期
基金：
欧洲研究理事会;
关键词：
maximal induced matchings; triangle-free graphs; polynomial delay; combinatorial bounds; extremal graphs; INDEPENDENT SETS;
D O I：
10.1002/jgt.21994
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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) approximate to 1.5849(n) maximal induced matchings, and this bound is the best possible. We prove that every n-vertex triangle-free graph has at most 3(n/3) approximate to 1.4423(n) maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K-3,K-3. Our result implies that all maximal induced matchings in an n-vertex triangle-free graph can be listed in time O(1.4423(n)), yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph. (C) 2015 Wiley Periodicals, Inc.
引用
收藏
页码：231 / 250
页数：20
相关论文
共 50 条
  • [21] More about sparse halves in triangle-free graphs
    Razborov, A. A.
    SBORNIK MATHEMATICS, 2022, 213 (01) : 109 - 128
  • [22] Triangle-free graphs with large independent domination number
    Shiu, Wai Chee
    Chen, Xue-gang
    Chan, Wai Hong
    DISCRETE OPTIMIZATION, 2010, 7 (1-2) : 86 - 92
  • [23] The fractional chromatic number of triangle-free graphs with Δ ≤ 3
    Lu, Linyuan
    Peng, Xing
    DISCRETE MATHEMATICS, 2012, 312 (24) : 3502 - 3516
  • [24] The Four-in-a-Tree Problem in Triangle-Free Graphs
    Derhy, Nicolas
    Picouleau, Christophe
    Trotignon, Nicolas
    GRAPHS AND COMBINATORICS, 2009, 25 (04) : 489 - 502
  • [25] A note on Reed's conjecture for triangle-free graphs
    Abrishami, Gholamreza
    Erfanian, Ahmad
    DISCRETE MATHEMATICS, 2023, 346 (12)
  • [26] The Four-in-a-Tree Problem in Triangle-Free Graphs
    Nicolas Derhy
    Christophe Picouleau
    Nicolas Trotignon
    Graphs and Combinatorics, 2009, 25 : 489 - 502
  • [27] Enumerating Minimal Dominating Sets in Triangle-Free Graphs
    Bonamy, Marthe
    Defrain, Oscar
    Heinrich, Marc
    Raymond, Jean-Florent
    36TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2019), 2019,
  • [28] Some spectral inequalities for triangle-free regular graphs
    Koledin, Tamara
    Stanic, Zoran
    FILOMAT, 2013, 27 (08) : 1561 - 1567
  • [29] Colouring vertices of triangle-free graphs without forests
    Dabrowski, Konrad K.
    Lozin, Vadim
    Raman, Rajiv
    Ries, Bernard
    DISCRETE MATHEMATICS, 2012, 312 (07) : 1372 - 1385
  • [30] Coloring triangle-free graphs with local list sizes
    Davies, Ewan
    de Joannis de Verclos, Remi
    Kang, Ross J.
    Pirot, Francois
    RANDOM STRUCTURES & ALGORITHMS, 2020, 57 (03) : 730 - 744
12345