排序方式: 共有4条查询结果,搜索用时 0 毫秒
1
1.
董进全 《内蒙古大学学报(自然科学版)》1992,23(4):465-467
图G的曼荫度vas(G)定度为对G进行项点着色且使得G中同色顶点导出的子图的每个连通分支都为星时所需的最少色数,本文证明了平面图和外平面图的曼荫度的平凡上界事实上也是最好的上界. 相似文献
2.
Halin图和Series—Parallel图的星荫度 总被引:1,自引:1,他引:0
证明了:(1)所有Halin图的星荫度为3,和(2)所有Series-Parallel图的星荫度小于等于3。 相似文献
3.
A star forest is a forest whose components are stars. The star arboricity of a graph G,denoted by sa( G),is the minimum number of star forests needed to decompose G. Let k be a positive integer. A k-star forest is a forest whose components are stars of order at most k + 1. The k-star arboricity of a graph G,denoted by sak( G),is the minimum number of k-star forests needed to decompose G. In this paper,it is proved that if any two vertices of degree 3 are nonadjacent in a subcubic graph G then sa2( G) ≤2.For general subcubic graphs G, a polynomial-time algorithm is described to decompose G into three 2-star forests. For a tree T and[Δ k, T)/k]t≤ sak( T) ≤[Δ( T)- 1/K]+1,where Δ( T) is the maximum degree of T.kMoreover,a linear-time algorithm is designed to determine whether sak( T) ≤m for any tree T and any positive integers m and k. 相似文献
4.
给出1-树图的某些结构性质,证明了2-边连通的1-树图G存在一个(△+2)-关联着色使得各项点的远关联被分配上相同的颜色,并确定了它的关联色数等△+1,这里△表示图的最大度。 相似文献
1