D:\sbornik\...\tpel.DVI Mathematical Problems of Computer Science 36, 13-16, 2012. A N ote on I nter val E dge-color ings of Gr aphs R a fa ye l R . K a m a lia n yz a n d P e t r o s A . P e t r o s ya n yx yInstitute for Informatics and Automation Problems of NAS of RA, zDepartment of Applied Mathematics and Informatics, RAU xDepartment of Informatics and Applied Mathematics, YSU e-mail: rrkamalian@yahoo.com, pet petros@ipia.sci.am Abstract An edge-coloring of a graph G with colors 1; : : : ; t is called an interval t-coloring if for all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integers. In this note we prove that if a connected graph G with n vertices admits an interval t-coloring, then t · 2n ¡ 3. We also show that if G is a connected r-regular graph with n vertices that has an interval t-coloring and n ¸ 2r + 2, then this upper bound can be improved to 2n ¡ 5. Refer ences [1 ] A .S . A s r a t ia n , C.J. Ca s s e lg r e n , \ On in t e r va l e d g e c o lo r in g s o f ( ®; ¯ ) -b ir e g u la r b ip a r t it e g r a p h s " , D iscrete M ath. 307, p p . 1 9 5 1 -1 9 5 6 , 2 0 0 6 . [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, p p . 2 5 -3 4 , 1 9 8 7 . [3 ] 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 62, p p . 3 4 -4 3 , 1 9 9 4 . [4 ] M.A . A xe n o vic h , \ On in t e r va l c o lo r in g s o f p la n a r g r a p h s " , Congr. Numer. 159, p p . 7 7 -9 4 , 2 0 0 2 . [5 ] 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 iscrete M ath. 236, p p . 1 3 1 -1 4 3 , 2 0 0 1 . [6 ] R .R . K a m a lia 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 , D o c t o r a l Th e s is , N o vo s ib ir s k, 1 9 9 0 . [7 ] R .R . K a m a lia n , P .A . P e t r o s ya n , \ A n o t e o n u p p e r b o u n d s fo r t h e m a xim u m s p a n in 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 " , D iscrete M ath. 312, p p . 1 3 9 3 -1 3 9 9 , 2 0 1 2 . [8 ] P .A . P e t r o s ya n , \ In t e r va l e d g e -c o lo r in g s o f c o m p le t e g r a p h s a n d n-d im e n s io n a l c u b e s " , D iscrete M ath. 310, p p . 1 5 8 0 -1 5 8 7 , 2 0 1 0 . 1 3 1 4 A Note on Interval Edge-colorings of Graphs ¶ñ³éáõÙ ·ñ³ýÝ»ñÇ ÙÇç³Ï³Ûù³ÛÇÝ ÏáÕ³ÛÇÝ Ý»ñÏáõÙÝ»ñÇ Ù³ëÇÝ è. ø³Ù³ÉÛ³Ý ¨ ä. ä»ïñáëÛ³Ý ²Ù÷á÷áõÙ G ·ñ³ýÇ ÏáÕ³ÛÇÝ ÝñÏáõÙÁ 1 ; : : : ; t ·áõÛÝñáí ϳÝí³Ý»Ýù ÙÇç³Ï³Ûù³ÛÇÝ t–Ý»ñÏáõÙ, »Ã» µáÉáñ ·áõÛÝ»ñÁ û·ï³·áñÍí»É »Ý ¨ Ûáõñ³ù³ÝãÛáõñ ·³·³ÃÇÝ ÏÇó ÏáÕ»ñÁ Ý»ñÏí³Í »Ý ½áõÛ· ³é ½áõÛ· ï³ñµ»ñ ¨ ѳçáñ¹³Ï³Ý ·áõÛÝ»ñáí: ²Ûë ³ß˳ï³ÝùáõÙ ³å³óáõóíáõÙ ¿, áñ »Ã» ·³·³Ã³ÝÇ G ϳå³Ïóí³Í ·ñ³ýÁ áõÝÇ ÙÇç³Ï³Ûù³ÛÇÝ t–Ý»ñÏáõÙ, ³å³ t · 2 n¡ 3 : ܳ¨ ³ß˳ï³ÝùáõÙ óáõÛó ¿ ïñíáõÙ, áñ »Ã» n ·³·³Ã³ÝÇ G ϳå³Ïóí³Í r–ѳٳë»é ·ñ³ýÁ áõÝÇ ÙÇç³Ï³Ûù³ÛÇÝ t-Ý»ñÏáõÙ ¨ n ¸ 2 r + 2 , ³å³ t · 2 n ¡ 5 : Çàìåòêà î èíòåðâàëüíûx ðåáåðíûx ðàñêðàñêàx ãðàôîâ Ð. Êàìàëÿí è Ï. Ïåòðîñÿí Àííîòàöèÿ Èíòåðâàëüíîé t-ðàñêðàñêîé ãðàôà G íàçîâåì ïðàâèëüíóþ ðàñêðàñêó ðåáåð G â öâåòà 1 ; :::; t ïðè êîòîðîé â êàæäûé öâåò i, 1 · i · t îêðàøåíî xîòÿ áû îäíî ðåáðî ãðàôà G, è ðåáðà, èíöèäåíòíûå êàæäîé âåðøèíå G, îêðàøåíû â ïîñëåäîâàòåëüíûå öâåòà.  íàñòîÿùåé ðàáîòå äîêàçàíî, ÷òî åñëè ñâÿçíûé ãðàô G ñ n âåðøèíàìè èìååò èíòåðâàëüíóþ t–ðàñêðàñêó, òî t · 2 n ¡ 3 . Òàêæå â äàííîé ðàáîòå ïîêàçàíî, ÷òî åñëè ñâÿçíûé r-ðåãóëÿðíûé ãðàô G ñ n âåðøèíàìè èìååò èíòåðâàëüíóþ t-ðàñêðàñêó è n ¸ 2 r + 2 , òî t · 2 n ¡ 5