满足5色条件完全图的边着色 - 上海师范大学学报.pdf

维普资讯 第32卷第3期 上海师范大学学报 (自然科学版) VoI．32，No．3 2003年 9月 JournalofShanghaiNormalUniversity(NaturalSciences) Sep ．200 3 满足 5色 条件完全图的边着色 唐明元 (上海师范大学 数理信息学院，上海 200234) 摘 要：设K 是具有 ／,／个顶点的完全图， ／,／)是满足下列条件的最小正整数：对于任意的正 整数m ≥ ／,／)，存在K 的一个m边着色，使得 中的任一个 至少含 5种颜色．ErdOs和 Gy~nf6s给出了八n)的上下界：÷n n)n；并且证明了 9)=8．作者证明了 10)=9； 1 并且改进了 n)的下界 n)÷n+1． 关键词：花形图；正规花形 图；5色 条件 中图分类号：O157 文献标识码：A 文章编号：1000-5137(2003)03-0021-05 U 引 吾 设 G是一个有限、无向的简单图， (G)表示G的顶点集，E(G)表示G的边集， (G)和 (G)分 别表示G的顶点数和边数．如果图日满足：(日) V(G)，E(日) E(G)，则称 日是G的一个子图；如 果 (日)=V(G)，则称 日是G的一个生成子图．如果 是V(G)的一个非空子集，由 导出的G的子 图记为G[Va]．如果E 是E(G)的一个非空子集，由E 导出的G的子图记为G[E]．其他没有出现的 术语和记号参见 [1]．PaulErdSs在[2]的问题 l2中提出下列问题 ：设 是具有 n个顶点的完全图， n)是满足下列条件的最小正整数：对于任意的正整数m≥ n)，存在 的一个边着色，使得 中的 任一个 至少含5种颜色，求 n)．ErdSs和Gy6rfas给出了 n)的上下界：--q-‘n n)n，显然要求 ／,／满足：／,／≥6；并且指出，已经证明了 9)=8．本文证明了 10)=9；同时改进 了 ／,／)的下界 ／,／) T‘n+ 1， (n≥7)．即文 中的定理 1和定理 2． 1 基本概念和引理 定义1 设K 是具有 ／,／个顶点的完全图，m是一个正整数，如果存在 的一个m边着色，使得 中的任一个 至少含5种颜色，则称 关于m满足5色 条件 ，相应的m边着色称为满足5色 条 件的m边着色． 按照定义 1， ／,／)即为使K 满足5色 条件的最小正整数m． 定义2 设图G有一个m边着色，EV(G)，如果存在 ∈V(G)，使得 ∈E(G)，并且 着色 i (1≤i≤m)，则称色 i在顶点 上表现，并记为 =i． 为了方便起见，我们引进花形 图和正规花形图的概念． 收稿 日期：2002-12-30 基金项 目：上海市教委科技发展基金资助项 目(02DK06) 作者简介：唐明元(1953-)，男，上海师范大学数理信息学院副教授 维普资讯 上海师范大学学报 (自然科学版) 定义3 设 =u (i=1，2，…，n)是n个三角形，由上述n个三角形关于顶点u粘合而成的图， 称为具有n片花瓣的花形图(简称为n瓣花形图)，记为F，顶点u称为花心， =u 。称为花瓣 ，边u 和 u 称为花的内边 ，简称为 内边 ，边 1)i 称为花的外边 ，简称为外边． 设 F是具有 rl,片花瓣的花形图，显然 F=u ，(F)=2n+1，8(F)=3n． 定义4 设F=uTi是具有n片花瓣的花形图，Ti=ui；是一片花瓣，如果 的两条内边都着相 同的颜色，即 =u ，则称 是一片正规花瓣；如果对于F的每一片花瓣 (i=1，2，…，n)，都是正规 花瓣，则称 F是一个正规花形图． 下面的结论是显然的． 引理 1 设m是一个正整数， 是n个顶点的完全