Degenerate matchings and edge colorings
Degenerate matchings and edge colorings
复制标题
DOI：
10.1016/j.dam.2018.01.002
复制
发表时间：
2018-04-20
影响因子：
1.1
通讯作者：
Rautenbach, Dieter
中科院分区：
文献类型：
--
作者：
Baste, Julien;Rautenbach, Dieter
图G中的一个匹配M是r-退化的，如果G中与M中的一条边关联的顶点集所诱导的子图是r-退化的.戈达德、Hedetniemi、Hedetniemi和Laskar（Generalized subgraph-restricted matching in graphs，Discrete Mathematics 293（2005）129-138）引入了非循环匹配的概念，其与1退化匹配一致。解决他们提出的一个问题，我们描述了一个有效的算法来确定在一个给定的弦图的r-退化匹配的最大尺寸。此外，我们研究了图的r-色指数，得到了上界，并讨论了极图。(C)2018 Elsevier B. V.版权所有。
A matching M in a graph G is r-degenerate if the subgraph of G induced by the set of vertices incident with an edge in M is r-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 r-degenerate matching in a given chordal graph. Furthermore, we study the r-chromatic index of a graph defined as the minimum number of r-degenerate matchings into which its edge set can be partitioned, obtaining upper bounds and discussing extremal graphs. (C) 2018 Elsevier B.V. All rights reserved.