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.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2018, 239, pp.38-44. 〈10.1016/j.dam.2018.01.002〉
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.sorbonne-universite.fr/hal-01777928
Contributeur : Gestionnaire Hal-Upmc <>
Soumis le : mercredi 25 avril 2018 - 11:14:07
Dernière modification le : lundi 18 mars 2019 - 14:59:08
Document(s) archivé(s) le : mardi 25 septembre 2018 - 13:58:45

Fichier

Degenerate_Matchings.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

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〉

Partager

Métriques

Consultations de la notice

172

Téléchargements de fichiers

14