文档介绍：论文题目(汉文) 图的关联图的边染色
论文题目(外文)The Proper Edge Coloring on Some classes of Incidence Graphs
图的关联图的边染色
中文摘要
张忠辅等人在2000年提出了图的关联图的概念,研究了图的关联图的性质和一些特殊图的关联图的正常边染色. 并在此基础上提出了图的关联图的边染色猜想:每个简单图的关联图都是第一类图,即简单图的关联图的边色数等于的最大度.
图的关联图是一种特殊的运算图, 具有较为复杂的结构,确定其边色数是比较困难的. 本文在研究关联图结构的基础上, 将所研究图的关联图分解成两个边不交的生成子图, 然后利用数学归纳法或构造染色的方法确定关联图的边色数. 证明了正则二部图、完全二部图、特殊的树、图、一类广义图和几类冠图的关联图都是第一类图,验证了这些图的关联图满足图的关联图的边染色猜想. 主要结果如下:
(1)设为正则二部图或完全二部图,则.
(2)设是具有最大度的树,为的一个最大度点. 若,则树的关联图是第一类图. 其中, .
(3)具有相邻最大度顶点的树的关联图和最大度小于等于4的树的关联图均是第一类图.
(4) 设图是图, 则; 设图是广义图, 若的两个度点不相邻, 则.
(5)设是具有最大度的树的冠图,若具有相邻最大度顶点,则.
(6)设为圈的冠图,若或,则
.
关键词:关联图,正常边染色,二部图,树,图,冠图
The Proper Edge Coloring on Some Classes of Incidence Graphs
Abstract
Zhang Zhong-Fu puts forward the concepts of incidence graph about a given graph in 2000 and studied both the related properties of incidence graph and the proper edge coloring of incidence graphs for some special graphs in references [34].Based on those a conjecture about the proper edge coloring of incidence es: For any simple connected graph , the incidence graph of a given graph is of Class 1.
The incidence graph of a given graph , as a kind of operator graphs, has plex structure than the given graph . The edge chromatic number of incidence graphs is difficult to determine. Based on the research on the basis of the structure of incidence graphs, the study of incidence graphs is posed into two spanning subgraph who are edge-disjiont . Then we use mathematical induction or the method of constructing the proper edge coloring to determine the edge chromatic number of incidence graphs. We proved that the incidence graphs of regular bipartite plete bipartite graphs、special trees、graphs、a kind of generalized graphs and several kinds of corona graphs are of class 1, and verified that the incidence graphs of those graphs meet the conjecture of incidence graphs about edge chromatic number. In this dissertation, the following result can be obtained:
(1) let be a regular bipartite plete bip