标定的最大外平面图G_(MO)的数目

介绍了n≥3,n阶标定的具有不同拓扑结构的最大外平面图GMO可能有的数目,论证并给出了它们的递推公式及2种直接表达式,并使用这些公式验算了低阶的GMO的数目。

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

对最大外平面图的区数、边数、度数和色数等性质进行了研讨.利用步进法,证明了最大外平面图的色数为3,且是唯一3可着色的结论.利用最大外平面图的性质,对最大平面图的区数、边数、度数和色数等性质进行了讨论,并证明了色数为3的那种最大平面图,是唯一3可着色的结论.

最大外可平面图的树图

通过对最大外可平面图和 K临界图的研究给出三个主要结论( 1 )最大外可平面图的生成树有 2 p- 3* 3棵。( 2 )最大外可平面图的树图GT,Δ( GT)≥ p+ 1。( 3)临界图 G,当 K( G) =1时 ,树图 GT 是平凡图 ,当K( G) =2时 ;树图 GT是

The Complete Chromatic Number of Maximal Outerplane Graphs

Let G be a maximal outerplane graph and X0(G) the complete chromatic number of G. This paper determines exactly X0(G) for △(G)≠5 and proves 6≤X0.(G)≤7 for △(G) = 5, where △(G) is the maximum degree of vertices of G.

图的色多项式问题

定义1 设图G为含有P个顶点的标定图,对其进行X—正常染色的方法数是X的一个函数,可表示成X的一个多项式,称为图G的色多项式,记为f(G,X)。 引理1 给定图G,设u、v∈V(G),e=(u,v)∈E(G)