首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到17条相似文献,搜索用时 93 毫秒
1.
孙磊  高波 《数学进展》2001,30(4):377-380
星色数的概念最早是由Vince作为图的色数的推广而引入的.本文研究了两类图乘积G×H,G[H]的星色数.  相似文献   

2.
图的星色数     
李德明 《数学进展》1999,28(3):259-265
给出了一些星色数为4的平面图,它们不含有轮图作为子图,这回答了Zhu的一个问题,给出了一类4连通平面图其星色数在3与4之间,这也回答了Abbott和Zhou的一个问题,应用图的同态概念,讨论了某些图的字典积的星色数,证明了一个图及其补图的星色数的和与积所满足的两个不等式。  相似文献   

3.
王志雄 《数学研究》1995,28(4):91-94
本文给出互补图的星色数所满足的一些必要条件,并确定一些图类的星色数.  相似文献   

4.
图的星色数的概念是Vince在1988年提出的,它是图的色数的一个推广.本文构造了一类星色数是4的平面图.  相似文献   

5.
设G为n阶简单图,λ2(G)为G的第二大特征根.我们给出了所有使λ2(G)<1 的偶图,以及使λ2(G)<1、围长不小于4的非偶图.  相似文献   

6.
陈晏 《经济数学》2001,18(1):87-91
图 G的围长是指 G中最短圈的长度 ;若 G没有圈 ,则定义 G的围长为无究大 .本文研究有 v个顶点 ,围长至少为 n+1图的最大边数 ,记作 ex{ v,{ C3 ,C4 ,… ,Cn} ) .我们称这种围长至少为 n+1,并具有最多边的图为极图 .我们将讨论这种极图的一个重要性质 ,即极图度的分布  相似文献   

7.
将一个图的所有最大匹配作为顶点集,称两个最大匹配相邻,若它们之一通过交换一条边得到另一个,由引所得图为该图的最大匹配图。本文研究了最大匹配图的围长,从而给出了最大匹配图是树或完全图的条件。  相似文献   

8.
李德明 《数学学报》2004,47(5):1031-103
图的星色数是通常色数概念的推广.本文求出了几类由轮图导出的平面图的星色数.前两类是由3-或5-轮图经细分等构造出的,其星色数分别为2+2/(2n+1),2+3/(3n+1)和2+3/(3n-1).第三类平面图是由n-轮图经过Hajos构造得到的,其星色数为3+1/n.本类图的星色数结果推广了已有结论.  相似文献   

9.
图的最大亏损及围长   总被引:3,自引:0,他引:3       下载免费PDF全文
图的最大亏损主要由其参数Betti亏数确定(例如,见[3]).本文给出了由图的独立数及围长所确定的Betti亏数的一个最好上界 ,从而即可得到关于图的最大亏格的一个新结果.  相似文献   

10.
樊锁海  谢虹玲 《应用数学》2004,17(2):271-276
图X称为弱点传递图如果X的自同态幺半群EndX在顶点集V(X)上的作用是传递的 .本文给出了广义Petersen图是二分图的充要条件 ,刻划了奇围长小于 9的广义Petersen图的弱点传递性 ,作为推论给出了所有h ≤ 1 5的弱点传递的广义Pe tersen图P(h ,t) .  相似文献   

11.
超图的强星色数   总被引:3,自引:0,他引:3  
图的星色数的概念是由A.Vince(1988)首次提出来的,它是图的色数的一个自然而又重要的推广,L.Hadad等人(1994)将这一概念推广到一致超图,定义了h-一致超图的强(弱)星色数,这里我们给出一般超图的强星色数的概念,研究了它的基本性质,计算了3-一致循环超图的强星色数,它们的强星色数形成了一个严格介于3和4之间的递减序列.  相似文献   

12.
本文得到了m 1阶星和完全等二部图联图的边色数和均匀全色数.  相似文献   

13.
推广的奇轮的圆色数   总被引:1,自引:0,他引:1  
图G的圆色数(又称"星色数")xc(G)是Vince在1988年提出的,它是图的色数 的自然推广.本文由奇轮出发构造了一族平面图,并证明了此类图的圆色数恰恰介于2和 3之间,填补了该领域的空白.  相似文献   

14.
The Star Chromatic Numbers of Some Planar Graphs Derived from Wheels   总被引:1,自引:0,他引:1  
The notion of the star chromatic number of a graph is a generalization of the chromatic number. In this paper, we calculate the star chromatic numbers of three infinite families of planar graphs. The first two families are derived from a 3-or 5-wheel by subdivisions, their star chromatic numbers being 2+2/(2n + 1), 2+3/(3n + 1), and 2+3(3n−1), respectively. The third family of planar graphs are derived from n odd wheels by Hajos construction with star chromatic numbers 3 + 1/n, which is a generalization of one result of Gao et al. Received September 21, 1998, Accepted April 9, 2001.  相似文献   

15.
三类笛卡尔积图的关联色数   总被引:2,自引:0,他引:2  
图的关联色数的概念是 Brualdi和 Massey于 1 993年引入的 ,它同图的强色指数有密切的关系 .Guiduli[2 ] 说明关联色数是有向星萌度的一个特殊情况 ,迄今仅确定了某些特殊图类的关联色数 .本文给出了完全图与完全图、圈与完全图、圈与圈的笛卡尔积图的关联色数。  相似文献   

16.
We investigate the notion of the star chromatic number of a graph in conjunction with various other graph parameters, among them, clique number, girth, and independence number.  相似文献   

17.
An acyclic coloring of a graph is a proper vertex coloring such that the union of any two color classes induces a disjoint collection of trees. The more restricted notion of star coloring requires that the union of any two color classes induces a disjoint collection of stars. We prove that every acyclic coloring of a cograph is also a star coloring and give a linear-time algorithm for finding an optimal acyclic and star coloring of a cograph. If the graph is given in the form of a cotree, the algorithm runs in O(n) time. We also show that the acyclic chromatic number, the star chromatic number, the treewidth plus 1, and the pathwidth plus 1 are all equal for cographs.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号