作者：王纪辉近似二部图边覆盖染色最小度顶点边覆盖色数
摘要：设G是一个简单图，其顶点集为V（G）而边集为E（G）．S包含E（G）称为G的一个边覆盖，如果由S导出的子图是G的一个生成子图．G的边覆盖色数X’c（G）是E（G）所能划分成的最大边覆盖数．已知δ-1≤X’c（G）≤δ，由此将X＇c（G）=δ的图称为CⅠ类图，否则称为CⅡ类图．显然，图的边覆盖染色分类问题是NP-完全的．给出了近似二部图是CⅠ类图的一个充分条件，而且该条件中的下界是最好的．
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
《山东大学学报·理学版》（CN：37-1389/N）是一本有较高学术价值的大型月刊，自创刊以来，选题新奇而不失报道广度，服务大众而不失理论高度。颇受业界和广大读者的关注和好评。 《山东大学学报·理学版》为理工科综合性学术期刊。旨在反映该校自然科学领域中的最新研究成果，促进学术交流，活跃学术思想。
杂志详情
