D:\sbornik\...\MIRUMYAN.DVI


Mathematical Problems of Computer Science 23, 2004, 32{35.

Some Simpli¯cation of Complete System of

T r ansfor mations for P r oper E dge Colour ings of

B ipar tite Gr aphs

A lis a K . Mir u m ya n

Institute for Informatics and Automation Problems of NAS of RA

e-mail mirumyan@rambler.ru

Abstract

In the investigation of a set of combinatorial objects, an important problem is to
¯nd a complete system of transformations. In this article a set of (k + 1)-colourings of
an arbitrary bipartite graph are considered. It is prooved that 2-transformation is a
complete system of transformations for this type of set.

Refer ences

[1 ] A . S . A s r a t ia n a n d A . N . Mir u m ya n , Tr a n s fo r m a t io n o f E d g e Co lo u r in g s o f a b ip a r t it e
m u lt ig r a p h , a n d t h e ir a p p lic a t io n s , S o vie t Ma t h . D o kl. vo l. 4 3 , 1 9 9 1 .

[2 ] F. H a r a r y, Gr a p h t h e o r y, A d d is o n -W e s le y, 1 9 6 9 .

[3 ] A . S . A s r a t ia n , Tr is t a n M. J. D e n le y & R . H a g g kvis t , B ip a r t it e g r a p h s a n d t h e ir a p p li-
c a t io n s , Ca m b r id g e U n ive r s it y, 1 9 9 8 .

[4 ] A . S . A s r a t ia n a n d A . N . Mir u m ya n , On t r a n s fo r m a t io n s o f e d g e c o lo u r in g s o f t h e
c o m p le t e b ip a r t it e g r a p h Knn:, A ka d . N a u k R e s p u b . A r m e n ia D o kl. 9 5 , 1 9 9 5 .

ºñÏÙ³ë ·ñ³ý»ñÇ ë»÷³Ï³Ý ÏáÕÇ ·áõݳíáñÙ³Ý Ó¨³÷áËáõÃÛáõÝÝ»ñÇ ÉñÇí
ѳٳϳñ·Ç å³ñ½»óáõÙ

². Ü. ØÇñáõÙÛ³Ý

²Ù÷á÷áõÙ

гٳÏó³Ï³Ý ûµÛ»ÏïÝ»ñÇ µ³½ÙáõÃÛ³Ý Ñ»ï³½áïÙ³Ý ÁÝóóùáõ٠ϳñ¨áñ ÑÇÙݳËݹÇñ
¿ Ó¨³÷áËáõÃÛáõÝÝ»ñÇ ÉñÇí ѳٳϳñ·Ç ·ïÝ»ÉÁ:

3 2