IntFinalSieve.DVI


Mathematical Problems of Computer Science 23, 2004, 100{101.

Su±cient Condition for the P r oper ty of a Gr aph to B e

B ipar tite

R a fa e l R . K a m a lia n a n d V a h a g n V . Mkr t c h ya n

Institute for Informatics and Automation Problems of NAS of RA

e-mails rrkamalian@yahoo.com, vahanmkrtchyan2002@yahoo.com

Abstract

A su±cient condition is found to determine when a graph with vertices on the
integer sieve of Rn is bipartite. This condition can be useful in cases when the
description of a graph does not contain an appropriate bipartition of the set of its
vertices.

Refer ences

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

[2 ] K o n ig D ., Gr a p h e n u n d Ma t r iz e s . M at. F iz. L apok., v.3 8 , p p .1 1 6 -1 1 9 , 1 9 3 1 .

´³í³ñ³ñ å³ÛÙ³Ý ·ñ³ýÇ »ñÏÏáÕÙ³ÝÇáõÃÛ³Ý Ñ³Ù³ñ

è. è.ø³Ù³ÉÛ³Ý ¨ ì. ì. ØÏñïãÛ³Ý

²Ù÷á÷áõÙ

Rn ï³ñ³ÍáõÃÛ³Ý ³ÙµáÕç³ÃÇí ó³ÝóÇ íñ³ ïñí³Í ·³·³ÃÝ»ñáí ·ñ³ýÇ Ñ³Ù³ñ
·ïÝí»É ¿ »ñÏÏáÕÙ³ÝÇáõÃÛ³Ý Ñ³Ûï³ÝÇß: ²Ûë ѳÛï³ÝÇßÁ ϳñáÕ ¿ û·ï³Ï³ñ ÉÇÝ»É
³ÛÝ ¹»åù»ñáõÙ, »ñµ ·ñ³ýÇ Ýϳñ³·ñáõÃÛáõÝÁ ãÇ å³ñáõݳÏáõÙ ·³·³ÃÝ»ñÇ µ³½ÙáõÃÛ³Ý
ѳñÙ³ñ³í»ï ïñáÑáõÙ:

1 0 0