最大外平面图和最大平面图的性质  

Properties of Maximal Outerplanar Graph and Maximal Planar Graph

作　　者：冯纪先[1] 

机构地区：[1]武汉大学电子信息学院,湖北武汉430072

出　　处：《高等数学研究》2013年第4期9-12,共4页Studies in College Mathematics

摘　　要：对最大外平面图的区数、边数、度数和色数等性质进行了研讨.利用步进法,证明了最大外平面图的色数为3,且是唯一3可着色的结论.利用最大外平面图的性质,对最大平面图的区数、边数、度数和色数等性质进行了讨论,并证明了色数为3的那种最大平面图,是唯一3可着色的结论.In this paper, properties, such as point, edge, region, degree, chromatic number, uniqueness, etc., of a maximal outerplanar graph are discussed. The statements that the chromatic number of a maximal outerplanar graph is 3, and it is uniquely 3-colorable are proved using the step-by-step method. Similar properties for a maximal planar graph are studied using properties of maximal outerplanar graph. The statement that if the chromatic number of a maximal planar graph is 3, it is uniquely 3-colorable is proved.

关 键 词：最大外平面图 最大平面图 图着色 唯一k可着色 

分 类 号：O157.5[理学—数学]