D:\sbornik\...\article.DVI


Mathematical Problems of Computer Science 31, 122{129, 2008.

I nter val T otal Color ings of Cer tain Gr aphs

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-mail: pet petros@fipia.sci.am, yahoo.comg

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 with each vertex v together with v are colored by (dG(v) + 1)
consecutive colors, where dG(v) is the degree of the vertex v in G. It is proved that
complete graphs, complete bipartite graphs and n¡dimensional cubes have interval
total colorings and bounds are found for the possible number of colors in such colorings.

Refer ences

[1 ] A .S . A s r a t ia n , T.M.J. D e n le y, R . H a g g kvis t , B ip a r t it e Gr a p h s a n d Th e ir A p p lic a t io n s ,
Ca m b r id g e Tr a c t s in Ma t h e m a t ic s , 1 3 1 , Ca m b r id g e U n ive r s it y P r e s s , 1 9 9 8 .

[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 ournal of Combin. Theory, Ser. B , vo l. 6 2 , p p . 3 4 -4 3 , 1 9 9 4 .

[4 ] M. B e h z a d , Gr a p h s a n d Th e ir Ch 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 .

[5 ] M. B e h z a d , G. Ch a r t r a n d , J.K . Co o p e r , \ Th e c o lo u r n u m b e r s o f c o m p le t e g r a p h s " ,
J ournal of L ondon M ath. Soc. 42, p p . 2 2 6 -2 2 8 , 1 9 6 7 .

[6 ] O.V . B o r o d in , \ On t h e t o t a l c o lo u r in g o f p la n a r g r a p h s " , J . R eine Angew. M ath. 394,
p p . 1 8 0 -1 8 5 , 1 9 8 9 .

[7 ] O.V . B o r o d in , A .V . K o s t o c h ka , D .R . W o o d a ll, \ To t a l c o lo r in g s o f p la n a r g r a p h s wit h
la r g e m a xim u m d e g r e e " , J ournal of Graph Theory 26, p p . 5 3 -5 9 , 1 9 9 7 .

[8 ] K .H . Ch e w, H .P . Y a p , \ To t a l c h r o m a t ic n u m b e r o f c o m p le t e r¡ p a r t it e g r a p h s " , J ournal
of Graph Theory 16, p p . 6 2 9 -6 3 4 , 1 9 9 2 .

[9 ] T.R . Je n s e n , B .To ft , Gr a p h Co lo r in g P r o b le m s , W ile y In t e r s c ie n c e S e r ie s in D is c r e t e
Ma t h e m a t ic s a n d Op t im iz a t io n , 1 9 9 5 .

[1 0 ] A .V . K o s t o c h ka , \ Th e t o t a l c o lo r in g o f a m u lt ig r a p h s wit h m a xim a l d e g r e e 4 " , D iscrete
M athematics 17, p p . 1 6 1 -1 6 3 , 1 9 7 7 .

[1 1 ] A .V . K o s t o c h ka , \ Th e t o t a l c o lo r in g o f a m u lt ig r a p h s wit h m a xim a l d e g r e e 5 is a t m o s t
s e ve n " , D iscrete M athematics 162, p p . 1 9 9 -2 1 4 , 1 9 9 6 .

[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 u r in g s o f c o m p le t e g r a p h s a n d n¡ c u b e s " , M athe-
matical P roblems of Computer Science, vo l. 2 5 , p p . 5 -8 , 2 0 0 6 .

[1 3 ] M. R o s e n fe ld , \ On t h e t o t a l c o lo r in g o f c e r t a in g r a p h s " , Israel J . M ath. 9, p p . 3 9 6 -4 0 2 ,
1 9 7 1 .

1 2 2



P. Petrosyan 1 2 3

[1 4 ] D .P . S a n d e r s , Y . Zh a o , \ On t o t a l 9 -c o lo r in g p la n a r g r a p h s o f m a xim u m d e g r e e s e ve n " ,
J ournal of Graph Theory 31, p p . 6 7 -7 3 ,1 9 9 9 .

[1 5 ] N . V ija ya d it ya , \ On t h e t o t a l c h r o m a t ic n u m b e r o f a g r a p h " , J ournal of L ondon M ath.
Soc. (2) 3, p p . 4 0 5 -4 0 8 , 1 9 7 1 .

[1 6 ] V .G. V iz in g , \ On a n e s t im a t e o f t h e c h r o m a t ic c la s s o f a p¡ g r a p h " , D iskret. Analiz 3,
p p . 2 5 -3 0 , 1 9 6 4 .

[1 7 ] 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 8 ] 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 , B e r lin , 1 9 9 6 .
[1 9 ] Z. Zh a n g , J. Zh a n d , J. W a n g , \ Th e t o t a l c h r o m a t ic n u m b e r s o f s o m e g r a p h s " , Scientia

Sinica A 31, p p . 1 4 3 4 -1 4 4 1 , 1 9 8 8 .

àñáß ·ñ³ýÝ»ñÇ ÙÇç³Ï³Ûù³ÛÇÝ Édzϳï³ñ Ý»ñÏáõÙÝ»ñ

ä. ä»ïñáëÛ³Ý

²Ù÷á÷áõÙ

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