【作者】 席美丽；

【导师】 王德强；

【作者基本信息】 大连海事大学 ， 应用数学， 2008， 硕士

【摘要】 具有重要的理论意义和实际意义的各种染色问题,一直是图论中的热点话题之一。离散系统中的许多问题都可以转化为图着色问题,例如,给定图G,不包含子图的G的n个顶点的图的边的最大数目就依赖于图G的色数。因此Jensen和Toft断言:图着色理论在离散数学中处于中心的地位。在现实生活中许多领域都会涉及到将某种对象的集合按照一定的规则进行分类的问题,例如时间表问题、排序问题、排课表问题、存储问题、电路安排、任务分配等等,都与图着色理论密切相关。所谓图着色是指对图中的顶点、边(对平面图而言还有面)等元素按照一定的规则进行分类。对象不同或规则不同,便有各式各样的着色。随着染色理论的发展又出现了许多新的染色,例如:全着色、列表着色、点强全着色、强边着色、强着色、关联着色、圈着色、距离面着色、区间着色、r-强边着色、完备着色及动态着色等,这些染色已成为现在图着色领域中新的热点.对于过去很多未解决的问题我们可以把它转化为一个新的染色问题,使原问题变得简单易懂并且便于研究。本文主要研究的是图的邻强边染色与2-强边染色问题。首先借助于Akbari对树2-强边染色及3-强边染色的研究与张忠辅对树邻强边染色的研究,给出了对树进行2-强边染色时,2-强边色数等于最大度加1的充分条件是具有最大度的两个顶点的距离小于等于2。然后根据圈、完全图、完全二部图、轮图、项链、P_n~2、P_n~3、P_n~4、P_n~5、单圈图、若干联图、方形网格与六角网络的结构特点及其具有最大度的顶点之间的关系,研究了它们的2-强边染色问题,确定了它们的2-强边色数与最大度的关系,并且给出了它们的2-强边染色方案。更多还原

【Abstract】 The coloring problems is one of popular problems in graph theory because of it’s profound significance in both theory and practice.Many issues in discrete systems can be translated into the problems of graph coloring.For example,the edge maximum of n-order graph which don’t contain a certain graph G as a subgraph depends on the chromatic number of the graph.Therefore T R.Jensen and B.Toft asserted:the graph coloring theory in discrete mathematics at the center position.In real life,many areas will be dealt with the object of a certain set of rules according to certain classification of the problem.For example,schedule,scheduling,time-table problem,the problem of storing,circuit arrangement,task allocation,and so on.These problems are closely related to coloring theory.The so-called graph coloring is refers speaking of the graph in the vertex,edge(to the plane graph also has face) and so on the element carries on the classification according to the certain rule.Object dissimilarity or rule dissimilarity,then has all kinds of colotings.With the development of coloring theory,there are many new coloring, such as total coloring,list coloring,strong edge coloring,strong coloring,choosable coloring,r-strong edge color and so on hundred and thousand of colouring ways.These has bscome new hot spots in the graph colouring.As to the unresolved questions in the past,we can put them into a new coloring problem such that it is easy to understand and convenient to study.In this paper,we discuss the adjacent strong edge coloring and 2-strong edge coloring of some graphs.First,with the research of 2-strong edge coloring and 3-strong edge coloring of tree from Akbari and adjacent strong edge coloring of tree from Zhang Zhongfu,a sufficient condition is proposed that 2-strong edge coloring number equals to the maximum degree plus one.Then according to the struct of cycle,complete graph, complete bipartite graph,wheel,nacklace,P_n~2,P_n~3,P_n~4,P_n~5,monocycle graph,some join-graphs,square mesh,hexagonal mesh and the relationship between the vertexes with the maximum degree,the 2-strong edge coloring of these graphs is studied to obtain the relationship of 2-strong edge coloring number and the maximum degree. Besides,the coloring method on the 2-strong edge coloring of these graphs are given.更多还原