完全多部图和笛卡儿积图的线性点荫度  

The Vertex Linear Arboricity of Complete Multiple Graphs and Cartesian Product Graphs

作　　者：房勇[1] 吴建良[2] 

机构地区：[1]山东大学数学院 [2]山东矿业学院济南校区

出　　处：《山东矿业学院学报》1999年第3期59-61,共3页Journal of Shandong University of Science and Technology(Natural Science)

摘　　要：图的线性点荫度是对它的顶点进行染色所用的最少颜色数，同时使得染同一种颜色的点集所导出的子图，它的每个分支均为路．本文完全确定了完全多部图的线性点荫度，给出了笛卡儿积图的线性点荫度的一个上界，得到了一些特殊图（ 如路，圈和完全图） 的笛卡儿积图的线性点荫度．The vertex linear arboricity of graph G is the least number of colors with which V(G) can be colored such that each subset of vertices received same color induces a subgraph whose connected components are paths. In the paper, we determined the vertex linear arboricity of complete multiple graphs and provided an upper bound for the vertex linear arboricity of Cartesian product graphs.

关 键 词：图 完全多部图 笛卡儿积图 线性点荫度 

分 类 号：O157.5[理学—数学]