期刊
DISCRETE MATHEMATICS
卷 306, 期 12, 页码 1207-1216出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.disc.2005.09.016
关键词
near-bipartition; acyclic set; independent set
类别
For a given graph G, if the vertices of G can be partitioned into an independent set and an acyclic set, then we call G a near-bipartite graph. This paper studies the recognition of near-bipartite graphs. We give simple characterizations for those near-bipartite graphs having maximum degree at most 3 and those having diameter 2. We also show that the recognition of near-bipartite graphs is NP-complete even for graphs where the maximum degree is 4 or where the diameter is 4. (c) 2006 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据