论文部分内容阅读
图的染色与色数问题是图论中的一个重要研究内容，也是图论中的一个十分活跃的领域，且有着深刻而丰富的理论结果和广泛的实际应用，其理论和方法在离散数学中占有重要地位.
1999年，Irving和Manlove引入了图的b-染色数概念，并证明了：对于一般图来说，确定其b-染色数b(G)是一个Np-难问题；但对于树图来说却存在多项式时间算法.2004年，Faik引入图的b-连续的概念，并且证明了弦图是b-连续的.
本文的主要工作有：
(1)研究了方形网格的b-染色问题，给出其b-染色数，并且证明了Gnxn是b-连续的.
(2)提出了图的完全b-染色数和完全b-连续的概念，研究了路，圈，方形网格以及完全n叉树图的完全b-染色问题，给出了他们的完全b-染色数，并证明这些图都是完全b-连续的.
(3)提出了图的b-边染色数和b-边连续的概念，给出了路，圈，方形网格以及完全n叉树图的b-边染色数，并且证明路，圈以及完全n叉树图是b-边连续的.
(4)提出了图的完全b-边染色数以及完全b-边连续的概念，给出了路，圈以及完全n叉树图的完全b-边染色数，并且证明这些图都是完全b-边连续的.