位置:成果数据库 > 期刊 > 期刊详情页
无指定相交圈的非负特征图的列表点荫度
  • 时间:0
  • 分类:O157.5[理学—数学;理学—基础数学]
  • 作者机构:淮阴师范学院数学科学学院,江苏淮安223300
  • 相关基金:国家自然科学基金资助项目(11501235);国家自然科学基金天元基金资助项目(11226285); 江苏省自然科学基金资助项目(BK20140451); 江苏省高校自然科学基金资助项目(15KJB110002)
作者: 张海辉
中文摘要:

对于图的任一顶点集的划分,并使每个划分的导出子图均为无圈图的最小的划分基数称为图的顶点荫度.对于图G的每个顶点给定一个列表基数至少为k的颜色集合,对于图的任一染色,若每个顶点的颜色均选择与其关联的颜色集,使得每种颜色类的导出子图是一个无圈图的最小的基数k称为图的列表点荫度.证明了每个无6圈和相交i,j-圈(i,j∈{3,4})的非负特征图的列表顶点荫度为2,即为4列表可选色.

英文摘要:

The vertex arboricity ρ (G) of a graph G is the minimum number of subsets into which vertex set V(G) can be partitioned so that each subset induces an acyclic graph. A graph G is called list vertex k-arbo- rable if for any sets L(v) of cardinality at least k at each vertex v of G, one can choose a color for each v from its list L(v) so that the subgraph induced by every color class is a forest. The smallest k for a graph to be list vertex k-arborable is denoted by ρl (G). We prove that any graph with nonnegative characteristic without cycles of intersecting cycles i,j-cycles for i,j {3,4} has ρ1 (G) ≤2 and is 4-choosable.

同期刊论文项目
同项目期刊论文