D:\sbornik\...\Tpel_new.DVI


Mathematical Problems of Computer Science 35, 19{25, 2011.

Upper B ounds for the M aximum Span in I nter val

T otal Color ings of Gr aphs

P e t r o s A . P e t r o s ya n y a n d N e r s e s A . K h a c h a t r ya n z

yInstitute for Informatics and Automation Problems of NAS of RA,
zDepartment of Informatics and Applied Mathematics, YSU

e-mail: pet petros@ipia.sci.am, xachnerses@gmail.com

Abstract

An interval total t-coloring of a graph G is a total coloring of G with colors 1; 2; : : : ; t
such that at least one vertex or edge of G is colored by i, i = 1; 2; : : : ; t, and the
edges incident to each vertex v together with v are colored by dG(v) + 1 consecutive
colors, where dG(v) is the degree of a vertex v in G. In this paper we prove that if a
connected graph G with n vertices admits an interval total t-coloring, then t · 2n ¡ 1.
Furthermore, we show that if G is a connected r-regular graph with n vertices which
has an interval total t-coloring and n ¸ 2r + 2, then this upper bound can be improved
to 2n ¡ 3. We also give some other upper bounds for the maximum span in interval
total colorings of graphs.

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 athematics 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 ( in R u s s ia n ) .

[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 ] M. B e h z a d ,\ Gr a p h s a n d t h e ir c h r o m a t ic n u m b e r s " , P h .D . t h e s is , Mic h ig a n S t a t e U n i-
ve r s it y, 1 9 6 5 .

[6 ] K . Gia r o , M. K u b a le a n d 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 .

[7 ] 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
( in R u s s ia n ) .

[8 ] P .A . P e t r o s ya n ,\ In t e r va l t o t a 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 " , P roceedings of
the CSIT Conference, p p . 8 4 -8 5 , 2 0 0 7 .

[9 ] P .A . P e t r o s ya n ,\ In t e r va l t o t a l c o lo r in g s o f c e r t a in g r a p h s " , M athematical P roblems of
Computer Science, Vol. 31, p p . 1 2 2 -1 2 9 , 2 0 0 8 .

1 9



2 0 Upper Bounds for the Maximum Span in Interval Total Colorings of Graphs

[1 0 ] P .A . P e t r o s ya n , A .S . S h a s h ikya n ,\ On in t e r va l t o t a l c o lo r in g s o f t r e e s " , M athematical
P roblems of Computer Science, Vol. 32, p p . 7 0 -7 3 , 2 0 0 9 .

[1 1 ] P .A . P e t r o s ya n , A .Y u . To r o s ya n ,\ In t e r va l t o t a l c o lo r in g s o f c o m p le t e g r a p h s " , P roceed-
ings of the CSIT Conference, p p . 9 9 -1 0 2 , 2 0 0 9 .

[1 2 ] 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 athematics 3 1 0 , p p . 1 5 8 0 -1 5 8 7 , 2 0 1 0 .

[1 3 ] V .G. V iz in g , \ Ch r o m a t ic in d e x o f m u lt ig 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 6 5 ( in
R u s s ia n ) .

[1 4 ] 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, 1 9 9 6 .

[1 5 ] H .P . Y a p , To t a l Co lo r in g s o f Gr a p h s , L e c t u r e N o t e s in Ma t h e m a t ic s 1 6 2 3 , S p r in g e r -
V e r la g , 1 9 9 6 .

¶ñ³ýÝ»ñÇ ÙÇç³Ï³Ûù³ÛÇÝ Édzϳï³ñ
Ý»ñÏáõÙÝ»ñáõÙ Ù³ëݳÏóáÕ ·áõÛÝ»ñÇ ³é³í»É³·áõÛÝ

Ñݳñ³íáñ ÃíÇ í»ñÇÝ ·Ý³Ñ³ï³Ï³ÝÝ»ñ

ä. ². ä»ïñáëÛ³Ý, Ü. ². ʳã³ïñÛ³Ý

G ·ñ³ýÇ Édzϳï³ñ Ý»ñÏáõÙÁ i = 1 ; 2 ; : : : ; t ·áõÛÝ»ñáí ϳÝí³Ý»Ýù ÙÇç³Ï³Ûù³ÛÇÝ
Édzϳï³ñ t–Ý»ñÏáõÙ, »Ã» ³Ù»Ý ÙÇ i ·áõÛÝáí, i = 1 ; 2 ; : : : ; t Ý»ñÏí³Í ¿ ³éÝí³½Ý Ù»Ï
·³·³Ã ϳ٠ÏáÕ ¨ Ûáõñ³ù³ÝãÛáõñ v ·³·³ÃÇÝ ÏÇó ÏáÕ»ñÁ ¨ ³Û¹ ·³·³ÃÁ Ý»ñÏí³Í »Ý
dG ( v ) + 1 ѳçáñ¹³Ï³Ý ·áõÛÝ»ñáí, áñï»Õ dG ( v ) -áí Ý߳ݳÏí³Í ¿ v ·³·³ÃÇ ³ëïÇ׳ÝÁ
G ·ñ³ýáõÙ: ²Ûë ³ß˳ï³ÝùáõÙ ³å³óáõóíáõÙ ¿, áñ »Ã» n ·³·³Ã³ÝÇ G ϳå³Ïóí³Í
·ñ³ýÁ áõÝÇ ÙÇç³Ï³Ûù³ÛÇÝ Édzϳï³ñ t–Ý»ñÏáõÙ, ³å³ t · 2 n ¡ 1 : ²í»ÉÇÝ, óáõÛó ¿
ïñíáõÙ, áñ »Ã» n ·³·³Ã³ÝÇ G ϳå³Ïóí³Í r–ѳٳë»é ·ñ³ýÁ áõÝÇ ÙÇç³Ï³Ûù³ÛÇÝ
Édzϳï³ñ t–Ý»ñÏáõÙ ¨ n ¸ 2 r + 2 , ³å³ t · 2 n ¡ 3 : ܳ¨ ³ß˳ï³ÝùáõÙ
ïñíáõÙ »Ý ·ñ³ýÝ»ñÇ ÙÇç³Ï³Ûù³ÛÇÝ Édzϳï³ñ Ý»ñÏáõÙÝ»ñáõÙ Ù³ëݳÏóáÕ ·áõÛÝ»ñÇ
³é³í»É³·áõÛÝ Ñݳñ³íáñ ÃíÇ ³ÛÉ ·Ý³Ñ³ï³Ï³ÝÝ»ñ: