D:\sbornik\...\article.DVI


Mathematical Problems of Computer Science 29, 2007, 26{32.

On a Gener alization of I nter val E dge

Color ings of Gr aphs

P . A . P e t r o s ya n y a n d H . Z. A r a ke lya n z

yInstitue for Informatics and Automation Problems of NAS of RA
e-mail: pet petros@ipia.sci.am

zDepartment of Informatics and Applied Mathematics, YSU
e-mail: arak hakob@yahoo.com

Abstract

An interval edge (t; h)¡coloring (h 2 Z+) of a graph G is a proper coloring ® of
edges of G with colors 1; 2; : : : ; t such that at least one edge of G is colored by i;
i = 1; 2; : : : ; t and the colors of edges incident with each vertex v satisfy the condition

dG(v) ¡ 1 · max S (v; ®) ¡ min S (v; ®) · dG(v) + h ¡ 1;

where dG(v) is the degree of a vertex v and S (v; ®) is the set of colors of
edges incident with v. In this paper we investigate some properties of interval edge
(t; h)¡colorings.

Refer ences

[1 ] A .S . A s r a t ia n , R .R . K a m a lia n , In t e r va l c o lo r in g s o f e d g e s o f a m u lt ig r a p h , Appl. M ath.
5 ( 1 9 8 7 ) , Y e r e va n S t a t e U n ive r s it y, p p . 2 5 -3 4 .

[2 ] R .R . K a m a lia n , In t e r va l E d g e Co lo r in g s o f Gr a p h s , D o c t o r a l d is s e r t a t io n , Th e In s t i-
t u t e o f Ma t h e m a t ic s o f t h e S ib e r ia n B r a n c h o f t h e A c a d e m y o f S c ie n c e s o f U S S R ,
N o vo s ib ir s k, 1 9 9 0 .

[3 ] F. H a r a r y, Gr a p h Th e o r y, A d d is o n -W e s le y, R e a d in g , MA ,1 9 6 9 .

[4 ] V .G. V iz in g , Th e c h r o m a t ic in d e x o f a m u lt ig r a p h , K ibernetika 3 ( 1 9 6 5 ) , p p . 2 9 -3 9 .

[5 ] D .B . W e s t , In t r o d u c t io n t o Gr a p h Th e o r y, P r e n t ic e -H a ll, N e w Je r s e y, 2 0 0 1 .

[6 ] R .R . K a m a lia n , In t e r va l c o lo r in g s o f c o m p le t e b ip a r t it e g r a p h s a n d t r e e s , P r e p r in t o f
t h e Co m p u t in g Ce n t r e o f t h e A c a d e m y o f S c ie n c e s o f A r m e n ia , 1 9 8 9 , 1 1 p .

2 6



P. A. Petrosyan, H. Z. Arakelyan 2 7

¶ñ³ýÝ»ñÇ ÙÇç³Ï³Ûù³ÛÇÝ ÏáÕ³ÛÇÝ Ý»ñÏáõÙÝ»ñÇ ÁݹѳÝñ³óÙ³Ý Ù³ëÇÝ

ä. ². ä»ïñáëÛ³Ý ¨ Ð. ¼. ²é³ù»ÉÛ³Ý

²Ù÷á÷áõÙ

G ·ñ³ýÇ ÏáÕ»ñÇ ×Çßï ® Ý»ñÏáõÙÁ 1 ; 2 ; :::; t ·áõÛÝ»ñáí ϳÝí³Ý»Ýù ÙÇç³Ï³Ûù³ÛÇÝ
ÏáÕ³ÛÇÝ ( t; h) -Ý»ñÏáõÙ (h 2 Z+), »Ã» ³Ù»Ý ÙÇ i ·áõÛÝáí, i = 1 ; 2 ; :::; t Ý»ñÏí³Í ¿
³éÝí³½Ý Ù»Ï ÏáÕ ¨ Ûáõñ³ù³ÝãÛáõñ ·³·³ÃÇÝ ÏÇó ÏáÕ»ñÇ ·áõÛÝ»ñÁ µ³í³ñ³ñáõÙ »Ý
Ñ»ï¨Û³É å³ÛÙ³ÝÇÝ‘ dG ( v ) ¡ 1 · m a x S ( v; ®) ¡ m in S ( v; ®) · dG ( v ) + h¡ 1 , áñï»Õ dG ( v ) -Ý
v ·³·³ÃÇ ³ëïÇ׳ÝÝ ¿ G-áõÙ, ÇëÏ S ( v; ® ) v ·³·³ÃÇÝ ÏÇó ÏáÕ»ñÇ ·áõÛÝ»ñÇ µ³½ÙáõÃÛáõÝÝ
¿: ²Ûë ³ß˳ï³Ýùáõ٠ѻﳽáïíáõÙ »Ý ÙÇç³Ï³Ûù³ÛÇÝ ÏáÕ³ÛÇÝ ( t; h) Ý»ñÏáõÙÝ»ñÇ áñáß
ѳïÏáõÃÛáõÝÝ»ñ: