关于图色常量的Shen Lin和Irving界  

0n bound of Shen Lin and Irving for a graph-coloring constant

作　　者：张成学[1] 林晓惠[1] 杨元生[1] 

机构地区：[1]大连理工大学计算机科学与工程系

出　　处：《大连理工大学学报》1991年第4期485-491,共7页Journal of Dalian University of Technology

摘　　要：令阿Ａｒ＝（ａ_１，ａ_２，…，ａ_ｒ），其中整数ａ_ｉ≥２，ｒ≥１.所谓图Ｇ的Ａｒ着色即对 图Ｇ的边用不同的颜色ｃ_1ｃ_2,…,ｃ_ｒ着色，使得没有一个ａ_ｉ个顶点的完全子 图的所有边都着色ｃ_ｉ（ｉ＝１，２，…，ｒ）．令ＨlＮ为具有Ｎ个顶点但不包含l个顶 点的完全子图的图的集合，Ｎ（Ａr,l）表示Ｇ∈ＨlＮ但不能被 Ａ 着色的图具有的 最少顶点数。本文定义一种临界图，并在此基础上利用Ｈ５（Ｎ－１）的临界图构造Ｈ５Ｎ 的临界图。通过证明Ｈ５（１２）的临界图均能（３，３）着色，证明Ｈ５（１２）中的图均能（３，３） 着色，进而得出：１３＜Ｎ（（３，３），５）＜１８，优于前人得出的１０＜Ｎ（（３，３），５）＜１８的结 果．Let Ar=(a1,a2,…,ar),a'is integers≥2, r≥1. By an Ar-coloring of a graph G the authors mean a coloring of the edges of G by distinct colors c1,c2, …,cr,so that there are no complete subgraphs on ai vertices whose edges are co1ored in ci(i=1,2,…,r).Let HlN denote the set of all graphs on N vertices which do not contain comp1ete subgraph on l yertices. Let N(Ar,l) denote the minimum N so that there exists a graph G∈HlN which cannot be Ar-colored. In this paper, the authors define a kind of critica1 graphs, and then using the critica1 graphs of H5(N-1),construct the critica1 graphs of H5N. By proving al1 the critica1 graphs of H5(12) can be (3,3)-colorcd, the authors prove that all the graphs in H5(12) can be (3, 3)-colored, so the authors improve N((3,3),5)'s lower bound to N((3,3)5,5)≥13. Before this paper, the best bound of N((3,3), 5) is 10≤N((3,3),5)≤18. so far, l3≤N((3,3),5)≤18, given in this paper, is the best bound of N((3, 3), 5).

关 键 词：拉姆塞理论 临界图 Ar着色 无效图 

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