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

摘要

令阿Ａｒ＝（ａ_１，ａ_２，…，ａ_ｒ），其中整数ａ_ｉ≥２，ｒ≥１.所谓图Ｇ的Ａｒ着色即对 图Ｇ的边用不同的颜色ｃ_1ｃ_2,…,ｃ_ｒ着色，使得没有一个ａ_ｉ个顶点的完全子 图的所有边都着色ｃ_ｉ（ｉ＝１，２，…，ｒ）．令ＨlＮ为具有Ｎ个顶点但不包含l个顶 点的完全子图的图的集合，Ｎ（Ａr,l）表示Ｇ∈ＨlＮ但不能被 Ａ 着色的图具有的 最少顶点数。本文定义一种临界图，并在此基础上利用Ｈ５（Ｎ－１）的临界图构造Ｈ５Ｎ 的临界图。通过证明Ｈ５（１２）的临界图均能（３，３）着色，证明Ｈ５（１２）中的图均能（３，３） 着色，进而得出：１３＜Ｎ（（３，３），５）＜１８，优于前人得出的１０＜Ｎ（（３，３），５）＜１８的结 果．