摘要
给出了临界极大外平面图以及最大度临界极大外平面图的定义 ,并讨论了它们的性质 ,为研究极大外平面图的四染色提供了一种新方法 .
The criticality play an important role in the theory of graph coloring.The definitions of critical maximal outerplanar graph and maximum degree critical maximal outerplanar graph are presented.The properties of these kinds of graphs are discussed.It is shown that if G and G′ are critical maximal outerplanar graphs with a common boundary circuit Q r ,then d G (v i;) + d G′ (v i) ≥7 for every vertex v i∈V(Q r ).Furthermore it is also proved that if G and G′ are maximal degree critical graphs with a common boundary circuit Q r and G has a critical degree.Let v i and v′ j are two vertex sets adjacent to v i in G ,where i≠j .Then v p v q can not be a chord of G′ for any v p∈v i′ and v q∈v′ j with {p,q}±{z,r} .The concepts and the results given here present a novel method for studying the four coloring of maximal outerplaner graph.
出处
《东北师大学报（自然科学版）》
CAS
CSCD
北大核心
2002年第2期16-21,共6页
Journal of Northeast Normal University(Natural Science Edition)
关键词
临界圈
临界极大外平面图
最大度临界极大外平面图
临界度
critical cycle
critical maximal outerplanar graph
maximum degree critical maximal outerplanar graph
critical degree
