本文研究关于图的展开性与彩虹数的几个问题：（1）利用鞅论中的Azuma不等式和有限群表示论研究半点传递图与随机双陪集图的集中性质（concentration）；（2）对Daniely和Linial[21]提出的关于图的半着色（semi-coloring）的公开问题给出了肯定回答，且用概率方法得到了关于正则图边着色数的上界估计；（3）利用Fan分解得到了计算极大外平面图的彩虹数上界的多项式时间算法；（4）对树宽度有界的图给出了计算其彩虹数上界的一个线性时间参数算法，且能够在多项式时间内判断所得上界的好坏。第一章介绍图的展开性及彩虹数的背景知识、一些基本定义和记号。在第二章，基于Tanner[56]得到的关于有界强集中子（bounded strongconcentrator）与其特征值的关系，利用鞅论中的Azuma不等式及有限群表示论证明了几乎所有的半点传递图是有界强集中子，且构造了如下几类半点传递的有界强集中子：（2,2）阶广义六角二部图;大Mathieu群给出的唯一的设计Mi所对应的图XMi（i∈{22,23,24}）；小Mathieu群给出的唯一的设计Di所对应的图XDi（i∈{9,10,11,12}）；以及利用对称群构造的系列半点传递图。Daniely与Linial [21]利用图的提升定义了一种图之间的运算-紧积（tightproduct），并用之研究图的展开性。在紧积的存在性的证明中，他们提出了图的半着色概念及如下的公开问题：是否每一个图都有一个半着色？我们在第三章对此问题给出了肯定的回答，且用概率方法给出了一个关于正则图的边着色数的上界。在第四章，我们给出了极大Fan的彩虹数和相关的彩虹着色，引入极大外平面图的极大Fan分解概念；基于极大势搜索（maximal cardinality search）算法和极大外平面图的极大Fan分解，给出了一个计算极大外平面图的彩虹数上界的多项式时间算法且举出了达到上界的例子以说明算法的最优性。在第五章，我们基于在算法设计特别是近似算法设计中广泛应用的“divideand conquer”思想，给出了图的彩虹数的类似于“divide and conquer”的结果；并利用此结果和Ford算法的思想，给出了一个计算具有较小树宽度的图的彩虹数的上界的线性时间算法以及达到紧的上界的例子，且能在多项式时间内判断我们得到的上界的好坏。