On trees with a maximum proper partial 0-1 coloring containing a maximum matching

I prove that in a tree in which the distance between any two endpoints is even, there is a maximum proper partial 0-1 coloring such that the edges colored by 0 form a maximum matching.     

On star and caterpillar arboricity

We give new bounds on the star arboricity and the caterpillar arboricity of planar graphs with given girth. One of them answers an open problem of Gyárfás and West: there exist planar graphs with track number 4. We also provide new NP-complete problems.     

Graph Coloring with Adaptive Evolutionary Algorithms

This paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EAs). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution. This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping Genetic Algorithm (GGA) on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping (GA) and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity.     

关于多重联图的均匀全染色

对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数．本文证明了关于多重联图的若干情况下的均匀全色数定理,得到了若干特殊多重联图的均匀全色数．     

关于联图K_(2,n)∨P_m的邻点可区别的全染色

一个全染色被称为邻点可区别的如果它满足对任意两个相邻点所关联的色集合不同.本文给出了联图K2,n∨Pm的邻点可区别的全色数并且证明了它满足邻点可区别的全染色猜想.     

An approximation result for the interval coloring problem on claw-free chordal graphs

We study the problem of finding an acyclic orientation of an undirected graph, such that each (oriented) path is covered by a limited number k of maximal cliques. This is equivalent to finding a k-approximate solution for the interval coloring problem on a graph. We focus our attention on claw-free chordal graphs, and show how to find an orientation of such a graph in linear time, which guarantees that each path is covered by at most two maximal cliques. This extends previous published results on other graph classes where stronger assumptions were made.     

D(β)-vertex-distinguishing total coloring of graphs

A new concept of the D(β)-vertex-distinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger than β have different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it, is proposed in this paper. The D(2)-vertex-distinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented.     

图的邻点全和可区别全染色

设f:V(G)∪E(G)→{1,2,…,k}是图G的一个正常k-全染色。令■其中N(x)={y∈V(G)|xy∈E(G)}。对任意的边uv∈E(C),若有Φ(u)≠Φ(v)成立,则称f是图G的一个邻点全和可区别k-全染色。图G的邻点全和可区别全染色中最小的颜色数k叫做G的邻点全和可区别全色数,记为f tndi∑(G)。本文确定了路、圈、星、轮、完全二部图、完全图以及树的邻点全和可区别全色数,同时猜想:简单图G(≠K2)的邻点全和可区别全色数不超过△(G)+2。     

子立方无爪图的单射边色数至多为6

设$G$是一个图. 图$G$的一个单射边染色是指图$G$的一个边染色, 使得距离为$2$的两条边或者在同一个三角形中的两条边染不同的颜色. 图$G$的单射边色数是指图$G$的任意单射边染色所需要的最少颜色数. 关于单射边色数有一个猜想: 任意一个子立方图的单射边色数都不超过$6$. 在本文中, 我们证明了这个猜想对子立方无爪图是成立的, 并且给出图例说明上界$6$是紧的. 同时, 我们的证明隐含了求解这类图不超过$6$种颜色的单射边染色方案的一个线性时间算法.     

Maximizing H‐Colorings of Connected Graphs with Fixed Minimum Degree

For graphs G and H , an H‐coloring of G is a map from the vertices of G to the vertices of H that preserves edge adjacency. We consider the following extremal enumerative question: for a given H , which connected n‐vertex graph with minimum degree δ maximizes the number of H‐colorings? We show that for nonregular H and sufficiently large n , the complete bipartite graph is the unique maximizer. As a corollary, for nonregular H and sufficiently large n the graph is the unique k‐connected graph that maximizes the number of H‐colorings among all k‐connected graphs. Finally, we show that this conclusion does not hold for all regular H by exhibiting a connected n‐vertex graph with minimum degree δ that has more ‐colorings (for sufficiently large q and n ) than .