2017/02/08 by Julien Baste, Dieter Rautenbach, Baste, Julien +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1702.02358
openalex publication_date 2017/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.