用构造性方法计算多重图Ramsey数的界  

Bounds for multigraph Ramsey numbers calculated by the constructive method

作　　者：赵文飞[1] 梁美莲[2] 许晓东[3] 陈挚[1] 

机构地区：[1]国防科学技术大学理学院,湖南长沙410073 [2]广西大学数学与信息科学学院,广西南宁530004 [3]广西科学院,广西南宁530007

出　　处：《广西大学学报（自然科学版）》2009年第6期832-835,共4页Journal of Guangxi University（Natural Science Edition）

基　　金：广西自然科学基金资助项目(0991074);广西科学院基本科研业务费资助项目(09YJ17XX01)

摘　　要：在图的边染色问题中,通常考虑的是每条边染且只染一种颜色。边的集染色是这种边染色的一种推广,使每条边对应的不一定是一种颜色,而是给定的颜色集的一个子集。多重图的边染色与边的集染色是等价的。多重图Ramsey数是经典Ramsey数的一种自然的推广,它是通过把完全图的边染色推广到完全多重图的边染色实现的。计算Ramsey数的准确值是NP难题,求多重图Ramsey数的准确值往往更加困难。用一些研究经典Ramsey数的方法来研究2-多重图Ramsey数的界,利用构造性方法证明了一些关于不同参数的2-多重图Ramsey数的不等式,并在此基础上得出了一些小参数多重图Ramsey数的准确值或上下界。In edge-coloring problems of graphs, each edge is often colored in one and only one color. Set-coloring of edges is a generalization of such a kind of edge coloring, in which every edge is mapped to a subset of a given color set instead of one color. Edge-coloring of multigraphs is the same to the set-coloring of edges in graphs. The multigraph Ramsey number is a natural generalization of the classical Ramsey number, given by generalizing the edge coloring of simple complete graphs to the edge coloring of complete muhigraphs. Computing the values of Ramsey numbers is NP hard, and it is even difficult to compute the values of multigraph ones. Some methods of studying classical Ramsey numbers are used to obtain bounds for 2-multigraph Ramsey numbers in this paper. Some inequalities on different 2-multigraph Ramsey numbers are proved by the constructive method, and based on what values or bounds for some small multigraph Ramsey numbers are given.

关 键 词：RAMSEY数 多重图 集染色 

分 类 号：O157.5[理学—数学]