无指定相交圈的非负特征图的列表点荫度

On list Vertex Arboricity of Graphs with Nonnegative Characteristic without Cycles of Specific Length

对于图的任一顶点集的划分,并使每个划分的导出子图均为无圈图的最小的划分基数称为图的顶点荫度.对于图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.