D:\sbornik\...\statya.DVI


Mathematical Problems of Computer Science 25, 2006, 5{8.

I nter val E dge Colour ings of Complete Gr aphs and

n-cubes

P e t r o s A . P e t r o s ya n

Institue for Informatics and Automation Problems (IIAP) of NAS of RA

e-mail pet petros@yahoo.com

Abstract

For complete graphs and n-cubes bounds are found for the possible number of
colours in an interval edge colourings.

Refer ences

[1 ] F. H a r a r y, " Gr a p h Th e o r y" , Addison-W esley, R eading, MA ,1 9 6 9 .

[2 ] A . A . Zyko v, " Th e o r y o f ¯ n it e g r a p h s " , Novosibirsk, Nauka, 1 9 6 9 .

[3 ] 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 u 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, Y e r e va n S t a t e U n ive r s it y, p p . 2 5 -3 4 1 9 8 7 .

[4 ] R .R . K a m a lia n , " In t e r va l E d g e Co lo u r in g s o f Gr a p h s " , D octoral dissertation, The In-
stitute of M athematics of the Siberian B ranch of the Academy of Sciences of USSR ,
N o vo s ib ir s k, 1 9 9 0 .

[5 ] 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 r e m 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 , p p . 6 1 -7 2 ,
1 9 9 0 .

[6 ] 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 , p p . 1 5 1 -1 5 8 , 1 9 7 1 .

[7 ] 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 Complexity of Com-
puter Computations ( 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 .

[8 ] 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 u r in g s o f g r a p h s " ,
J . Combin. Theory Ser. B 6 2 p p . 3 4 -4 3 , 1 9 9 4 .

[9 ] 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 u 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 , p p . 1 3 1 -1 4 3 , 2 0 0 1 .

5



6 Interval Edge Colourings of Complete Graphs and n-cubes

[1 0 ] 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 u r in g " , SIAM J . Comput. 1 0 , N 4 , p p .
7 1 8 -7 2 0 , 1 9 8 1 .

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

[1 2 ] R .R . K a m a lia n , P .A . P e t r o s ya n , " On lo we r b o u n d fo r W ( K2n ) " , M athematical P rob-
lems of Computer Science, V o l. 2 3 , p p .1 2 7 -1 2 9 , Y e r e va n , 2 0 0 4 .

ÈñÇí ·ñ³ýÝ»ñÇ ¨ n-ã³÷³ÝÇ Ëáñ³Ý³ñ¹Ý»ñÇ
ÙÇç³Ï³Ûù³ÛÇÝ ÏáÕ³ÛÇÝ Ý»ñÏáõÙÝ»ñ

ä. ä»ïñáëÛ³Ý

²Ù÷á÷áõÙ

ÈñÇí ·ñ³ýÝ»ñÇ ¨ n-ã³÷³ÝÇ Ëáñ³Ý³ñ¹Ý»ñÇ Ñ³Ù³ñ ëï³óí³Í »Ý ·Ý³Ñ³ï³Ï³ÝÝ»ñ
ÙÇç³Ï³Ûù³ÛÇÝ ÏáÕ³ÛÇÝ Ý»ñÏÙ³Ý Ù»ç û·ï³·áñÍíáÕ ·áõÛÝ»ñÇ Ñݳñ³íáñ ÃíÇ Ñ³Ù³ñ: