ABSTRACT

An edge-coloring of a graph G with colors is an interval t-coloring, if all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integer. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. The set of all interval colorable graphs is denoted by. For a graph, the least and the greatest values of t for which G has an interval t -coloring are denoted by and, respectively. In this paper, we show for any infinite bicyclic graph.

Keywords:Interval Edge-Coloring, Lower Bound, Infinite Bicyclic Graph

无穷双圈图的区间边着色的下界

陶艳亮

新疆大学数学与系统科学学院，新疆 乌鲁木齐

收稿日期：2017年5月6日；录用日期：2017年5月24日；发布日期：2017年5月27日

摘 要

图G的一个用了颜色的边着色称为区间t-着色，如果所有t种颜色都被用到，并且关联于G的同一个顶点的边上的颜色是各不相同的且这些颜色构成了一个连续的整数区间。图G称为是可区间着色的，如果对某个正整数t，G有一个区间t-着色。所有可区间着色的图构成的集合记作。对图，使得G有一个区间t-着色的t的最小值和最大值分别记作和。本文中，我们证明了对于无穷双圈图，有。

关键词 :区间着色，下界，无穷双圈图

Copyright © 2017 by author and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文中讨论的图都是有限的，无向的，没有自环和重边的图。和分别表示图的顶点集和边集，和分别表示顶点在图中的度和邻点集，表示图的最大度。

图的一个顶点称为悬挂点，如果它的度等于1，表示个顶点的圈。设是一个连通图，称为的圈数。当时，是双圈图。图的一个真边着色是图的一个边着色使得没有两条相邻边着相同的颜色。图的边色数是图的所有真边着色中所用颜色的最小数目。如果是图的一个真边着色，那么顶点的谱，记作，是与关联的边上的颜色构成的集合。我们用和分别表示的谱的最小颜色和最大颜色。

图的一个用了颜色的真边着色称为区间t-着色，如果所有t种颜色都被用到，并且对于任意的，与顶点关联的边所着颜色的色值构成一个连续整数区间，即是一个连续整数区间。图称为是可区间着色的，如果对某个正整数t，有一个区间t-着色。所有可区间着色的图构成的集合记作。对图，使得有一个区间t-着色的t的最小值和最大值分别记作和。显然，。

区间着色的概念是由Asratian和Kamalian在 [1] 中提出来的。在 [1] [2] 中，他们证明了如果，那么。对正则图来说，这个结论的逆也是成立的。此外，如果是一个正则图，那么，且对任意的，有一个区间t-着色。在 [3] 中，Kamalian进一步证明了如果是一个连通图，那么。这个上界被Giaro，Kubale和Malafiejski在 [4] 中改进了，他们证明了如果并且是一个至少有3个顶点的连通图，那么。对某些图类来说，的上界还得到了进一步的改进。其中包括可平面图 [5] 和至少有个顶点的r-正则图 [6] 。

图的亏度，记作，是指粘在上使得它可区间着色的悬挂边的最小数目。显然，当且仅当。在 [7] 中张维娟完全确定了单圈图和双圈图的亏度。参数和的确切数值对少数几类可区间着色的图来说已经完全确定了，其中包括偶圈，树 [8] 。本文中，我们完全确定了无穷双圈图的下界，并且证明了。

本文的框架如下。第二部分，给出了无穷双圈图的下界。第三部分，结论。第四部分，致谢。

2. 无穷双圈图的区间边着色的下界

图称作是无穷双圈无悬挂图，如果它恰有一个4度点其它顶点都是2度点，见图1所示。在无穷

图1. 无穷双圈无悬挂图

双圈无悬挂图的顶点上不断添加悬挂边得到的图称作无穷双圈有悬挂图。用符号表示所有无穷双圈无悬挂图的集合，用符号表示所有无穷双圈有悬挂图的集合。用表示所有无穷双圈图的集合，显然有。

引理2.1 [7] 如果图，则有

引理2.2。如果并且，则。

