Degenerate matchings and edge colorings - Sorbonne Université Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2018

Degenerate matchings and edge colorings

Résumé

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.
Fichier principal
Vignette du fichier
Degenerate_Matchings.pdf (254.52 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01777928 , version 1 (25-04-2018)

Identifiants

Citer

Julien Baste, Dieter Rautenbach. Degenerate matchings and edge colorings. Discrete Applied Mathematics, 2018, 239, pp.38-44. ⟨10.1016/j.dam.2018.01.002⟩. ⟨hal-01777928⟩
899 Consultations
143 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More