论文部分内容阅读
边染色图中的单色子图问题是目前图论研究领域的热点问题.Bollobás和Gyárfá猜想当n≥4k-3时,任意的2-边染色完全图Kn中都包含一个阶至少为n-2k+2的单色k-连通子图.当k=2,3时此猜想已经被证明是正确的,Liu等人证明了n≥13k-15时任意的2-边染色完全图Kn都包含一个阶至少为n-2k+2的单色k-连通子图.Fujita等人证明了当n≥6.5(k-1)时结论成立.一些学者将这个问题推广到完全多部图中,并得到若干结果.
本文中,我们主要考虑了边染色图中的单色k-连通子图阶的问题.
首先,研究了完全图Kn中的k-连通单色子图问题,我们完整刻画了完全图Kn(n≥13k-15)的所有2-边染色,使得完全图Kn中的单色k-连通子图的阶最多为n-2k+2.
然后,我们研究了2-边染色完全二部图和完全多部图中的2-连通单色子图的阶,给出了其精确值或者上下界,且其中上下界相差最多为1.
最后,对于完全图我们还证明了当n≥13时,任意的2-边染色完全图Kn,如果Kn中有一个最大阶为n-2k+2的单色k-连通子图(k=2,3),那么Kn中必有一个阶至少为n-6的单色4-连通子图.