Degenerate matchings and edge colorings

Julien Baste 1, 2 Dieter Rautenbach 3
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 APR - Algorithmes, Programmes et Résolution
LIP6 - Laboratoire d'Informatique de Paris 6
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 metadatas

Cited literature [8 references]  Display  Hide  Download
Contributor : Gestionnaire Hal-Upmc <>
Submitted on : Wednesday, April 25, 2018 - 11:14:07 AM
Last modification on : Wednesday, March 27, 2019 - 1:34:00 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⟩



Record views


Files downloads