图的剖分的强边色数研究

发布时间：2020-12-02 14:44

　　图G =（V,E）的强边着色是将多种颜色分配给图G的边集,使得着每一种颜色的边的集合是图G的一个导出匹配;图G的强边色数指的是在图G的所有强边着色中需要的颜色最少的强边着色的颜色数,记为x’s（G）.对图G中的一条边e进行剖分指的是删除边e,添加一个新的顶点x并且将x和e的两个端点连接.图G的k次剖分图,用G（k）表示,指的是将图G的每一条边都恰好进行k次剖分得到的图.设Pm和Pu分别为包含m和n个顶点的路.平面（m,n）-格子图定义为Pm和Pn的乘积图Pm□Pn.我们用Kn表示n个顶点的完全图.本文研究平面格子图Pm□Pn的k次剖分图的强边色数以及完全图Kn的k次剖分图的强边色数.论文的主要结果如下:（1）对于平面格子图G= Pm□Pn,当m = 1或者n = 1时,xs’（G）= e（G）若e（G）<3,x’s（G）= 3 若 e（G）≥ 3;当 m = 2,n = 2 时,x’s（G）= 4;当 m = 2,n ≥ 3 或者m ≥ 3,n = 2 时,x’s（G）= 6;当 m>3,n ≥ 3 时,x’s（G）= 8.（2）令G（kk）是平面格子图G = Pm□Pn的... 

【文章来源】：郑州大学河南省 211工程院校

【文章页数】：56 页

【学位级别】：硕士

【部分图文】：

图４平面格子图Ｇ＝Ｐ３ＱＰ３??

图５平面格子图Ｇ?＝?Ｐ３ＯＰ３的一个强边着色??

图７平面格子图Ｇ?＝巧口巧的１次剖分图Ｇ⑴??


本文编号：2895475