On_lower_bound2.DVI


Mathematical Problems of Computer Science 23, 2004, 127{129.

On Lower B ound for W (K2 n)

R a fa e l R . K a m a lia n a n d P e t r o s A . P e t r o s ya n

Institute for Informatics and Automation Problems of NAS of RA

e-mails rrkamalian@yahoo.com, pet petros@yahoo.com

Abstract

The lower bound W (K2n) ¸ 3n ¡ 2 is proved for the greatest possible number of
colors in an interval edge coloring of the complete graph K2n.

Refer ences

[1 ] 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 .

[2 ] 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
, 2 5 -3 4 ,1 9 8 7 .

[3 ] S .V . S e va s t ia n o v, On in t e r va l c o lo u r a b ilit y o f e d g e s o f a b ip a r t it e g r a p h , M eth. Of D iscr.
Anal. In s o lu t io n o f e xt e r n a l p r o b le m s . Th e In s t it 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, N 5 0 , 6 1 -7 2 , 1 9 9 0 .

[4 ] S . Co o k, Th e c o m p le xit y o f t h e o r e m -p r o vin g p r o c e d u r e s . In P roc.3rd ACM Symp. o n
Th e o r y o f Co m p u t in g , 1 5 1 -1 5 8 , 1 9 7 1 .

[5 ] R .M. K a r p , R e d u c ib ilit y a m o n g Co m b in a t o r ia l P r o b le m s , in \ Co m p le xit y o f Co m p u t e r
Co m p u t a t io n s " ( R .E . Mille r a n d J.W . Th a t c h e r , E d s .) , p p . 8 5 -1 0 3 , N e w Y o r k, P le n u m ,
1 9 7 2 .

[6 ] 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 , N o vo s ib ir s k,
1 9 9 0 .

[7 ] K . Gia r o , M. K u b a le , M. Ma la ¯ e js ki, Co n s e c u t ive c o lo r in g s o f t h e e d g e s o f g e n e r a l
g r a p h s , D iscr. M ath. 2 3 6 , 1 3 1 -1 4 3 ,2 0 0 1 .

[8 ] A .A . Zyko v, Th e o r y o f ¯ n it e g r a p h s , N o vo s ib ir s k, N a u ka , 1 9 6 9 .

[9 ] A .S . A s r a t ia n , R .R . K a m a lia n , In ve s t ig a t io n o n in t e r va l e d g e c o lo r in g s o f g r a p h s , J .
Combin. Theory Ser. B 6 2 , 3 4 -4 3 ,1 9 9 4 .

[1 0 ] 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 , 2 9 -3 9 , 1 9 6 5 .

[1 1 ] I. H o lye r , Th e NP -c o m p le t e n e s s o f e d g e c o lo r in g , SIAM J . Comput. 1 0 , N 4 , 7 1 8 -7 2 0 ,
1 9 8 1 .

1 2 7



1 2 8 On Lower Bound for W (K2n)

êïáñÇÝ ·Ý³Ñ³ï³Ï³Ý W ( K2n ) -Ç Ñ³Ù³ñ

è. è. ø³Ù³ÉÛ³Ý, ä. ². ä»ïñáëÛ³Ý

²Ù÷á÷áõÙ

êï³óí³Í ¿ W ( K2n ) ¸ 3 n ¡ 2 ³Ýѳí³ë³ñáõÃÛáõÝÁ, áñÝ ³å³ÑáíáõÙ ¿ ëïáñÇÝ
·Ý³Ñ³ï³Ï³Ý K2n ÉñÇí ·ñ³ýÇ ÙÇç³Ï³Ûù³ÛÇÝ ÏáÕ³ÛÇÝ Ý»ñÏÙ³Ý Ù»ç û·ï³·áñÍíáÕ
·áõÛÝ»ñÇ ³é³í»É³·áõÛÝ Ñݳñ³íáñ ÃíÇ Ñ³Ù³ñ: