随机正则图k-彩虹指数的渐近结果

摘要

设G是一个带有边染色的连通图,其中相邻边可以染相同颜色.G中的一棵树被称作彩虹树,如果该树中所有边都染不同颜色.给定整数k≥2,G的k-彩虹染色是一个边染色,满足对于G中的任意k元点集S,都存在一棵连接了S中所有顶点的彩虹树.G的k-彩虹指数rx(G)是G的k-彩虹染色所需的最少颜色数.本文主要研究了随机正则图的k-彩虹指数.我们利用边分裂引理和对某些随机图直径的估计证明了:对于固定整数k≥2和r≥2k+1,rx_(k)(G_(n,r))=O(logn)大概率成立,并且这个结果是渐近紧的.