article1_in_English.DVI Mathematical Problems of Computer Science 25, 2006, 53{56. I nter val Colour ings of Some Regular Gr aphs R a fa ye l R . K a m a lia n , P e t r o s A . P e t r o s ya n Institue for Informatics and Automation Problems of NAS of RA e-mails rrkamalian@yahoo.com, pet petros@yahoo.com Abstract A lower bound is obtained for the greatest possible number of colors in an interval colourings of some regular graphs. R eferences [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 ] 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 . [3 ] 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 . [4 ] 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 ( 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 . [5 ] R .R . K a m a lia n , \ In t e r va l E d g e c o lo u 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 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 i- b ir s k, 1 9 9 0 . [6 ] S .V . S e va s t ia n o v, On in t e r va l c o lo 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 ethods 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 ( 1 9 9 0 ) , p p . 6 1 -7 2 . [7 ] 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 ( 1 9 8 1 ) , p p . 7 1 8 -7 2 0 . [8 ] 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 9 7 1 , p p . 1 5 1 -1 5 8 . [9 ] 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 .) , N e w Y o r k, 1 9 7 2 , p p . 8 5 -1 0 3 . [1 0 ] E . T. P a r ke r , E d g e -c o lo u r in g n u m b e r s o f s o m e r e g u la r g r a p h s , P roc. Amer. M ath. Soc. 3 7 , ( 1 9 7 3 ) , p p . 4 2 3 -4 2 4 . àñáß Ñ³Ù³ë»é ·ñ³ýÝ»ñÇ ÙÇç³Ï³Ûù³ÛÇÝ Ý»ñÏáõÙÝ»ñ è. ø³Ù³ÉÛ³Ý, ä. ä»ïñáëÛ³Ý ²Ù÷á÷áõÙ ²ß˳ï³ÝùáõÙ ëï³óí³Í ¿ ëïáñÇÝ ·Ý³Ñ³ï³Ï³Ý áñáß Ñ³Ù³ë»é ·ñ³ýÝ»ñÇ ÙÇç³Ï³Ûù³ÛÇÝ Ý»ñÏÙ³Ý Ù»ç û·ï³·áñÍíáÕ ·áõÛÝ»ñÇ ³é³í»É³·áõÛÝ Ñݳñ³íáñ ÃíÇ Ñ³Ù³ñ: 5 3