论文部分内容阅读
本文讨论的图均为有限无向的简单图。图的染色问题的研究一直是图论界的热点,图的连续边染色问题也是图染色问题的热点话题之一,它具有重要的实际意义和理论意义,它在组合分析和日程安排理论上有着非常广泛的应用。连续边染色问题首先是由Asratian和Kamalian在1987年提出的:对于简单图G用颜色1,2,3,…对其边正常染色,如果与每一个顶点关联的边的颜色构成一个连续的整数集合,那么就称这个边染色是连续的或连续边染色。在本文中,所研究的是连续边染色的一种推广(t,1)-连续边染色。 第一章中主要介绍了一些基本概念,相关符号以及图的(t,1)-连续边染色的概念。 设图G(V,E)是简单无向图,α是集合E(G)到集合[t]={1,2,…,t)的一个映射。若α满足以下条件: (1)α是图G的边可染映射; (2)对于每一种颜色i∈[t],至少存在一边e∈E使α(e)=i; (3)图G的任一顶点,满足 dG(v)-1≤max Sα(V)-min Sα(v)≤dG(v),其中Sα(v)={α(uv):u∈N(v),u∈V(G)}。则称图G是(t,1)-连续边可染的,α是图G的(t,1)-连续边可染映射。称wi(G)=min{t:G是(t,1)-连续边可染的},W1(G)=max{t:G是(t,1)-连续边可染的}分别为图G的最小(t,1)-连续边染色数和最大(t,1)一连续边染色数。 第二章介绍了笛卡尔积图G1×G2和直积图G1×G2的一些基本性质和(t,1)-连续边染色,给出了本文的主要定理及证明。第三章重点讨论直积图的最小(t,1)-连续边染色数W1和最大(t,1)-连续边染色数W1,并给出了相应的结论。在第四章中给出了可以进一步探讨的一些问题。