学位论文 > 优秀研究生学位论文题录展示

仙人掌的连续边着色

作　者: 张维娟
导　师: 黄琼湘
学　校: 新疆大学
专　业: 应用数学
关键词: 仙人掌连续边着色图的亏度
分类号: O157.5
类　型: 硕士论文
年　份: 2006年
下　载: 16次
引　用: 0次
阅　读: 论文下载

内容摘要

设G是简单图,用颜色1,2,3,···对G的边正常着色,如果在每一顶点表现的颜色构成一个连续的整数集合,那么就称这个着色是连续的[2].图的连续边着色对应于没有等待时间的日程安排问题.不是所有的图都有连续边着色.图G的亏度def(G)是粘在G上使得它可连续着色的悬挂边的最小数目[9].通常要确定一个图是否有连续边着色是比较困难的,而且已刻划的图只有很少的一部分.事实上, Sevastjanov在[3]中已经证明了即使是对一个给定的二部图,要确定它是否有连续边着色也是NP完全的.仙人掌是一个每个块是圈或K2的图.从定义可知一个仙人掌的任意两个不同的圈至多有一个公共点.用o(G)表示图G中包含的奇圈个数, Fn?表示由n个只有一个公共顶点的三角形构成的图.如果一个图G有导出子图G1和G2使得G = G1∪G2并且G1∩G2 = K1,则称G是G1和G2在顶点v的粘,记作G = G1∨v G2,其中v∈V (G1∩G2).在本文中,我们研究仙人掌的连续边着色问题.我们确定了奇圈数不超过2的仙人掌的亏度,给出了一个无割边且奇圈数是偶数的仙人掌可连续着色的充分条件,并且证明了无割边且奇圈数是奇数的仙人掌是不能连续着色的.此外,我们还给出了两类亏度为1的仙人掌.下面是本文的主要结论:1.设G是一个仙人掌,并且o(G) 2.如果G无割边且o(G) = 1,则def(G) = 1;否则, def(G) = 0.2.设G是一个无割边的仙人掌,并且o(G)是偶数.如果对G中的任意一个奇圈C,至少有一个点v∈V (C)使得dG(v) = 2,则def(G) = 0.3.设G是一个无割边的仙人掌,并且o(G)是奇数,则G不能连续着色.并且,如果对G中的任意一个奇圈C,至少有一个点v∈V (C)使得dG(v) = 2,则def(G) = 1.4.设G = C2k+1∨v1 H1∨v2 H2∨v3···∨v2k+1 H2k+1,这里C2k+1 = v1v2 ...v2k+1是一个奇圈, H1,...,H2k+1是无割边的仙人掌.如果o(Hi) = 1且dHi(vi) = 2,或者Hi = F2?mi+1,这里mi 1,则def(G) = 1.

全文目录

1. Introduction  6-9
2. Some preliminaries  9-11
3. Consecutive edge-colorings of cacti  11-25
4. References  25-26
5. List of published papers  26-27
6. Acknowledgement  27-28
学位论文独创性声明  28
学位论文知识产权权属声明  28

仙人掌的连续边着色

内容摘要

全文目录

相似论文