论文部分内容阅读
边染色图中的单色子图问题是目前图论研究领域的热点问题.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-连通子图.