图乘积的星色数

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

图的星临界性

图的星着色是图的正常着色的推广。本文对图的星临界性及其与图的临界性之间的关系进行研究，给出了两类星临界但非临界的平面图。     

一类星色数为4的平面图

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

临界图的边数

本文研究了△－临界图的边数下界，其中△＝１０，１１，１２，１３。     

互补图的星色数

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

边临界图的新下界

图$G$ 为简单的第二类连通图, 且对$G$ 的任意边$e$,有$chi^{prime}(G-e)相似文献   

图的星色数

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

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

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

边覆盖临界图的一些性质

设G是一个简单图,其顶点集为V(G)而边集为E(G),S∈E(G)称为 G的一个覆盖,如果由S导出的子图为G的一个生成子图. G的边覆盖色数χ'c(G)是E(G,)所能划分成的最大边覆盖数.已知δ-1 ≤χ'c(G)≤δ,由此将χ'c(G)=δ的图称为CI类图,否则称为CII类图.若G是连通CII类图,且G不是完全图,对任意的u,u∈V(G),e=uv( )E(G),都有χ'c(G+e)＞χ'c(G)成立,则称G为边覆盖临界的.本文研究了边覆盖临界图的一些性质.即若G为边覆盖临界图,则对任意的u,v∈V(G),若e=uv( )E(G),总存在w∈{u,v},有d(w)≤2δ-2,且w至少与max{d(w)-δ+1,3d(w)-4δ+4}个最小度顶点相邻.     

关于临界图的一个定理的推广

叶宏博证明了当Δ≥５时没有度序列是２ｒΔ２ｒ的Δ－临界图．Ｋａｙａｔｈｒｉ推广了上述结果,证明了当Δ≥５时,没有同时满足下列两个条件的Δ－临界图：（ａ）Ｇ有一个２度点ｘ;设ｙ,ｚ是ｘ的两个邻接点;（ｂ）有一主项点ｙ１∈ＮＧ（ｙ）（ｙ１≠ｙ）与－２度点邻接．我们对上述结果进一步推广,证明了条件（ｂ）不是必要的;只要ｙ１与一个度数小于Δ－１的点邻接即可（可以不是２度点）．     

ON THE MINIMUM COVERING NUMBER FORMULA OF GRAPHS

Throughout this paper,D=(d_1,d_2,...,d_n)denote a sequence of nonnegative inte-gers.We let(?)(D)denote the class of all graphs with degree sequence D,or equally,theclass of all symmetric(0,1)--matrices with trace 0 and row sum vector D.The structure matrix S=S(D) of D is a matrix of order n+1,whose entries are     

图的关联色数和关联着色猜想

本文综述了图的关联着色的已有结果，证明了关联着色猜想对于完全3—部图和高度留成立，确定了路、圈、扇、轮和加边轮等特殊图类的关联色数．     

几类图弱控制的广义束缚数

对任一图G,其弱控制的束缚数,广义束缚数分别定义为bw(G)=min{|E‖E(∪)E(G),且γw(G-E)＞γω(G)}.b'ω(G)=min{t|(A)E(∪)E(G),如果|E|=t,则有γω(G-E)＞γw(G)}.在本文中我们给出了几类图的弱控制的广义束缚数的精确值,称b'ω(G)=1图为弱控制去边临界图,并研究了正则图是弱控制去边临界图的充要条件,以及一般图和树的必要条件.     

CHROMATIC NUMBER OF SQUARE OF MAXIMAL OUTERPLANAR GRAPHS

Let x（G^2） denote the chromatic number of the square of a maximal outerplanar graph G and Q denote a maximal outerplanar graph obtained by adding three chords y1 y3, y3y5, y5y1 to a 6-cycle y1y2…y6y1. In this paper, it is proved that △ ＋ 1 ≤ x（G^2） ≤△ ＋ 2, and x（G^2） = A ＋ 2 if and only if G is Q, where A represents the maximum degree of G.     

图的最大亏格与图的着色数

结合边连通性,本文给出了一个图的Ｂｅｔｔｉ亏数由这个图的补图的着色数所确定的上界式,证明了所给出的上界式是最好的,得到关于图的最大亏格下界的若干新结果．     

关于图测地数的几个问题

本文研究了图的测地数.利用极点必属于测地集的方法,刻画了g(G)=n-1的图G的结构,同时使用图的一些重要参数,获得了图上下测地数的几个新的界.对于有向图D,讨论了g(D)=2的充要条件.     

极大外平面图的邻强边色数

本文证明了对极大外平面图 G,Δ(G) χ′as(G)≤ Δ(G) +1,且 χ′as(G) =Δ(G) +1,当且仅当存在两个最大度点相邻 .其中Δ (G)、χ′as(G)分别表示图 G的最大度和邻强边色数 .     

低度平面图的边面全色数

平面图G(V,E,F)的边面全色数X,(G)是使得集合E(G)∪ F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数。本文提出猜想:对任何平面图G,有△(G)≤X,(G)≤△(G)+3;并对顶点度不超过3或面度均为3的平面图证明了这个猜想为真。     

3-正则Halin-图全色数的注(英文)

本文讨论了△（G）＝3的Halin-图的金色数Xr（G）＝4的充分条件，并提出了3－正则Halin-图Xr（G）＝5的充分必要条件的猜想，其中△（G），Xr（G）分别表示G的最大度和全色数．     

极大外平面图的边面全色数

本文给出了△（Ｇ）≤６的极大外平面图的边面全色数，其中△（Ｇ）表示Ｇ的最大度。