论文部分内容阅读
1980年,Lowell Beineke和Richard Ringeisen[1] 提出了共色指标的概念。对图G的边集进行划分,使划分所得的每个子集是边独立集,星或三角形,则称这种边分划为G的一个边共染色,而这种分划中所含的最小子集数称图G的共色指标,用z(G)表示。2006年,刘信生等[7] 又提出了边共色数的概念。图G的边共色数,用z(G)表示,是指图G的一种边分划中所含的最小子集数,这种边分划中的每个子集是边独立集或星。易见边共色数就是无三角形时的共色指标。本文以z(G)的界:Φ(G)≤ z(G)≤Φ(G)+1 为基础,主要研究无三角形时的共色指标,即边共色数的问题,文章分为四节:
1.介绍了与边共染色相关的概念和引理。
2.讨论了边共着色中的分类问题。依据边共色数将简单图分为两类,并给出了两类图的一些简单的判定准则及相应图例。
3.研究了几种特殊图联图的边共染色,得到了联图Sm∨Sn,Sm∨Wn,Sm∨Pn及Sm ∨ Cn的边共色数公式。
4.研究了唯一边共着色图。给出了唯一的n-边共着色图的定义及几条简单性质,并构造了三种不同类型的唯一n-边共着色图.