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


Mathematical Problems of Computer Science 32, 70{73, 2009.

On I nter val T otal Color ings of T r ees

P e t r o s A . P e t r o s ya n y 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

pet petros@ipia.sci.am, anishashikyan@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 T
(T 6= K1) is a tree and ¢(T ) + 2 · t · M(T ) then T has an interval total t¡coloring,
where ¢(T ) is the maximum degree of vertices in T and M(T ) is a parameter which
can be e®ectively found for any T .

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

7 0