D:\sbornik\...\tpel1.DVI


Mathematical Problems of Computer Science 33, 54{58, 2010.

On I nter val T otal Color ings of Doubly Convex

B ipar tite Gr aphs

P e t r o s A . P e t r o s ya n yz a n d A n i S . S h a s h ikya 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, anishashikyan@gmail.com

Abstract

A bipartite graph G = (U; V; E) is doubly convex if all its vertices from the U can
be numbered 1; 2; : : : ; jUj and all vertices from V can be numbered 1; 2; : : : ; jV j in such
a way that for any vertex of G the set of numbers assigned to neighbors is an interval
of integers. 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 all
doubly convex bipartite graphs have an interval total coloring. Furthermore, we give
some bounds for the minimum and the maximum span in interval total colorings of
these graphs.

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 t h e ir A p p lic a t io n s ,
Ca m b r id g e U n ive r s it y P r e s s , Ca m b r id g e , 1 9 9 8 .

[2 ] 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 .

[3 ] 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 .

[4 ] 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 .

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

[6 ] 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 b ip a r t it e g r a p h s " , P ro-
ceedings of the CSIT Conference, p p . 9 5 -9 8 , 2 0 0 9 .

[7 ] 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 .

[8 ] 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 b ip a r t it e g r a p h s " , Ma s t e r 's Th e s is , Y e r e -
va n S t a t e U n ive r s it y, 2 0 0 9 , 2 9 p .

[9 ] 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 .

5 4



P. Petrosyan, A. Shashikyan 5 5

[1 0 ] 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 »ñÏÏáÕÙ³ÝÇ ·ñ³ýÁ ÏáãíáõÙ ¿ »ñϳÏÇ áõéáõóÇÏ, »Ã» G ·ñ³ýÇ ·³·³ÃÝ»ñÁ ϳñ»ÉÇ
¿ ³ÛÝå»ë ѳٳñ³Ï³É»É, áñ ³Ù»Ý ÙÇ ÏáÕÙÇ ó³Ýϳó³Í ·³·³Ã ѳñ¨³Ý ÉÇÝÇ ÙÛáõë
ÏáÕÙÇ Ñ³çáñ¹³Ï³Ý ǹ»ùëÝ»ñáí ·³·³ÃÝ»ñÇ Ñ»ï: G ·ñ³ýÇ Édzϳï³ñ Ý»ñÏáõÙÁ 1 ; 2 ; :::t
·áõÛÝ»ñáí ϳÝí³Ý»Ýù ÙÇç³Ï³Ûù³ÛÇÝ Édzϳï³ñ t-Ý»ñÏáõÙ, »Ã» ³Ù»Ý ÙÇ i ·áõÛÝáí,
i = 1 ; 2 ; :::; t Ý»ñÏí³Í ¿ ³éÝí³½Ý Ù»Ï ·³·³Ã ϳ٠ÏáÕ ¨ Ûáõñ³ù³ÝãÛáõñ v ·³·³ÃÇÝ
ÏÇó ÏáÕ»ñÁ ¨ ³Û¹ ·³·³ÃÁ Ý»ñÏí³Í »Ý dG ( v ) + 1 ѳçáñ¹³Ï³Ý ·áõÛÝ»ñáí, áñï»Õ -áí
Ý߳ݳÏí³Í ¿ v ·³·³ÃÇ ³ëïÇ׳ÝÁ G ·ñ³ýáõÙ: ²Ûë ³ß˳ï³ÝùáõÙ ³å³óáõóíáõÙ ¿, áñ
µáÉáñ »ñϳÏÇ áõéáõóÇÏ »ñÏÏáÕÙ³ÝÇ ·ñ³ýÝ»ñÁ áõÝ»Ý ÙÇç³Ï³Ûù³ÛÇÝ Édzϳï³ñ Ý»ñÏáõÙ:
²í»ÉÇÝ, ³ß˳ï³ÝùáõÙ ïñíáõÙ »Ý áñáß ·Ý³Ñ³ï³Ï³ÝÝ»ñ ³Ûë ·ñ³ýÝ»ñÇ ÙÇç³Ï³Ûù³ÛÇÝ
Édzϳï³ñ Ý»ñÏáõÙÝ»ñáõÙ Ù³ëݳÏóáÕ ·áõÛÝ»ñÇ Ýí³½³·áõÛÝ ¨ ³é³í»É³·áõÛÝ Ñݳñ³íáñ
ÃíÇ Ñ³Ù³ñ: