D:\sbornik\...\tpel3.DVI


Mathematical Problems of Computer Science 32, 78{85, 2009.

I nter val T otal Color ings of Gr aphs with a Spanning

Star

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

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

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 G = (V; E) is a graph containing the vertex u with dG(u) = jV j ¡ 1,
k(G) = maxv2V (v 6=u)dG(v) < jV j ¡ 1 and G admits an interval total t¡coloring then
t · jV j + 2k(G). We also show that this upper bound is sharp. Further we determine
all possible values of t for which the wheels have an interval total t¡coloring.

Refer ences

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

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

[3 ] 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 .
[4 ] 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ϳï³ñ Ý»ñÏáõÙÁ 1 ; 2 ; : : : ; t ·áõÛÝ»ñáí ϳÝí³Ý»Ýù ÙÇç³Ï³Ûù³ÛÇÝ
Édzϳï³ñ t –Ý»ñÏáõÙ, »Ã» ³Ù»Ý ÙÇ i ·áõÛÝáí, i = 1 ; 2 ; : : : ; t, Ý»ñÏí³Í ¿ ³éÝí³½Ý Ù»Ï
·³·³Ã, ϳ٠ÏáÕ, ¨ Ûáõñ³ù³ÝãÛáõñ v ·³·³ÃÇÝ ÏÇó ÏáÕ»ñÁ, ¨ ³Û¹ ·³·³ÃÁ Ý»ñÏí³Í ¿
dG ( v ) + 1 ѳçáñ¹³Ï³Ý ·áõÛÝ»ñáí, áñï»Õ dG ( v ) -áí Ý߳ݳÏí³Í v ·³·³ÃÇ ³ëïÇ׳ÝÁ G
·ñ³ýáõÙ: ²Ûë ³ß˳ï³ÝùáõÙ ³å³óáõóí³Í ¿, áñ »Ã» G = ( V; E ) -Ý, áñÁ å³ñáõݳÏáõÙ ¿
³ÛÝåÇëÇ u ·³·³Ã, áñ dG ( u ) = jV j¡ 1 , k ( G) = m a xv2V (v 6=u)dG ( v ) < jV j¡ 1 ¨ G ·ñ³ýÝ áõÝÇ
ÙÇç³Ï³Ûù³ÛÇÝ Édzϳï³ñ t- Ý»ñÏáõÙ, ³å³ then t · jV j + 2 k ( G ) : ܳ¨ óáõÛó ¿ ïñí³Í,

7 8



P. Petrosyan, N. Khachatryan 7 9

áñ ³Ûë í»ñÇÝ ·Ý³Ñ³ï³Ï³ÝÁ ѳë³Ý»ÉÇ ¿: ²ÛÝáõÑ»ï¨, ·ïÝí»É »Ý t- Ç µáÉáñ Ñݳñ³íáñ
³ñÅ»ùÝ»ñÁ, áñáÝó ѳٳñ ³ÝÇíÝ»ñÁ áõÝ»Ý ÙÇç³Ï³Ûù³ÛÇÝ Édzϳï³ñ t- Ý»ñÏáõÙ: