广义θ-链的区间边着色的上界

The Upper Bound of the Interval Edge-Coloring of the Generalized θ-Chain

摘要: 图G的一个用了颜色 1,2,…,t的边着色称为区间t-着色，如果所有t种颜色都被用到，并且关联于G的同一个顶点的边上颜色各不相同且这些颜色构成了一个连续的整数区间。G称作是可区间着色的，如果对某个正整数t，G有一个区间t-着色。所有可区间着色的图构成的集合记作ℵ。对图G∈ℵ，使得G有一个区间t-着色的t的最小值和最大值分别记作w(G)和W(G)。广义θ-链，记作θ_m1,_m2,…,_mk,是把路P=[v₀,v₁,…,v_k](k≥1)的每一条边v_i-1v_i用m_i≥2条两两内部不交的(v_i-1,v_i)-路替换掉而得到的简单图，这里i=1,2,…,k。在本文中，我们给出了W(θ_m1,_m2,…,_mk)的一个紧的上界。

Abstract: An edge-coloring of a graph G with colors 1,2,…,t 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 any G∈ℵ G has a interval t-coloring. w(G) and W(G) are the minimum and maximum numbers of t. A generalized θ-chain, denoted by θ_m1,_m2,…,_mkis a simple graph obtained by substituting m_i≥2 pairwise internally disjoint (v_i-1,v_i)-paths for each edge v_i-1v_i of the path P=[v₀,v₁,…,v_k](k≥1), where i=1,2,…,k. In this paper, we give a tight upper bound on W(θ_m1,_m2,…,_mk).

1. 引言

和分别表示图G的顶点集和边集，表示顶点在图G中的度，表示图G的最大度，表示图G的边色数，表示n个顶点的路。

如果α是图G的一个正常边着色，那么与关联的边上的颜色构成的集合，记作。我们用和分别表示的最小色值和最大色值。

图G的一个用了颜色的正常边着色α称为区间t-着色，如果所有t种颜色都被用到，并且对任意的，是连续的。图G称为是可区间着色的，如果对某个正整数t，G有一个区间t-着色。所有可区间着色的图构成的集合记作。对图，使得G有一个区间t-着色的t的最小值和最大值分别记作w(G)和W(G)。

区间边着色的概念是由Asratian和Kamalian在 [1] [2] 中提出来的，并且证明了如果，那么。在 [3] 中，Kamalian证明了如果是一个连通图，那么。这个上界被Giaro等在 [4] 中改进了，他们证明了如果是一个至少有3个顶点的连通图，那么。对某些图类来说，的上界还得到了进一步的改进，其中包括不含三角形的图 [1] [2] 和可平面图 [5] 。

广义θ-图是由条两两内部不交的-路构成的简单图，记作。广义θ-链是把路的每一条边()用条两两内部不交的-路替换掉得到的简单图，记作。在本文中，我们给出了的一个紧的上界。

2.的一个上界

令，是中两两内部不交的-路。对每一个，令

,

为了方便，我们记为中第i大的数，为中第i大的数。

引理2.1：设α是可区间着色图G的一个区间t-着色，是G中的一条路，其中且。那么，等号成立当且仅当

，。

证明：因为且，我们有

, (1)

等号成立当且仅当。因为且，我们有

, (2)

等号成立当且仅当。因为，，我们有

， (3)

等号成立当且仅当且。

由(1)-(3)，我们可以得到

,

等号成立当且仅当，。

证毕。

定理2.3：若广义θ-链可区间边着色的，那么

.

证明：设α是的一个区间-着色。那么存在两条边使得且。我们分以下两种情况讨论。

Case 1.，。

首先，我们假设，。令，，，这里且。那么，。由引理2.1，我们有

。 (4)

因为且，由(4)我们有，因此结论成立。

其次,我们假设且，这里。设，，，，这里，，，。我们考虑以下两条路:

,.

显然，，因此。我们能断言或者，否则，矛盾。不失一般性，设，那么。注意到且。由引理2.1，我们有

. (5)

因为，且对任意有，由(5)，我们有，因此结论成立。

Case 2.，，.

不失一般性，设，且，且，这里且。设，，，，这里，，，，，。那么

是中的一条路满足且。由引理2.1，可得

. (6)

令

显然，，表明。因为，且对任意有，，由(6)，我们有

因此结论成立。

证毕。