欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
设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Ⅰ类图的一个充分条件，而且该条件中的下界是最好的．
英文摘要：
Let G be a simple graph with vertex set V（G） and edge set E（G）. A subset S of E（G） is called an edge covering of G if the subgraph induced by S is a spanning subgraph of G. The maximum number of edge coverings which construct a partition of E（G） is called the edge covered chromatic index of G, denoted by X＇c （G）. It is well known that 8 - 1 ≤X＇c （G） ≤δ, then G is called a graph of CⅠ class if X＇c （G） = δ, otherwise G is called a graph of C Ⅱ class. It is easy to prove that the problem of deciding whether a given graph is CⅠ class or CⅡ class is NP-complete. A sufficient condition for a nearly bipartite graph to be CⅠ class is given. It is showen that the results are the best possible.
同期刊论文项目
同项目期刊论文
期刊信息
位置：