﻿ 广义θ-链的区间边着色的上界 The Upper Bound of the Interval Edge-Coloring of the Generalized θ-Chain

Advances in Applied Mathematics
Vol.07 No.04(2018), Article ID:24704,5 pages
10.12677/AAM.2018.74052

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

Xun Chen

College of Mathematics and System Science, Xinjiang University, Urumqi Xinjiang

Received: Apr. 11th, 2018; accepted: Apr. 21st, 2018; published: Apr. 28th, 2018

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 any, G has a interval t-coloring. w(G) and W(G) are the minimum and maximum numbers of t. A generalized θ-chain, denoted by, is a simple graph obtained by substituting pairwise internally disjoint -paths for each edge of the path, where. In this paper, we give a tight upper bound on.

Keywords:Interval Edge-Coloring, Upper Bound, Generalized θ-Graph, Generalized θ-Chain

Copyright © 2018 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. 引言

2.的一个上界

,

, (1)

, (2)

(3)

,

.

Case 1.

(4)

,.

. (5)

Case 2..

. (6)

The Upper Bound of the Interval Edge-Coloring of the Generalized θ-Chain[J]. 应用数学进展, 2018, 07(04): 418-422. https://doi.org/10.12677/AAM.2018.74052

1. 1. Asratian, A.S. and Kamalian, R.R. (1987) Interval Colorings of Edges of a Multigraph. Appl. Math., 5, 25-34. (In Russian)

2. 2. Asratian, A.S. and Kamalian, R.R. (1994) Investigation on Interval Edge-Colorings of Graphs. Journal of Combinatorial Theory, Series B, 62, 34-43. https://doi.org/10.1006/jctb.1994.1053

3. 3. Kamalian, R.R. (1990) Interval Edge Colorings of Graphs. Doctoral Thesis, Novosibirsk.

4. 4. Giaro, K., Kubale, M. and MaLafiejski, M. (2001) Consecutive Colorings of the Edges of General Graphs. Discrete Mathematics, 239, 131-143. https://doi.org/10.1016/S0012-365X(00)00437-4

5. 5. Axenovich, M.A. (2002) On Interval Colorings of Planar Graphs. Congressus Numerantium, 159, 77-94.