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

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).