期刊
DISCRETE APPLIED MATHEMATICS
卷 186, 期 -, 页码 19-44出版社
ELSEVIER
DOI: 10.1016/j.dam.2015.01.012
关键词
Clique-perfect graphs; Edge-coloring; Line graphs; Matchings
资金
- UBACyT [20020100100980]
- CONICET [PIP 112-200901-00178]
- ANPCyT (Argentina) [PICT-2012-1324]
- FONDECyT [1140787]
- Complex Engineering Systems Institute (ISCI, Chile)
A graph is clique-perfect if the maximum number of pairwise disjoint maximal cliques equals the minimum number of vertices intersecting all maximal cliques for each induced subgraph. In this work, we give necessary and sufficient conditions for the complement of a line graph to be clique-perfect and an O(n(2))-time algorithm to recognize such graphs. These results follow from a characterization and a linear-time recognition algorithm for matching-perfect graphs, which we introduce as graphs where the maximum number of pairwise edge-disjoint maximal matchings equals the minimum number of edges intersecting all maximal matchings for each subgraph. Thereby, we completely describe the linear and circular structure of the graphs containing no bipartite claw, from which we derive a structure theorem for all those graphs containing no bipartite claw that are Class 2 with respect to edge-coloring. (C) 2015 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据