均衡的完全3-部3-一致超图的单色放松路划分

李婷婷 张 霞

( 山东师范大学数学与统计学院,250358,济南 )

1 引 言

路划分问题起源于Gerencsér和Gyárfás[1](1967年)提出的一个基本的命题: 对于n个顶点的完全图Kn的任意的一个2-边染色, 它的顶点集V(Kn)可以被划分成一条红色路和一条蓝色路. 这里的空集和单点可以看作是染任意颜色的一条路. 1979年，Lehel猜想用圈代替上述命题中的路结论仍然成立. 对于n很大时Lehel猜想在文献[2]和[3]中被证实, 并且在2010年由Bessy和Thomassé[4]证得对所有的n都成立.

对于超图的情形, 本文先介绍论文中所用的一些基本概念和相关符号表示, 若未提及的概念和符号表示请参考文献[5]和[6].

一个k-一致超图H, 有l条超边e1,e2,e3,…,el满足对任意的i∈[l-1], 有|ei∩ei+1|=1并且对于2≤i+1

图G(或超图H)的一个边染色是从边集E(G)(或E(H))到颜色集的一个映射φ:E(G)→{1,2,3,…,k}(或E(H)). 上述称为图G(或超图H)的k种颜色的边染色, 简记为k-边染色. 本文主要讨论2-边染色, 一般用红色和蓝色来叙述.

2013年, Gyárfás和Sárközy[7]提出了一个关于完全的3-一致超图的单色划分的问题.

2018年,Bustamante, Hán和Stein证得下面的引理1.

值得注意的是对于放松圈(loose cycle)上述结论同样成立. 另外，引理1中ηn可以被改进.

目前对于完全超图的边染色的单色划分的研究结果相对较少, 对于完全的k-部k-一致超图的边染色的单色划分问题还没有相关的结果, 完全的k-部k-一致超图相对于完全超图研究起来更复杂, 对边的要求更苛刻. 本文研究均衡的完全3-部3-一致超图的单色放松路的划分, 为以后研究一般的k-部k-一致超图的单色划分问题打下基础.

2 结论及其证明

证s≤2时，结论显然成立. 下……