Skip to Main content Skip to Navigation
Journal articles

Degenerate matchings and edge colorings

Abstract : A matching in a graph is -degenerate if the subgraph of induced by the set of vertices incident with an edge in is -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 -degenerate matching in a given chordal graph. Furthermore, we study the -chromatic index of a graph defined as the minimum number of -degenerate matchings into which its edge set can be partitioned, obtaining upper bounds and discussing extremal graphs.
Document type :
Journal articles
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Gestionnaire Hal-Upmc Connect in order to contact the contributor
Submitted on : Wednesday, April 25, 2018 - 11:14:07 AM
Last modification on : Tuesday, January 4, 2022 - 3:50:53 AM
Long-term archiving on: : Tuesday, September 25, 2018 - 1:58:45 PM


Files produced by the author(s)



Julien Baste, Dieter Rautenbach. Degenerate matchings and edge colorings. Discrete Applied Mathematics, Elsevier, 2018, 239, pp.38-44. ⟨10.1016/j.dam.2018.01.002⟩. ⟨hal-01777928⟩



Les métriques sont temporairement indisponibles