Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs

We present in this article an evolutionary procedure for solving general optimization problems. The procedure combines efficiently the mechanism of a simple descent method and of genetic algorithms. In order to explore the solution space properly, periods of optimization are interspersed with phases of interaction and diversification. An adaptation of this search principle to coloring problems in graphs is discussed. More precisely, given a graphG, we are interested in finding the largest induced subgraph ofG that can be colored with a fixed numberq of colors. Whenq is larger or equal to the chromatic number ofG, then the problem amounts to finding an ordinary coloring of the vertices ofG.     

图的路色数问题的NP－完全性

一个给定的图是否存在用ｒ种颜色的正常Ｐｋ着色？称该问题为图的（ｋ，ｒ）路色数问题．本文研究其算法复杂性，并得到以下结果：对于任意给定的ｋ，２≤ｋ≤∞，图的（ｋ，２）路色数问题及直径为２的图的（ｋ，３）路色数问题都是ＮＰ－完全的；对于任意给定的ｋ，２≤ｋ≤∞，平面图的（ｋ，３）路色数问题也是ＮＰ－完全的．     

星和完全等二部图联图的点可区别均匀边染色

研究了星与完全等二部图的联图Sm∨Kn,n的点可区别均匀边染色。     

Pm×Kn的邻点可区别全色数

设G是简单图．设f是一个从V(G)∪E(G)到{1,2,…,k}的映射．对每个v∈V(G),令C_f(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}．如果f是k-正常全染色,且对任意u,v∈V(G),uv∈E(G),有C_f(u)≠C_f(v),那么称f为图G的邻点可区别全染色(简称为k-AVDTC)．数x_(at)(G)=min{k|G有k-AVDTC}称为图G的邻点可区别全色数．本文给出路P_m和完全图K_n的Cartesion积的邻点可区别全色数．     

3一致 C-超图的最小边数

混合超图是含有两类超边的超图,一类称为C-超边,一类称为D-超边,它们的区别主要体现在染色要求上．混合超图的染色,要求每一C-超边至少有两个点染相同的颜色,而每一D-超边至少有两个点染不同的颜色．所用的最大颜色数称为对应混合超图的上色数,所用的最小颜色数称为对应混合超图的下色数．上、下色数与边数有密切关系．作者在文献[2]中证明了具有最小上色数的3一致C-超图边数的一个下界为‘n(n-2)/3’,其中n为对应混合超图的顶点数．该文证明当n=2k 1时,该下界是可以达到的．     

Total chromatic number of one kind of join graphs

The total chromatic number χ_T(G) of a graph G is the minimum number of colors needed to color the elements (vertices and edges) of G such that no adjacent or incident pair of elements receive the same color. G is called Type 1 if χ_T(G)=Δ(G)+1. In this paper we prove that the join of a complete inequibipartite graph K_n1,n2 and a path P_m is of Type 1.     

Variations on the Theorem of Birkhoff – von Neumann and Extensions

 The theorem of Birkhoff – von Neumann concerns bistochastic matrices (i.e., matrices with nonnegative real entries such that all row sums and all column sums are equal to one). We consider here real matrices with entries unrestricted in sign and we extend the notion of permutation matrices (integral bistochastic matrices); some generalizations of the theorem are derived by using elementary properties of graph theory. Received: October 10, 2000 Final version received: April 11, 2002     

简单完整正则平面图

对简单完整正则平面图的特性和结构进行了分析和讨论 ,找出了简单完整正则平面图的可能的种类 .此外 ,对各种简单完整正则平面图的色数进行了求解 ,并用不同的方法给出了各个简单完整正则平面图的作色方案 .     

An inequality for the group chromatic number of a graph

We give an inequality for the group chromatic number of a graph as an extension of Brooks’ Theorem. Moreover, we obtain a structural theorem for graphs satisfying the equality and discuss applications of the theorem.     

Partitioning series-parallel multigraphs intoν*-excluding edge covers

We prove that, for any given vertexν* in a series-parallel graph G, its edge set can be partitioned into k= min{k′(G) 1,δ(G)} subsets such that each subset covers all the vertices of G possibly except forν*, whereδ(G) is the minimum degree of G and k′(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof.