一些积图的点可区别均匀边色数

本文研究了积图的点可区别均匀边染色问题.利用构造法得到了积图G×G的点可区别均匀边染色的一个结论,并且获得了等阶的完全图与完全图、星与星、轮与轮的积图的点可区别均匀边色数,验证了它们满足点可区别均匀边染色猜想(VDEECC).     

图M（Pn）和M（Gn）的点可区别均匀边染色

用构造法研究了路和圈的Mycielski图的点可区别均匀边染色,得到了路和圈的Mycielski图的点可区别均匀边色数,验证了它们满足点可区别均匀边染色猜想（VDEECC）．     

一些倍图的点可区别均匀边色数

如果图G的一个正常边染色满足任意两个不同点的关联边色集不同,且任意两种颜色所染边数目相差不超过1,则称为点可区别均匀边染色,其所用最少染色数称为点可区别均匀边色数.本文得到了星、扇和轮的倍图的点可区别均匀边色数.     

图M(S_n)和M(F_n)的点可区别均匀边色数

如果图G的一个正常边染色满足任意两个不同点的关联边色集不同,且任意两种颜色所染边数目相差不超过1,则称为点可区别均匀边染色(VDEEC),其所用最少染色数称为点可区别均匀边色数.本文用构造法研究了一些Mycielski图的点可区别均匀边染色,得到了星和扇的Mycielski图的点可区别均匀边色数,验证了它们满足点可区别均匀边染色猜想.     

图的一般邻点可区别均匀边染色和均匀全染色

提出了一般邻点可区别均匀边染色和全染色的新概念,研究了路P_n、圈C_n、星S_n、扇F_n、轮W_n、完全二部图K_(m,n)、2维平面网格图P_m×P_n的一般邻点可区别均匀边染色和全染色,具体给出这些图的一般邻点可区别均匀边染色和全染色指标.     

图K_(3,4)∨K_t的点可区别正常边染色

设f是图G的一个正常边染色.对任意x∈V(G),令S(x)表示与点x相关联的边的颜色所构成的集合.若对任意u,v∈V(G),u≠v,有S(u)≠S(v),则称f是图G的一个点可区别正常边染色.对一个图G进行点可区别正常边染色所需的最少的颜色的数目称为G的点可区别正常边色数,记为χ_s'(G).讨论了图K_(3,4)∨K_t的点可区别正常边染色及其色数,利用正多边形的对称性构造染色以及组合分析的方法,确定了图K_(3,4)∨K_t的点可区别正常边色数,得到了当t是大于等于2的偶数以及t是奇数且3≤t≤25时,χ_s'(K_(3,4)∨K_t)=t+7;当t是奇数且t≥27时,χ_s'(K_(3,4)∨K_t)=t+8.     

若干Mycielski图的点可区别均匀全色数

研究了一些Mycielski图的点可区别均匀全染色(VDETC),利用构造法给出了路、圈、星和扇的Mycielski图的点可区别均匀全色数,验证了它们满足点可区别均匀全染色猜想(VDETCC).     

三类平方图的点边邻点可区别全色数

根据平方图的结构性质,用穷染,递推的方法,讨论了路,圈,扇的平方图的点边邻点可区别全染色,得到了相应的色数,即并给出了一种染色方案.     

图K_3~cVK_t的点可区别正常边染色

图G的正常边染色称为是点可区别的,如果对G的任意两顶点的关联边的颜色构成的集合不同.对图G进行点可区别正常边染色所需要的最少颜色数称为图G的点可区别正常边色数,记为x_s'(G).给出了3阶空图与t阶完全图的联图的点可区别正常边色数.     

一些特殊图的Mycielski图的点可区别均匀全色数

讨论了路、圈、星的Mycielski图的点可区别均匀全染色问题,得到了其点可区别均匀全色数.     

棋盘图的几种染色

染色问题是图论的重要研究内容之一,采用一种全新的方法给出了一类特殊图——棋盘图的邻点可区别边染色和邻点可区别全染色,并给出了相应的色数.     

图的倍图与补倍图

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题．对简单图C，如果V（D（G））：V（G）∪V（G′）E（D（G））=E（C）∪E（C″）U{vivj′｜vi∈V（G），Vj′∈V（G′）且vivj∈E（G））那么，称D（C）是C的倍图，如果V（D（G））=V（C）∪V（G′），E（D（C））：E（C）∪E（G′）∪{vivj′}vi∈V（G），vj′∈V（G’）and vivj∈（G）），称D（C）是G的补倍图，这里G′是G的拷贝．本文研究了D（G）和D的色数，边色数，欧拉性，哈密顿性和提出了D（G） 的边色数是D（G）的最大度等公开问题．     

图的围长与无圈边色数之间的关系

对于一个图G的正常边着色，如果此种边着色使得该图没有2—色的圈，那么这种边着色被称为是G的无圈边着色．用d(G)表示图G的无圈边色数，即G的无圈边着色中所使用的最小颜色数．Alon N，Sadakov B and Zaks A在[1]中有如下结果：对于围长至少是2000△(G)log△(G)的图G，有d(G)≤△ 2，其中△是图G的最大度．我们改进了这个结果，得到了如下结论：对于围长至少是700△(G)log△(G)的图G，有d(G)≤△ 2．     

图的分散数

The decay number of a connected graph is defined to be the minimum number of the components of the cotree of the graph. Upper bounds of the decay numbers of graphs are obtained according to their edge connectivities. All the bounds in this paper are tight. Moreover, for each integer k between one and the upper bound, there are infinitely many graphs with the decay number k.     

5连通图中的可去边

An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G- e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated [1, 11, 14, 15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5- connected graph. Based on the properties, we proved that for a 5-connected graph G of order at least 10, if the edge-vertex-atom of G contains at least three vertices, then G has at least （3│G│ ＋ 2）/2 removable edges.     

关于扇和完全等二部图联图的边染色

得到了扇和完全等二部图联图的边色数.     

关于扇和完全等二部图联图的点可区别边染色

通过结构分析的方法,考虑各种不同情况,给出了一类联图的点可区别的边染色方法,并得到了它的点可区别的边色数.     

Constraint Propagation in Graph Coloring

In this paper we propose a method for integrating constraint propagation algorithms into an optimization procedure for vertex coloring with the goal of finding improved lower bounds. The key point we address is how to get instances of Constraint Satisfaction Problems (CSPs) from a graph coloring problem in order to give rise to new lower bounds outperforming the maximum clique bound. More precisely, the algorithms presented have the common goal of finding CSPs in the graph for which infeasibility can be proven. This is achieved by means of constraint propagation techniques which allow the algorithms to eliminate inconsistencies in the CSPs by updating domains dynamically and rendering such infeasibilities explicit. At the end of this process we use the largest CSP for which it has not been possible to prove infeasibility as an input for an algorithm which enlarges such CSP to get a feasible coloring. We experimented with a set of middle-high density graphs with quite a large difference between the maximum clique and the chromatic number.     

完全图的广义Mycielski图的邻强边染色

对|V(G)|≥3的连通图G,若κ-正常边染色法满足相邻点的色集合不相同,则称该染色法为κ-邻强边染色,其最小的κ称为图G的邻强边色数。张忠辅等学者猜想:对|V(G)|≥3的连通图G,G≠C_5其邻强边色数至多为△(G)+2,利用组合分析的方法给出了完全图的广义Mycielski图的邻强边色数,从而验证了图的邻强边染色猜想对于此类图成立。