Degenerate matchings and edge colorings

被引：16
作者：
Baste, Julien [1 ,2 ]
Rautenbach, Dieter [3 ]
机构：
[1] Sorbonne Univ, CNRS, Lab Informat Paris 6, F-75005 Paris, France
[2] Univ Montpellier, LIRMM, Montpellier, France
[3] Ulm Univ, Inst Optimizat & Operat Res, Ulm, Germany
来源：
DISCRETE APPLIED MATHEMATICS | 2018年 / 239卷
关键词：
Matching; Edge coloring; Induced matching; Acyclic matching; Uniquely restricted matching; STRONG CHROMATIC INDEX; MAXIMUM INDUCED MATCHINGS; GRAPHS;
D O I：
10.1016/j.dam.2018.01.002
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A matching M in a graph G is r-degenerate if the subgraph of G induced by the set of vertices incident with an edge in M is r-degenerate. Goddard, Hedetniemi, Hedetniemi, and Laskar (Generalized subgraph-restricted matchings in graphs, Discrete Mathematics 293 (2005) 129-138) introduced the notion of acyclic matchings, which coincide with 1 degenerate matchings. Solving a problem they posed, we describe an efficient algorithm to determine the maximum size of an r-degenerate matching in a given chordal graph. Furthermore, we study the r-chromatic index of a graph defined as the minimum number of r-degenerate matchings into which its edge set can be partitioned, obtaining upper bounds and discussing extremal graphs. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码：38 / 44
页数：7
相关论文
共 32 条
  • [1] LARGE INDUCED DEGENERATE SUBGRAPHS
    ALON, N
    KAHN, J
    SEYMOUR, PD
    [J]. GRAPHS AND COMBINATORICS, 1987, 3 (03) : 203 - 211
  • [2] Large induced forests in sparse graphs
    Alon, N
    Mubayi, D
    Thomas, R
    [J]. JOURNAL OF GRAPH THEORY, 2001, 38 (03) : 113 - 123
  • [3] THE STRONG CHROMATIC INDEX OF A CUBIC GRAPH IS AT MOST 10
    ANDERSEN, LD
    [J]. DISCRETE MATHEMATICS, 1992, 108 (1-3) : 231 - 252
  • [4] On the Number of Labeled Graphs of Bounded Treewidth
    Baste, Julien
    Noy, Marc
    Sau, Ignasi
    [J]. GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2017), 2017, 10520 : 88 - 99
  • [5] Bau S, 2002, J Australas Combin, V25, P285
  • [6] Combinatorial optimization on graphs of bounded treewidth
    Bodlaender, Hans L.
    Koster, Arie M. C. A.
    [J]. COMPUTER JOURNAL, 2008, 51 (03) : 255 - 269
  • [7] Bruhn H., 2015, ELECT NOTES DISCRETE, V49, P277, DOI DOI 10.1016/J.ENDM.2015.06.038
  • [8] The graphs with maximum induced matching and maximum matching the same size
    Cameron, K
    Walker, T
    [J]. DISCRETE MATHEMATICS, 2005, 299 (1-3) : 49 - 55
  • [9] INDUCED MATCHINGS
    CAMERON, K
    [J]. DISCRETE APPLIED MATHEMATICS, 1989, 24 (1-3) : 97 - 102
  • [10] Induced matchings in intersection graphs
    Cameron, K
    [J]. DISCRETE MATHEMATICS, 2004, 278 (1-3) : 1 - 9
1234