图乘积的星色数

星色数的概念最早是由Vince作为图的色数的推广而引入的.本文研究了两类图乘积G×H,G[H]的星色数.     

由轮图导出的某些平面图类的星色数

图的星色数是通常色数概念的推广.本文求出了几类由轮图导出的平面图的星色数.前两类是由3-或5-轮图经细分等构造出的,其星色数分别为2+2/(2n+1),2+3/(3n+1)和2+3/(3n-1).第三类平面图是由n-轮图经过Hajos构造得到的,其星色数为3+1/n.本类图的星色数结果推广了已有结论.     

图的星色数

给出了一些星色数为４的平面图,它们不含有轮图作为子图,这回答了Ｚｈｕ的一个问题,给出了一类４连通平面图其星色数在３与４之间,这也回答了Ａｂｂｏｔｔ和Ｚｈｏｕ的一个问题,应用图的同态概念,讨论了某些图的字典积的星色数,证明了一个图及其补图的星色数的和与积所满足的两个不等式。     

临界图的星色数

1988年,Vince定义了图的色数的一个推广——图的星色数,本文研究了有围长限制或有最大度限制的临界图的星色数,得到了三个新结果。     

互补图的星色数

本文给出互补图的星色数所满足的一些必要条件，并确定一些图类的星色数．     

超图的强星色数

图的星色数的概念是由Ａ．Ｖｉｎｃｅ（１９８８）首次提出来的,它是图的色数的一个自然而又重要的推广,Ｌ．Ｈａｄａｄ等人（１９９４）将这一概念推广到一致超图,定义了ｈ－一致超图的强（弱）星色数,这里我们给出一般超图的强星色数的概念,研究了它的基本性质,计算了３－一致循环超图的强星色数,它们的强星色数形成了一个严格介于３和４之间的递减序列．     

星色数在三与四之间的一些平面图类

本文构造出了星色数为３＋１／ｄ,３＋2（2ｄ－１）,３＋３／（３ｄ－１）,和３＋３／（３ｄ－２）的一些平面图类,从而部分解决了Ｖｉｎｃｅ的问题.     

团剖分问题的复杂性

本文考虑分离图和树的平方图上团剖分问题的复杂性.文中的图均为无向简单图,团是指完备子图.分离图是指其点集可剖分为一个团和一个独立集之并的图.图 G 的团剖分是一组边不相重的团,它们包含了 G 的每条边.成员最少的团剖分叫做最小团部分.这个最小成员数叫做团剖分数,记为 CP(G).图的团剖分问题是 NP—完全的.本文的一个结果是证明了分离图上的团剖分问题仍保持,NP—完全性.     

自同构群为Mathieu群的边本原图

一个图Γ称之为边本原图.若Γ的全自同构群作用在Γ的边集上是本原的.边本原图是一类重要的对称图,这类图不是很多,但一些著名的图,比如Heawood图,Tutte-Coxeter图和Higman-Sims图都是边本原图.我们通过构造陪集图的方法来研究边本原图,并给出了基柱为Mathieu群的几乎单群上边本原图的分类.     

给定割点数的简单连通图的最小EDS极图

图的EDS(偏心距离和)是图的一个类似于Wiener指数的另一个重要指数,近年来受到广泛的关注.2012年H.B.Hua等在Discrete Appl.Math.中的一篇关于图的EDS极图的论文中提出一个问题:哪些图是具有k个割点及最大或最小EDS的极图?通过研究图的EDS确定了给定割点数为k的简单连通图的最小EDS极图.     

Sm ∨ Kn,n的边色数和均匀全色数

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

推广的奇轮的圆色数

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

Some Theorems Concerning the Star Chromatic Number of a Graph

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.     

三类笛卡尔积图的关联色数

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

Acyclic and star colorings of cographs

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.     

The Star Chromatic Numbers of Some Planar Graphs Derived from Wheels

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.