证明：设的两个圈为，，公共顶点为，即。由引理2.1知道是偶数。又因为，所以和有相同的奇偶性。

情况1。和都是奇数。

下面我们给出图的一个区间4-着色。我们给的边集：分别着色：，同时给的边集:分别着色：，就得到的一个区间4-着色。

情况2。和都是偶数。

下面我们给出图的一个区间4-着色。我们给的边集：分别着色：，同时给的边集:分别着色：，就得到的一个区间4-着色。

由以上讨论我们知道，总有区间4-着色，因此，。另一方面，。所以得到成立。

用符号表示图通过添加一条悬挂边得到的图。

引理2.3。如果并且，则并且。

证明：设的两个圈为，，公共顶点为，即。由，由引理2.1知道是奇数。又因为，所以和有不同的奇偶性。不失一般性，令为奇数,，为偶数。当添加一条悬挂边，是悬挂点。由亏度的定义，得到成立。

下面我们证明。

情况1。，此时，。我们给出图的一个区间5-着色。我们给的边集：分别着色：，同时给的边集：分别着色：，给边着颜色2，就得到的一个区间5-着色。

情况2。，此时，。我们给出图的一个区间4-着色。如果，我们给的边集：分别着色：，同时给的边集：分别着色：，给的边集：分别着色：，给边着颜色2，就得到的一个区间4-着色。如果，我们给的边集：分别着色：，同时给的边集：分别着色：，给的边集：如果，我们给的边集：分别着色：，同时给的边集：分别着色：，给的边集：分别着色：，给边着颜色2，就得到的一个区间4-着色。分别着色：，给边着颜色2，就得到的一个区间4-着色。

情况3。，此时，。我们给出图的一个区间4-着色。如果，我们给的边集:分别着色：，给的边集:分别着色：，同时给的边集:分别着色：，给边着颜色3，就得到的一个区间4-着色。如果，我们给的边集：分别着色：，给的边集分别着色：，同时给的边集：分别着色：，给边着颜色2，就得到的一个区间4-着色。

由以上讨论我们知道，总有区间-着色，因此，。另一方面，。我们得到：成立。

引理2.4。设，则。

证明：首先是由某个通过不断加悬挂边得到的图。其中的两个圈为，，公共顶点为。因此有悬挂边，其中为悬挂点。由引理2.2知道如果，则有区间-着色，由引理2.3知道如果，则并且也存在区间-着色。

以下我们利用归纳法给一个区间着色。设，分别讨论以下几种情形。

如果和都是奇数，

当时，令

此时，是一个区间5-着色。

当时，令

此时，是一个区间4-着色。

当时，令

此时，是一个区间4-着色。总之，是的一个区间-着色。

如果和都是偶数，用类似的方法也可以得到的一个区间-着色，不妨也记作。

如果和的奇偶性不同，则由引理2.3，图也存在区间-着色，不妨也记作。

现在假设无穷双圈图含有真子图，按归纳假设有区间着色，且它的区间边色数为。以下要利用构造的一个区间-着色。我们考虑以下情形：

如果的端点是的最大度点，即。此时，

于是可取如下：

此时，显然是的一个区间-着色。

如果的端点不是的最大度点，即。此时，则我们可取如下：

由于，是一个-连续着色，故也是。由以上讨论，。另一方面，总有。于是结论成立，证毕。

由引理2.2，2.3，2.4直接得到下面的结果。

3. 结论

设，

(i) 如果且为奇数，那么且。

(ii)否则且。

致谢

本文是在黄琼湘教授细心和认真的指导下完成的，在这里向黄老师表达深深的感谢和崇高的敬意。

文章引用

陶艳亮. 无穷双圈图的区间边着色的下界
The Lower Bounds of the Interval Edge-Colorings of Infinite Bicyclic Graphs[J]. 应用数学进展, 2017, 06(03): 382-387. http://dx.doi.org/10.12677/AAM.2017.63044

参考文献 (References)