D:\sbornik\...\Article.DVI


Mathematical Problems of Computer Science 24, 2005, 82{85.

On T r ees with a Special P r oper P ar tial 0 ¡ 1 Color ings

V a h a n V . Mkr t c h ya n

Department of Informatics and Applied Mathematics, Yerevan State University

e-mail vahanmkrtchyan2002yahoo.com

Abstract

It is proved that in a tree in which the distance between any two endpoints is even,
there is a maximum proper partial 0 ¡1 coloring such that the edges colored by 0 form
a maximum matching.

Refer ences

[1 ] L o va s z L ., P lu m m e r M.D ., Ma t c h in g Th e o r y, A n n a ls o f D is c r e t e Ma t h . 2 9 , N o r t h
H o lla n d , 1 9 8 6 .

[2 ] H a r a r y F., \ Gr a p h Th e o r y" , A d d is o n -W e s le y, R e a d in g , MA , 1 9 6 9 .

гïáõÏ ïÇåÇ ×ß·ñÇï Ù³ëݳÏÇ 0-1 Ý»ñÏáõÙÝ»ñ å³ñáõݳÏáÕ Í³é»ñÇ Ù³ëÇÝ

ì.ì. ØÏñïãÛ³Ý

²Ù÷á÷áõÙ

²ß˳ï³ÝùáõÙ óáõÛó ¿ ïñí»É, áñ ³ÛÝ Í³é»ñáõÙ, áñáÝóáõÙ ó³Ýϳó³Í »ñÏáõ ϳËí³Í
·³·³ÃÝ»ñÇ Ñ»é³íáñáõÃÛáõÝÁ ½áõÛ· ÃÇí ¿, ·áÛáõÃÛáõÝ áõÝÇ Ù³ùëÇÙ³É ×ß·ñÇï Ù³ëݳÏÇ
0-1 Ý»ñÏáõÙ, áñ 0 ·áõÛÝáí Ý»ñÏí³Í ÏáÕ»ñÇ µ³½ÙáõÃÛáõÝÁ ϳ½ÙáõÙ ¿ ͳéÇ Ù³ùëÇÙ³É
½áõ·³ÏóáõÙ:

8 2