Variants of the Hajnal-Szemerédi Theorem

The Hajnal-Szemerédi Theorem [Hajnal & Szemerédi, Colloq Math Soc J Bolyai, 1970] states that a graph with hk vertices and minimum degree at least (h − 1)k contains k vertex disjoint copies of K_h. Its proof is not algorithmic. Here, we present an algorithm that, for a fixed h, finds in such a graph k − C(h) vertex disjoint copies of K_h in polynomial time in k, C(h) being a constant depending on h only. The proof suggests a variant of the theorem for h-partite graphs, which is conjectured here and proven in a slightly weaker form in some special cases. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 275–282, 1999     

The list colouring constants

We present a conjecture concerning list colourings and prove a weakened form of it. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 149–153, 1999     

Acrylic improper colorings of graphs

In this article, we introduce the new notion of acyclic improper colorings of graphs. An improper coloring of a graph is a vertex-coloring in which adjacent vertices are allowed to have the same color, but each color class V_i satisfies some condition depending on i. Such a coloring is acyclic if there are no alternating 2-colored cycles. We prove that every outerplanar graph can be acyclically 2-colored in such a way that each monochromatic subgraph has degree at most five and that this result is best possible. For planar graphs, we prove some negative results and state some open problems. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 97–107, 1999     

Hamilton cycles in block-intersection graphs of triple systems

Given a BIBD S = (V, B), its 1-block-intersection graph G_s has as vertices the elements of B; two vertices B₁, B₂ ∈ B are adjacent in G_s if |B₁ ∩ B₂| = 1. If S is a triple system of arbitrary index λ, it is shown that G_S is hamiltonian. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 243-246, 1999     

若干图的强染色

图 G(V,E)的一正常 k-染色 σ称为 G(V,E)的 - k-强染色当且仅当对任何两个不同顶点 u和 v,只要d(u,v)≤ 2 ,则 u、v染不同颜色 (这里 d(u,v)表示 u,v之间的距离 ) ,并称 xs(G) =min{ k|存在 G的 - k-强染色 }为 G的强色数 ,本文得到 θ-图 ,Cm,n图 ,Halin图的强色数 xs(G)     

既不含4-圈又不含6-圈的平面图的非正常染色

设d₁, d₂,..., d_k是k个非负整数. 若图G=(V,E)的顶点集V能被剖分成k个子集V₁, V₂,...,V_k, 使得对任意的i=1, 2,..., k, V_i的点导出子图G[V_i] 的最大度至多为d_i, 则称图G是(d₁, d₂,...,d_k)-可染的. 本文证明既不含4-圈又不含6-圈的平面图是(3, 0, 0)-和(1, 1, 0)-可染的.     

Perfect 3-colorings on 6-regular graphs of order 9

The concept of a perfect coloring, introduced by P. Delsarte, generalizes the concept of completely regular code. We study the perfect 3-colorings (also known as the equitable partitions into three parts) on 6-regular graphs of order 9. A perfect n-colorings of a graph is a partition of its vertex set. It splits vertices into n parts A1, A2,...,An such that for all i,j∈{1,2,...,n}, each vertex of Ai is adjacent to aij vertices of Aj. The matrix A =(aij)n×n is called quotient matrix or parameter matrix. In this article, we start by giving an algorithm to find all different types of 6-regular graphs of order 9. Then, we classify all the realizable parameter matrices of perfect 3-colorings on 6-regular graphs of order 9.     

Phase transition for SIR model with random transition rates on complete graphs

We are concerned with the susceptible-infective-removed (SIR) model with random transition rates on complete graphs C _n with n vertices. We assign independent and identically distributed (i.i.d.) copies of a positive random variable ξ on each vertex as the recovery rates and i.i.d. copies of a positive random variable ρ on each edge as the edge infection weights. We assume that a susceptible vertex is infected by an infective one at rate proportional to the edge weight on the edge connecting these two vertices while an infective vertex becomes removed with rate equals the recovery rate on it, then we show that the model performs the following phase transition when at t = 0 one vertex is infective and others are susceptible. There exists λ _c > 0 such that when λ < λ _c ; the proportion r∞ of vertices which have ever been infective converges to 0 weakly as n → +∞ while when λ > λ _c ; there exist c(λ) > 0 and b(λ) > 0 such that for each n ≥ 1 with probability p ≥ b(λ); the proportion r_∞ ≥ c(λ): Furthermore, we prove that λ _c is the inverse of the production of the mean of ρ and the mean of the inverse of ξ.     

基于车身装配结构优化的改进图分解算法

在考虑车身制造和装配成本的前提下对车身装配结构优化方法进行了研究,提出一种改进的图分解算法将车身装配结构最优地分解为一组部件.以白车身侧围的装配模型为例,将结构的几何图形转化为与之对应的关系拓扑图,再分割该关系拓扑图为一组工程约束下的单连通不交叉子图集,结合遗传算法中的算子操作,利用有限单元法分析并计算得到产品几何图形的最优分割,采用NSGA-Ⅱ算法并实现该装配体综合性能最优的目标.