临界图的若干性质和图的关联着色的研究论文.doc
上传者：小健
2022-07-08 22:50:15上传
DOC文件
355 KB
临界图的若干性质和图的关联着色的研究论文.doc临界图的若干性质和图的关联着色的研究
作者姓名： 闫立军
专业名称：运筹学与控制论
指导教师：王淑栋
入学时间：2004年9月
研究方向：图论与组合最优化
职 称：副教授
论文提交日期：2007年5月 论文答辩日期：2007年6月 授予学位日期：
STUDY ON SOME PROPERTIES OF CRICTICAL
GRAPHS AND INCIDENCE COLORING OF GRAPHS
A Dissertation submitted in fulfillment of the requirement of the degree of
MASTER OF SCIENCE
from
Shandong University of Science and Technology
by
Yan Lijun
Supervisor: Associate Professor Wang Shudong
College of Information Science and Engineering
May 2007
本人呈给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公 认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于 其它任何学术机关作鉴定。
硕士生签名:
日 期:
AFFIRMATION
I declare that this dissertation, submitted in fulfillment of the requirements for the award of Master of Science, in Shandong University of Science and Technology, is wholly my own work unless referenced of acknowledge. The document has not been submitted for qualification at any other academic institute.
Signature:
Date:
摘要
无环图G的一个边着色”是从边集E到颜色集C的一个映射m.EiC，使得G中任 何两条相邻的边均有不同的像。若|C卜k ,则称兀是G的一个k-边着色。使得G有k- 边着色的最小k值称为G的边色数，即：（G ） = min ｛k \ G存在一个k -边着色｝。著名的 Vizing定理表明：若G是简单图，则/（G ）＜ A + lo根据边着色的定义可知/（G ） ＞ A。 于是人们根据图的边色数将简单图分为两类，即若/（G）= A ,则称G是第一类图；若 r（G） = A+l ,则称G是第二类图。设G是连通第二类图，且对G的任何边e都有： 力（G-e）＜/（G）,则称G是临界图。本文根据临界图的定义和VAL定理讨论了 的临界图的若干性质，为冲击临界图猜想作了准备工作。
图G的一个顶点着色0是从顶点集V到颜色集C的一个映射，使得G中任 何两个相邻的顶点均无相同的像。若口以，则称0是G的一个-顶点着色。使得G有 -顶点着色的最小k值称为G的顶点色数，用力（G）表示。
设1（G） = ｛（le）veV,ee E且v与e相关联｝是G的关联集。称G的两个关联（v, e）
和（w,y）相邻当且仅当下列三种情况之一成立：（l）v = w;⑵e=y；⑶vw = e或vw =f □ 图G的一个关联着色b是从关联集1（G）到颜色集C的一个映射b：/（G）TC，使得 7（G）中任何两个相邻的关联都有不同的像。若b：/（G）TC是G的一个关联着色且
I I , ―
C = k ,则称G是k可关联着色的。使得G有k可关联着色的最小k值称为G的关联色 数，用力（G）表示。
本文根据关联着色和顶点着色的定义、性质给出了关联图的两个等价定义，并在此 基础上讨论了关联图的一些性质以及关联着色与顶点着色的若干关系；利用穷染法和换 色技巧确定了 Meredith's图的关联色数；从图的结构性质出发，利用双重归纳法和换色 技巧证明了
44的系列平行图都存在一个0 + 2, 2）-关联着色；根据（kJ）-关联着色的定 义和4 = 4 , mad（G ） < 3的图的结构性质，利用归纳法和换色技巧证明了 △ = 4 , mad（G）<3的图G存在一个（6, 2）-关联着色。
关键词：边着色，顶点着色，关联着色，系列平行图，Meredith's图
Abstract
作者姓名： 闫立军
专业名称：运筹学与控制论
指导教师：王淑栋
入学时间：2004年9月
研究方向：图论与组合最优化
职 称：副教授
论文提交日期：2007年5月 论文答辩日期：2007年6月 授予学位日期：
STUDY ON SOME PROPERTIES OF CRICTICAL
GRAPHS AND INCIDENCE COLORING OF GRAPHS
A Dissertation submitted in fulfillment of the requirement of the degree of
MASTER OF SCIENCE
from
Shandong University of Science and Technology
by
Yan Lijun
Supervisor: Associate Professor Wang Shudong
College of Information Science and Engineering
May 2007
本人呈给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公 认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于 其它任何学术机关作鉴定。
硕士生签名:
日 期:
AFFIRMATION
I declare that this dissertation, submitted in fulfillment of the requirements for the award of Master of Science, in Shandong University of Science and Technology, is wholly my own work unless referenced of acknowledge. The document has not been submitted for qualification at any other academic institute.
Signature:
Date:
摘要
无环图G的一个边着色”是从边集E到颜色集C的一个映射m.EiC，使得G中任 何两条相邻的边均有不同的像。若|C卜k ,则称兀是G的一个k-边着色。使得G有k- 边着色的最小k值称为G的边色数，即：（G ） = min ｛k \ G存在一个k -边着色｝。著名的 Vizing定理表明：若G是简单图，则/（G ）＜ A + lo根据边着色的定义可知/（G ） ＞ A。 于是人们根据图的边色数将简单图分为两类，即若/（G）= A ,则称G是第一类图；若 r（G） = A+l ,则称G是第二类图。设G是连通第二类图，且对G的任何边e都有： 力（G-e）＜/（G）,则称G是临界图。本文根据临界图的定义和VAL定理讨论了 的临界图的若干性质，为冲击临界图猜想作了准备工作。
图G的一个顶点着色0是从顶点集V到颜色集C的一个映射，使得G中任 何两个相邻的顶点均无相同的像。若口以，则称0是G的一个-顶点着色。使得G有 -顶点着色的最小k值称为G的顶点色数，用力（G）表示。
设1（G） = ｛（le）veV,ee E且v与e相关联｝是G的关联集。称G的两个关联（v, e）
和（w,y）相邻当且仅当下列三种情况之一成立：（l）v = w;⑵e=y；⑶vw = e或vw =f □ 图G的一个关联着色b是从关联集1（G）到颜色集C的一个映射b：/（G）TC，使得 7（G）中任何两个相邻的关联都有不同的像。若b：/（G）TC是G的一个关联着色且
I I , ―
C = k ,则称G是k可关联着色的。使得G有k可关联着色的最小k值称为G的关联色 数，用力（G）表示。
本文根据关联着色和顶点着色的定义、性质给出了关联图的两个等价定义，并在此 基础上讨论了关联图的一些性质以及关联着色与顶点着色的若干关系；利用穷染法和换 色技巧确定了 Meredith's图的关联色数；从图的结构性质出发，利用双重归纳法和换色 技巧证明了
44的系列平行图都存在一个0 + 2, 2）-关联着色；根据（kJ）-关联着色的定 义和4 = 4 , mad（G ） < 3的图的结构性质，利用归纳法和换色技巧证明了 △ = 4 , mad（G）<3的图G存在一个（6, 2）-关联着色。
关键词：边着色，顶点着色，关联着色，系列平行图，Meredith's图
Abstract
临界图的若干性质和图的关联着色的研究论文
