
arXiv: 1702.02358
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.
Induced matching, matching, [INFO] Computer Science [cs], induced matching, Coloring of graphs and hypergraphs, Acyclic matching, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), acyclic matching, FOS: Mathematics, Matching, Mathematics - Combinatorics, Combinatorics (math.CO), uniquely restricted matching, edge coloring, Edge coloring
Induced matching, matching, [INFO] Computer Science [cs], induced matching, Coloring of graphs and hypergraphs, Acyclic matching, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), acyclic matching, FOS: Mathematics, Matching, Mathematics - Combinatorics, Combinatorics (math.CO), uniquely restricted matching, edge coloring, Edge coloring
| 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). | 16 | |
| 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% |
