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.
Domaines
Informatique [cs]Origine | Fichiers produits par l'(les) auteur(s) |
---|
Loading...