Petros's_article.DVI


Mathematical Problems of Computer Science 49, 7{17, 2018.

On Locally-B alanced 2-P ar titions of Complete

M ultipar tite Gr aphs

A r a m H . Gh a r ib ya n y a n d P e t r o s A . P e t r o s ya n yz

yDepartment of Informatics and Applied Mathematics, YSU,
zInstitute for Informatics and Automation Problems of NAS RA

e-mail: aramgharibyan@gmail.com, petros petrosyan@ysu.am, pet petros@ipia.sci.am

Abstract

A 2-partition of a graph G is a function f : V (G) ! fWhite; Blackg. A 2-partition
f of a graph G is locally-balanced with an open neighborhood if for every v 2 V (G),

jjfu 2 NG(v): f(u) = Whitegj ¡ jfu 2 NG(v): f(u) = Blackgjj · 1;

where NG(v) = fu 2 V (G): uv 2 E(G)g. A 2-partition f0 of a graph G is locally-
balanced with a closed neighborhood if for every v 2 V (G),

¯̄
jfu 2 NG[v]: f 0(u) = Whitegj ¡ jfu 2 NG[v]: f0(u) = Blackgj

¯̄
· 1;

where NG[v] = NG(v) [ fvg. In this paper we give necessary and su±cient conditions
for the existence of locally-balanced 2-partitions of complete multipartite graphs.

Keywords: 2-partition, Locally-balanced 2-partition, Equitable coloring, Com-
plete multipartite graph.

1 . In t r o d u c t io n

A ll g r a p h s c o n s id e r e d in t h is wo r k a r e ¯ n it e , u n d ir e c t e d , a n d h a ve n o lo o p s o r m u lt ip le e d g e s .
L e t V ( G) a n d E ( G) d e n o t e t h e s e t s o f ve r t ic e s a n d e d g e s o f a g r a p h G, r e s p e c t ive ly. Th e s e t
o f n e ig h b o r s o f a ve r t e x v in G is d e n o t e d b y NG ( v ) . L e t NG[v] = NG ( v ) [fvg. A g r a p h G is
c a lle d a c o m p le t e n-p a r t it e ( n ¸ 2 ) g r a p h if it s ve r t ic e s c a n b e p a r t it io n e d in t o n n o n e m p t y
in d e p e n d e n t s e t s X1; : : : ; Xn s u c h t h a t e a c h ve r t e x in Xi is a d ja c e n t t o a ll t h e o t h e r ve r t ic e s
in Xj fo r 1 · i < j · n. L e t Kr1;r2;:::;rn d e n o t e a c o m p le t e n-p a r t it e g r a p h wit h in d e p e n d e n t
s e t s X1; X2; : : : ; Xn o f s iz e s r1; r2; : : : ; rn. Th e t e r m s a n d c o n c e p t s t h a t we d o n o t d e ¯ n e c a n
b e fo u n d in [8 , 1 5 ].

A 2 -partition o f a g r a p h G is a fu n c t io n f : V ( G) ! fWhite; B lackg. A 2 -p a r t it io n f
o f a g r a p h G is locally-balanced with an open neighborhood if fo r e ve r y v 2 V ( G ) ,

jjfu 2 NG ( v ) : f ( u ) = Whitegj ¡ jfu 2 NG ( v ) : f ( u) = B lackgjj · 1 :
A 2 -p a r t it io n f 0 o f a g r a p h G is locally-balanced with a closed neighborhood if fo r e ve r y
v 2 V ( G) ,

jjfu 2 NG[v]: f 0 ( u ) = Whitegj ¡ jfu 2 NG[v]: f 0 ( u) = B lackgjj · 1 :

7



8 On Locally-Balanced 2-Partitions of Complete Multipartite Graphs

Th e c o n c e p t o f lo c a lly-b a la n c e d 2 -p a r t it io n o f g r a p h s wa s in t r o d u c e d b y B a likya n a n d
K a m a lia n [1 2 ] in 2 0 0 5 , a n d it c a n b e c o n s id e r e d a s a s p e c ia l c a s e o f e qu it a b le c o lo r in g s
o f h yp e r g r a p h s [1 ]. In [1 ], B e r g e o b t a in e d s o m e s u ± c ie n t c o n d it io n s fo r t h e e xis t e n c e o f
e qu it a b le c o lo r in g s o f h yp e r g r a p h s . In [7 , 9 , 1 0 , 1 4 ], t h e a u t h o r s c o n s id e r e d t h e p r o b le m s o f
t h e e xis t e n c e a n d c o n s t r u c t io n o f p r o p e r ve r t e x-c o lo r in g o f a g r a p h fo r wh ic h t h e n u m b e r o f
ve r t ic e s in a n y t wo c o lo r c la s s e s d i®e r b y a t m o s t o n e . In [1 1 ], 2 -ve r t e x-c o lo r in g s o f g r a p h s
we r e c o n s id e r e d fo r wh ic h e a c h ve r t e x is a d ja c e n t t o t h e s a m e n u m b e r o f ve r t ic e s o f e ve r y
c o lo r . In p a r t ic u la r , in [1 1 ], it wa s p r o ve d t h a t t h e p r o b le m o f t h e e xis t e n c e o f s u c h a
c o lo r in g is NP -c o m p le t e e ve n fo r t h e ( 2 p; 2 q ) -b ir e g u la r ( p; q ¸ 2 ) b ip a r t it e g r a p h s . In [1 2 ],
B a likya n a n d K a m a lia n p r o ve d t h a t t h e p r o b le m o f e xis t e n c e o f lo c a lly-b a la n c e d 2 -p a r t it io n
wit h a n o p e n n e ig h b o r h o o d o f b ip a r t it e g r a p h s wit h m a xim u m d e g r e e 3 is NP -c o m p le t e .
L a t e r , t h e y a ls o p r o ve d [1 3 ] t h e s im ila r r e s u lt fo r lo c a lly-b a la n c e d 2 -p a r t it io n s wit h a c lo s e d
n e ig h b o r h o o d . In [2 , 3 , 4 ], t h e n e c e s s a r y a n d s u ± c ie n t c o n d it io n s fo r t h e e xis t e n c e o f lo c a lly-
b a la n c e d 2 -p a r t it io n s o f t r e e s we r e o b t a in e d . In [6 ], t h e a u t h o r s o b t a in e d s o m e n e c e s s a r y
c o n d it io n s fo r t h e e xis t e n c e o f lo c a lly-b a la n c e d 2 -p a r t it io n s o f E u le r ia n g r a p h s . In p a r t ic u la r ,
t h e y p r o ve d s o m e r e s u lt s o n t h e e xis t e n c e o f lo c a lly-b a la n c e d 2 -p a r t it io n s o f r o o k's g r a p h s
a n d c yc le p o we r s .

In t h e p r e s e n t p a p e r we g ive n e c e s s a r y a n d s u ± c ie n t c o n d it io n s fo r t h e e xis t e n c e o f
lo c a lly-b a la n c e d 2 -p a r t it io n s o f c o m p le t e m u lt ip a r t it e g r a p h s . A p r e lim in a r y ve r s io n o f t h is
p a p e r wa s p r e s e n t e d a t t h e 6 t h P o lis h Co m b in a t o r ia l Co n fe r e n c e , B e d le wo , P o la n d , 2 0 1 6 [5 ].

2 . Ma in R e s u lt s

B e fo r e we fo r m u la t e a n d p r o ve o u r r e s u lt s , we in t r o d u c e s o m e t e r m in o lo g y a n d n o t a t io n . Fo r
a n y 2 -p a r t it io n ' o f a g r a p h G, we d e ¯ n e ' a s fo llo ws : fo r a n y v 2 V ( G) , le t

'( v ) =

(
B lack, if '( v ) = White,
White, if '( v ) = B lack.

If ' is a 2 -p a r t it io n o f a g r a p h G a n d v 2 V ( G) , t h e n d e ¯ n e # ( v ) a n d # [v] a s fo llo ws :
# ( v ) = jfu 2 NG ( v ) : '( u ) = Whitegj ¡ jfu 2 NG ( v ) : '( u ) = B lackgj,
# [v] = jfu 2 NG[v]: '( u) = Whitegj ¡ jfu 2 NG[v]: '( u ) = B lackgj.

Cle a r ly, ' is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a n o p e n n e ig h b o r h o o d ( wit h a c lo s e d
n e ig h b o r h o o d ) if fo r e ve r y v 2 V ( G ) , j # ( v ) j · 1 ( j # [v]j · 1 ) .

If G is a c o m p le t e n-p a r t it e g r a p h a n d X is a p a r t o f G, t h e n X is c a lle d a n o d d ( e ve n )
p a r t if jXj is o d d ( jXj is e ve n ) . If G is a c o m p le t e n-p a r t it e g r a p h , t h e n b y m1, m2, a n d
m¸3 we d e n o t e t h e n u m b e r o f p a r t s o f G wit h o n e ve r t e x, t wo ve r t ic e s a n d a t le a s t t h r e e
ve r t ic e s , r e s p e c t ive ly. If ' is a 2 -p a r t it io n o f a c o m p le t e n-p a r t it e g r a p h G a n d X is a p a r t
o f G, t h e n b y WX ( BX ) we d e n o t e t h e n u m b e r o f White ( B lack ) ve r t ic e s o f t h e p a r t X. If
' is a 2 -p a r t it io n o f a c o m p le t e n-p a r t it e g r a p h G, t h e n b y W ( B ) we d e n o t e t h e n u m b e r o f
White ( B lack ) ve r t ic e s in G.

W e b e g in wit h t h e fo llo win g s im p le le m m a .

Lemma 1. If ' is a locally-balanced 2-partition of G, then ' is also a locally-balanced 2-
partition of G.

Lemma 2. If Kr1;r2:::;rn has a locally-balanced 2 -partition with an open neighborhood, then
for any part X, jWX ¡ BXj · 1 .



A. Gharibyan and P. Petrosyan 9

P r oof. L e t ' b e a a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a n o p e n n e ig h b o r h o o d o f Kr1;r2:::;rn .
S u p p o s e , t o t h e c o n t r a r y, t h a t t h e r e e xis t s a p a r t X0 s u c h t h a t e it h e r WX0 ¡ BX0 ¸ 2 o r
BX0 ¡ WX0 ¸ 2 . B y L e m m a 1 ., we c a n a s s u m e t h a t t h e r e e xis t s a p a r t X0 s u c h t h a t

WX0 ¡ BX0 ¸ 2 ( 1 )

It is e a s y t o s e e t h a t fo r a n y v 2 X,

# ( v ) = W ¡ B ¡ WX + BX .

Fr o m t h is a n d t a kin g in t o a c c o u n t t h a t fo r a n y v 2 V ( Kr1;r2:::;rn ) ; ¡ 1 · # ( v ) · 1 , we o b t a in
t h a t fo r a n y p a r t X,

¡ 1 · W ¡ B ¡ WX + BX · 1 : ( 2 )
B y ( 1 ) a n d ( 2 ) , we h a ve

W ¡ B ¸ 1 : ( 3 )
Fo r a n y p a r t Y ( Y 6= X0 ) , b y ( 2 ) , we h a ve

¡ 1 · W ¡ B ¡ WY + BY · 1 .

Fr o m t h is a n d ( 3 ) , we o b t a in t h a t fo r a n y p a r t Y ( Y 6= X0 ) ,

WY ¡ BY ¸ 0 : ( 4 )

L e t u s c o n s id e r a n y v 2 X ( X 6= X0 ) . Cle a r ly,

# ( v ) =
X

Y;Y 6=X
( WY ¡ BY ) =

X

Y;Y 6=X;X0
( WY ¡ BY ) + WX0 ¡ BX0 :

B y ( 1 ) a n d ( 4 ) , we g e t # ( v ) ¸ 2 , wh ic h is a c o n t r a d ic t io n .

T heor em 1. The graph Kr1;r2:::;rn has a locally-balanced 2-partition with an open neigh-
borhood if and only if the number of odd parts is even or one.

P r oof. A s s u m e t h a t Kr1;r2:::;rn h a s k e ve n p a r t s a n d s o d d p a r t s . S u p p o s e t h a t Kr1;r2:::;rn
h a s a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a n o p e n n e ig h b o r h o o d , b u t c o n t a in s o d d n u m b e r s
( s ¸ 3 ) o d d p a r t s . L e m m a 2 im p lie s t h a t fo r a n y p a r t X o f Kr1;r2:::;rn , jWX ¡ BXj · 1 . W e
d e c o m p o s e a ll t h e ve r t ic e s o f t h e g r a p h in t o t h r e e g r o u p s a s fo llo ws :

1 . a ll e ve n p a r t s Xi ( h e r e , we h a ve WXi ¡ BXi = 0 , b y L e m m a 2 ) ;

2 . a ll o d d p a r t s X0i wit h WX0i > BX
0
i
( h e r e , we h a ve WX0

i
¡ BX0

i
= 1 , b y L e m m a 2 ) ;

3 . a ll o d d p a r t s X00i wit h WX00i < BX00i ( h e r e , we h a ve WX00i ¡ BX00i = ¡ 1 , b y L e m m a 2 .) .

L e t X1; X2; : : : ; Xk b e p a r t s o f t h e ¯ r s t g r o u p ; X
0
1; X

0
2; : : : ; X

0
m b e p a r t s o f t h e s e c o n d

g r o u p ; X001 ; X
00
2 ; : : : ; X

00
t b e p a r t s o f t h e t h ir d g r o u p . W it h o u t lo s s o f g e n e r a lit y, we m a y

a s s u m e t h a t m > t. Co n s id e r t wo c a s e s .



1 0 On Locally-Balanced 2-Partitions of Complete Multipartite Graphs

Ca s e 1 : t = 0 .
Cle a r ly, m ¸ 3 . L e t u s c o n s id e r a ve r t e x v 2 X01. B y 1 a n d 2 , we h a ve

# ( v ) =
X

Y;Y 6=X01
( WY ¡ BY ) =

kX

i=1

( WXi ¡ BXi ) +
mX

i=2

( WX0
i
¡ BX0

i
) = m ¡ 1 ¸ 2 ;

wh ic h is a c o n t r a d ic t io n .
Ca s e 2 : t > 0 .

L e t u s c o n s id e r a ve r t e x v 2 X001 . B y 1 , 2 a n d 3 , we h a ve

# ( v ) =
X

Y;Y 6=X00
1

( WY ¡ BY ) =
kX

i=1

( WXi ¡ BXi ) +
mX

i=1

( WX0i ¡ BX0i ) +

tX

i=2

( WX00i ¡ BX00i ) = m ¡ ( t ¡ 1 ) = ( m ¡ t) + 1 ¸ 2 ;

wh ic h is a c o n t r a d ic t io n .
N o w we s h o w t h a t if t h e n u m b e r o f o d d p a r t s is e ve n o r o n e , t h e n Kr1;r2:::;rn h a s a

lo c a lly-b a la n c e d 2 -p a r t it io n wit h a n o p e n n e ig h b o r h o o d .
Fir s t we c o lo r e ve n p a r t s u n ifo r m ly.
N e xt we c o n s id e r t wo c a s e s .
Ca s e A ) Th e n u m b e r o f o d d p a r t s is 2 l. Fir s t l o d d p a r t s we c o lo r a s fo llo ws : if X is

s u c h a p a r t wit h 2 p + 1 ( p ¸ 0 ) ve r t ic e s , t h e n a n y p ve r t ic e s g e t t h e c o lo r B lack a n d t h e
r e s t ve r t ic e s g e t t h e c o lo r White. N e xt l o d d p a r t s we c o lo r s im ila r ly b y t a kin g t h e c o lo r
White in s t e a d o f B lack, a n d vic e ve r s a .

Ca s e B ) X is t h e o n ly o d d p a r t wit h 2 p + 1 ( p ¸ 0 ) ve r t ic e s .
In t h is c a s e we c o lo r a n y p ve r t ic e s o f X wit h t h e c o lo r B lack a n d t h e r e s t ve r t ic e s wit h t h e
c o lo r White.

It is e a s y t o s e e t h a t t h e a b o ve -m e n t io n e d 2 -p a r t it io n is a lo c a lly-b a la n c e d 2 -p a r t it io n o f
Kr1;r2:::;rn wit h a n o p e n n e ig h b o r h o o d .

T heor em 2. If m1 = 0 , then the graph Kr1;r2:::;rn has a locally-balanced 2-partition with
a closed neighborhood if and only if it has no odd part.

P r oof. L e t ' b e a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d n e ig h b o r h o o d o f Kr1;r2:::;rn .
S u p p o s e , t o t h e c o n t r a r y, t h a t t h e r e e xis t s a n o d d p a r t X. S in c e m1 = 0 , we h a ve jXj ¸ 3 .
W it h o u t lo s s o f g e n e r a lit y, we m a y a s s u m e t h a t WX > BX . W e c o n s id e r t wo c a s e s .

Ca s e 1 : BX = 0 .
Co n s id e r a ve r t e x v 2 X. Cle a r ly, '( v ) = White. Th is im p lie s t h a t

# [v] = W ¡ B ¡ WX + BX + 1 :

S in c e ' is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d n e ig h b o r h o o d o f Kr1;r2:::;rn , we h a ve

¡ 1 · W ¡ B ¡ WX + BX + 1 · 1 :

Th is im p lie s t h a t



A. Gharibyan and P. Petrosyan 1 1

W ¡ B ¸ WX ¡ 2 > 0 .

Ca s e 2 : BX > 0 .
Co n s id e r a ve r t e x v 2 X wit h '( v ) = B lack. Th is im p lie s t h a t

# [v] = W ¡ B ¡ WX + BX ¡ 1 .

S in c e ' is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d n e ig h b o r h o o d o f Kr1;r2:::;rn , we h a ve

¡1 · W ¡ B ¡ WX + BX ¡ 1 · 1 .

Th is im p lie s t h a t W ¡ B ¸ WX ¡ BX > 0 .
In a n y c a s e we o b t a in

W ¡ B > 0 : ( 5 )

Fir s t we c o n s id e r t h e c a s e wh e n fo r a n y p a r t Y , WY ¸ BY . L e t u s c o n s id e r a ve r t e x v 2 X0
( X0 6= X ) wit h '( v ) = White. Th is im p lie s t h a t

# [v] =
X

Y;Y 6=X0
( WY ¡ BY ) + 1 =

WX ¡ BX +
X

Y;Y 6=X;X0
( WY ¡ BY ) + 1 ¸ 2 ;

wh ic h is a c o n t r a d ic t io n .

S o , we m a y a s s u m e t h a t t h e r e e xis t s a p a r t X0 s u c h t h a t WX0 < BX0.
If WX0 = 0 , t h e n we c o n s id e r a ve r t e x v 2 X0. Cle a r ly, '( v ) = B lack. Fr o m t h is a n d

t a kin g in t o a c c o u n t t h a t ' is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d n e ig h b o r h o o d o f
Kr1;r2:::;rn , we h a ve

¡ 1 · W ¡ B ¡ WX0 + BX0 ¡ 1 · 1 :

H e n c e , W ¡ B · 2 ¡ BX0 · 0 , wh ic h c o n t r a d ic t s ( 5 ) .
If WX0 > 0 , t h e n we c o n s id e r a ve r t e x v 2 X0 wit h '( v ) = White. Fr o m t h is a n d t a kin g

in t o a c c o u n t t h a t ' is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d n e ig h b o r h o o d o f Kr1;r2:::;rn ,
we h a ve

¡1 · W ¡ B ¡ WX0 + BX0 + 1 · 1 :

H e n c e , W ¡ B · WX0 ¡ BX0 < 0 , wh ic h c o n t r a d ic t s ( 5 ) .
L e t Kr1;r2:::;rn b e a c o m p le t e n-p a r t it e g r a p h wit h o u t a n o d d p a r t . In t h is c a s e we c o lo r

e a c h p a r t u n ifo r m ly.

Lemma 3. If m1 > 0 and Kr1;r2:::;rn has a locally-balanced 2-partition with a closed neigh-
borhood, then jW ¡ Bj · 1 .



1 2 On Locally-Balanced 2-Partitions of Complete Multipartite Graphs

P r oof. L e t ' b e a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d n e ig h b o r h o o d o f Kr1;r2:::;rn .
Co n s id e r a ve r t e x v o f t h e p a r t X wit h jXj = 1 . S in c e ' is a lo c a lly-b a la n c e d 2 -p a r t it io n
wit h a c lo s e d n e ig h b o r h o o d o f Kr1;r2:::;rn , we h a ve # [v] = W ¡ B, a n d h e n c e

¡1 · W ¡ B · 1 :

Remar k 1. Clearly, L emma 3. implies that if jV ( Kr1;r2:::;rn ) j is even, then W = B,
and if jV ( Kr1;r2:::;rn ) j is odd, then jW ¡ Bj = § 1 (in fact, by L emma 1., we may assume that
W ¡ B = 1 ).

T heor em 3. If m1 > 0 and jV ( Kr1;r2:::;rn ) j is even, then Kr1;r2:::;rn has a locally-balanced
2-partition with a closed neighborhood if and only if it has no odd part X with at least three
vertices.

P r oof. L e t ' b e a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d n e ig h b o r h o o d o f Kr1;r2:::;rn .
S u p p o s e t h a t t h e r e e xis t s a n o d d p a r t X wit h a t le a s t t h r e e ve r t ic e s . W e m a y a s s u m e t h a t
WX > BX . W e c o n s id e r t wo c a s e s .

Ca s e 1 : BX = 0 .
Co n s id e r a ve r t e x v 2 X. Cle a r ly, '( v ) = White. Th is im p lie s t h a t

# [v] = W ¡ B ¡ WX + BX + 1 :

B y R e m a r k 1 , we g e t # [v] = 1 ¡ WX · ¡ 2 , wh ic h is a c o n t r a d ic t io n .
Ca s e 2 : BX > 0 .

Co n s id e r a ve r t e x v 2 X wit h '( v ) = B lack. Th is im p lie s t h a t

# [v] = W ¡ B ¡ WX + BX ¡ 1 :

B y R e m a r k 1 a n d t a kin g in t o a c c o u n t t h a t WX > BX , we o b t a in

# [v] = BX ¡ WX ¡ 1 · 2 ;

wh ic h is a c o n t r a d ic t io n .
N o w le t Kr1;r2:::;rn b e a c o m p le t e n-p a r t it e g r a p h wit h m1 > 0 o d d p a r t s . Cle a r ly, m1 is

e ve n .
E a c h e ve n p a r t we c o lo r u n ifo r m ly. Th e n we c o lo r m1

2
o d d p a r t s wit h t h e c o lo r B lack

a n d t h e o t h e r m1
2

o d d p a r t s wit h t h e c o lo r White.
It is e a s y t o s e e t h a t t h is 2 -p a r t it io n is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d n e ig h -

b o r h o o d o f Kr1;r2:::;rn .

T heor em 4. If the graph Kr1;r2:::;rn has an odd number of vertices, m1 > 0 and there
exists a part X such that jXj = 2 + 2 k (k 2 N ) , then Kr1;r2:::;rn has no locally-balanced
2 -partition with a closed neighborhood.

P r oof. S u p p o s e t h a t ' is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d n e ig h b o r h o o d o f
Kr1;r2:::;rn . B y R e m a r k 1 a n d L e m m a 1 , we g e t

W ¡ B = 1 :



A. Gharibyan and P. Petrosyan 1 3

L e t u s c o n s id e r fo u r c a s e s .
Ca s e 1 : BX = 0 :

L e t u s c o n s id e r a ve r t e x v 2 X. S in c e ' is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d
n e ig h b o r h o o d o f Kr1;r2:::;rn , we h a ve

# [v] = W ¡ B ¡ WX + BX + 1 = 2 ¡ WX · ¡2 ;

wh ic h is a c o n t r a d ic t io n .
Ca s e 2 : WX = 0 :

L e t u s c o n s id e r a ve r t e x v 2 X. S in c e ' is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d
n e ig h b o r h o o d o f Kr1;r2:::;rn , we h a ve

# [v] = W ¡ B ¡ WX + BX ¡ 1 = BX ¸ 4 ;

wh ic h is a c o n t r a d ic t io n .
Ca s e 3 : WX > BX > 0 :

L e t u s c o n s id e r a ve r t e x v 2 X wit h '( v ) = B lack. S in c e ' is a lo c a lly-b a la n c e d 2 -p a r t it io n
wit h a c lo s e d n e ig h b o r h o o d o f Kr1;r2:::;rn , we h a ve

# [v] = W ¡ B ¡ WX + BX ¡ 1 = BX ¡ WX · ¡ 2 ;

wh ic h is a c o n t r a d ic t io n .
Ca s e 4 : 0 < WX · BX .

L e t u s c o n s id e r a ve r t e x v 2 X wit h '( v ) = White. S in c e ' is a lo c a lly-b a la n c e d 2 -p a r t it io n
wit h a c lo s e d n e ig h b o r h o o d o f Kr1;r2:::;rn , we h a ve

# [v] = W ¡ B ¡ WX + BX + 1 = 2 + BX ¡ WX ¸ 2 ;

wh ic h is a c o n t r a d ic t io n .

T heor em 5. If the graph Kr1;r2:::;rn has an odd number of vertices, m1 > 0 and each
part X of the graph has either two vertices or an odd number of vertices, then Kr1;r2:::;rn has
a locally-balanced 2 -partition with a closed neighborhood if and only if m1 ¸ 2 m2 + m¸3 ¡ 1 .

P r oof. S u p p o s e t h a t ' is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d n e ig h b o r h o o d o f
Kr1;r2:::;rn . B y R e m a r k 1 a n d L e m m a 1 , we h a ve

W ¡ B = 1 : ( 6 )

L e t u s c o n s id e r a p a r t X wit h o n ly t wo ve r t ic e s u a n d v.
If '( v ) = White a n d '( u ) = B lack, t h e n s in c e ' is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h

a c lo s e d n e ig h b o r h o o d o f Kr1;r2:::;rn , we h a ve

# [v] = W ¡ B ¡ WX + BX + 1 = 2 ;

a c o n t r a d ic t io n .
S im ila r ly, if '( v ) = B lack a n d '( u ) = White, t h e n we c o n s id e r t h e ve r t e x u.
If '( v ) = '( u ) = B lack, t h e n s in c e ' is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d

n e ig h b o r h o o d o f Kr1;r2:::;rn , we h a ve

# [v] = W ¡ B ¡ WX + BX ¡ 1 = 2 ;



1 4 On Locally-Balanced 2-Partitions of Complete Multipartite Graphs

a c o n t r a d ic t io n .
Th is im p lie s t h a t '( v ) = '( u ) = White.
L e t X b e a n o d d p a r t wit h a t le a s t t h r e e ve r t ic e s .
If WX = 0 , t h e n b y c o n s id e r in g a ve r t e x v 2 X a n d t a kin g in t o a c c o u n t t h a t ' is a

lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d n e ig h b o r h o o d o f Kr1;r2:::;rn , we o b t a in

# [v] = W ¡ B ¡ WX + BX ¡ 1 = BX ¸ 3 ;

a c o n t r a d ic t io n .
If 0 < WX < BX , t h e n b y c o n s id e r in g a ve r t e x v 2 X wit h '( v ) = White a n d t a kin g

in t o a c c o u n t t h a t ' is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d n e ig h b o r h o o d o f Kr1;r2:::;rn ,
we o b t a in

# [v] = W ¡ B ¡ WX + BX + 1 = 2 + BX ¡ WX ¸ 3 ;

a c o n t r a d ic t io n . Th is s h o ws t h a t

WX > BX : ( 7 )

L e t u s c o n s id e r t wo c a s e s .
Ca s e 1 : jXj = 3 .

B y ( 7 ) , we h a ve t h a t t h e r e a r e t wo p o s s ib le c a s e s : a ll ve r t ic e s o f X a r e White o r t wo o f
t h e m a r e White a n d t h e la s t o n e is B lack.

If WX = 3 a n d BX = 0 , t h e n fo r a n y v 2 X, we h a ve

# [v] = W ¡ B ¡ WX + BX + 1 = ¡1 :

Th is im p lie s t h a t fo r a n y v 2 X, ¡1 · # [v] · 1 :
If WX = 2 a n d BX = 1 , t h e n fo r a n y v 2 X, we h a ve e it h e r # [v] = W ¡B¡WX +BX +1 =

1 ( if '( v ) = White ) o r # [v] = W ¡ B ¡ WX + BX ¡ 1 = ¡ 1 ( if '( v ) = B lack ) .
Th is im p lie s t h a t fo r a n y v 2 X, ¡1 · # [v] · 1 :

Ca s e 2 : jXj ¸ 5 .
B y ( 7 ) , we h a ve WX ¡ BX ¸ 1 .

L e t u s s h o w t h a t WX ¡ BX = 1 .
S u p p o s e , t o t h e c o n t r a r y, t h a t WX ¡ BX ¸ 3 .

If BX = 0 , t h e n fo r a n y v 2 X, we h a ve

# [v] = W ¡ B ¡ WX + BX + 1 · ¡ 3 ;

wh ic h is a c o n t r a d ic t io n .
If WX > BX > 0 . Fo r a n y v 2 X wit h '( v ) = B lack, we h a ve

# [v] = W ¡ B ¡ WX + BX ¡ 1 · ¡3 ;

wh ic h is a c o n t r a d ic t io n .
Th is s h o ws t h a t WX ¡ BX = 1 .

S o , we o b t a in t h a t if X is a p a r t wit h a t le a s t t wo ve r t ic e s , t h e n we h a ve t h e fo llo win g t h r e e
p o s s ib le c a s e s :

a ) If X is a n o d d p a r t wit h t h r e e ve r t ic e s , t h e n

e it h e r WX ¡ BX = 1 o r WX ¡ BX = 3 ; ( 8 )



A. Gharibyan and P. Petrosyan 1 5

b ) If X is a n o d d p a r t wit h a t le a s t ¯ ve ve r t ic e s , t h e n

WX ¡ BX = 1 ; ( 9 )

c ) If X h a s t wo ve r t ic e s , t h e n

WX ¡ BX = 2 : ( 1 0 )

B y ( 6 ) , ( 8 ) ,( 9 ) ,( 1 0 ) , we g e t

m1 =
X

X;jXj=1
( BX + WX ) ¸

X

X;jXj=1
( BX ¡ WX ) = B ¡ W +

X

X;jXj=2
( WX ¡ BX ) +

X

X;WX ¡BX =1
( WX ¡BX ) +

X

X;WX ¡BX =3
( WX ¡BX ) = B¡W +2 jfX: X is a p a r t wit h jXj = 2 gj+

jfX: X is a p a r t wit h WX ¡ BX = 1 gj + 3 jfX: X is a p a r t wit h WX ¡ BX = 3 gj ¸

B ¡ W + 2 jfX: X is a p a r t wit h jXj = 2 gj + jfX: X is a p a r t wit h WX ¡ BX = 1 gj+

jfX: X is a p a r t wit h WX ¡ BX = 3 gj = B ¡ W + 2 jfX: X is a p a r t wit h jXj = 2 gj+

jfX: X is a n o d d p a r t wit h a t le a s t t h r e e ve r t ic e s gj = ¡ 1 + 2 m2 + m¸3:

N o w le t m1 ¸ 2 m2 + m¸3 ¡ 1 . W e c o n s t r u c t a 2 -p a r t it io n o f Kr1;r2:::;rn a s fo llo ws :
1 ) E a c h ve r t e x v 2 X ( jXj = 2 ) , we c o lo r wit h t h e c o lo r White;
2 ) Fo r a n y o d d p a r t X wit h jXj = 2 p + 1 ( p 2 N ) ve r t ic e s , we c o lo r p + 1 ve r t ic e s o f X

wit h t h e c o lo r White, a n d t h e r e s t p ve r t ic e s we c o lo r wit h t h e c o lo r B lack;

3 ) W e t a ke a n y ( 2 m2 + m¸3 ¡ 1 ) p a r t s wit h o n ly o n e ve r t e x o f t h e g r a p h a n d we c o lo r
e a c h ve r t e x in t h e s e p a r t s wit h t h e c o lo r B lack. S in c e jV ( Kr1;r2:::;rn ) j is o d d a n d m1 ¸
2 m2 + m¸3 ¡ 1 , we h a ve t h a t m1 ¡ ( 2 m2 + m¸3 ¡ 1 ) is e ve n a n d n o n -n e g a t ive . Th e ve r t ic e s
o f t h e r e m a in in g m1 ¡ ( 2 m2 + m¸3 ¡ 1 ) p a r t s we c o lo r u n ifo r m ly.

It is n o t d i± c u lt t o s e e t h a t t h is 2 -p a r t it io n is a lo c a lly-b a la n c e d 2 -p a r t it io n wit h a c lo s e d
n e ig h b o r h o o d o f Kr1;r2:::;rn .



1 6 On Locally-Balanced 2-Partitions of Complete Multipartite Graphs

Refer ences

[1 ] C. B e r g e , Gr a p h s a n d H yp e r g r a p h s , E ls e vie r S c ie n c e L t d , 1 9 8 5 .

[2 ] S .V . B a likya n , \ On e xis t e n c e o f c e r t a in lo c a lly-b a la n c e d 2 -p a r t it io n o f a t r e e " , M athe-
matical P roblems of Computer Science, Vol. 30, p p . 2 5 -3 0 , 2 0 0 8 .

[3 ] S .V . B a likya n a n d R . R . K a m a lia n , \ On e xis t e n c e o f 2 -p a r t it io n o f a t r e e , wh ic h o b e ys
t h e g ive n p r io r it y" , M athematical P roblems of Computer Science, Vol. 30, p p . 3 1 -3 5 ,
2 0 0 8 .

[4 ] S .V . B a likya n a n d R . R . K a m a lia n , \ N e c e s s a r y a n d s u ± c ie n t c o n d it io n fo r e xis t e n c e o f
lo c a lly-b a la n c e d 2 -p a r t it io n o f a t r e e u n d e r t h e e xt e n d e d d e ¯ n it io n o f a n e ig h b o u r h o o d
o f a ve r t e x" , M athematical P roblems of Computer Science, vo l. 3 1 , p p . 1 1 6 -1 2 1 , 2 0 0 8 .

[5 ] A . H . Gh a r ib ya n a n d P .A . P e t r o s ya n , \ L o c a lly-b a la n c e d 2 -p a r t it io n s o f c o m p le t e m u l-
t ip a r t it e g r a p h s " , 6th P olish Combinatorial Conference, B e d le wo , P o la n d , p . 1 9 , 2 0 1 6 .

[6 ] A .H . Gh a r ib ya n a n d P .A . P e t r o s ya n , \ On lo c a lly-b a la n c e d 2 -p a r t it io n s o f s o m e g r a p h s " ,
P roceedings of the CSIT Conference, Y e r e va n , p p . 1 9 6 -1 9 7 , 2 0 1 7 .

[7 ] A . H a jn a l a n d E . S z e m e r e d i, \ P r o o f o f a c o n je c t u r e o f P . E r d }o s " , Combinatorial theory
and its applications, II (P roc. Colloq., B alatonfred, 1969), N o r t h -H o lla n d , p p . 6 0 1 -6 2 3 ,
1 9 7 0 .

[8 ] G. Ch a r t r a n d a n d P . Zh a n g , Chromatic Graph Theory, D is c r e t e Ma t h e m a t ic s a n d It s
A p p lic a t io n s , CR C P r e s s , 2 0 0 9 .

[9 ] W . Me ye r , \ E qu it a b le c o lo r in g " , American M athematical M onthly, vo l. 8 0 , n o . 8 , p p .
9 2 0 -9 2 2 , 1 9 7 3 .

[1 0 ] A .V . K o s t o c h ka , \ E qu it a b le c o lo r in g s o f o u t e r p la n a r g r a p h s " , D iscrete M athematics
vo l. 2 5 8 , p p . 3 7 3 -3 7 7 , 2 0 0 2 .

[1 1 ] J. K r a t o c h vil, \ Co m p le xit y o f h yp e r g r a p h c o lo r in g a n d S e id e l's s wit c h in g " , Graph The-
oretic Concepts in Computer Science, 29th International W orkshop, W G 2003, E lspeet,
The Netherlands, R evised P apers, vo l. 2 8 8 0 , p p . 2 9 7 -3 0 8 , Ju n e 1 9 -2 1 , 2 0 0 3 .

[1 2 ] S . V . B a likya n a n d R . R . K a m a lia n , \ On N P -c o m p le t e n e s s o f t h e p r o b le m o f e xis t e n c e
o f lo c a lly-b a la n c e d 2 -p a r t it io n fo r b ip a r t it e g r a p h s G wit h ¢ ( G ) = 3 " , D oklady NAN
R A, vo l. 1 0 5 , n o . 1 , p p . 2 1 -2 7 , 2 0 0 5 .

[1 3 ] S .V . B a likya n a n d R .R . K a m a lia n , \ On NP -c o m p le t e n e s s o f t h e p r o b le m o f e xis t e n c e o f
lo c a lly-b a la n c e d 2 -p a r t it io n fo r b ip a r t it e g r a p h s G wit h ¢ ( G) = 4 u n d e r t h e e xt e n d e d
d e ¯ n it io n o f t h e n e ig h b o u r h o o d o f a ve r t e x" , D oklady NAN R A, vo l. 1 0 6 , n o . 3 , p p .
2 1 8 -2 2 6 , 2 0 0 6 .

[1 4 ] D . d e W e r r a , \ On g o o d a n d e qu it a b le c o lo r in g s " , In Cahiers du C.E .R .O., vo l. 1 7 , p p .
4 1 7 -4 2 6 , 1 9 7 5 .

[1 5 ] 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, 2 0 0 1 .

Submitted 02.10.2017, accepted 26.01.2018.



A. Gharibyan and P. Petrosyan 1 7

ÈñÇí µ³½Ù³ÏáÕÙ³ÝÇ ·ñ³ýÝ»ñÇ ÉáϳÉ-ѳí³ë³ñ³Ïßéí³Í
2-ïñáÑáõÙÝ»ñÇ Ù³ëÇÝ

². Ô³ñÇµÛ³Ý ¨ ä. ä»ïñáëÛ³Ý

²Ù÷á÷áõÙ

f : V ( G) ! fWhite; B lackg ýáõÝÏóÇ³Ý ÏáãíáõÙ ¿ G ·ñ³ýÇ 2-ïñáÑáõÙ: G ·ñ³ýÇ
f 2-ïñáÑáõÙÁ ÏáãíáõÙ ¿ ÉáϳÉ-ѳí³ë³ñ³Ïßéí³Í 2-ïñáÑáõÙ µ³ó ßñç³Ï³Ûùáí, »Ã»
Ï³Ù³Û³Ï³Ý v 2 V ( G ) ·³·³ÃÇ Ñ³Ù³ñ ï»ÕÇ áõÝÇ

jjfu 2 NG ( v ) : f ( u ) = Whitegj ¡ jfu 2 NG ( v ) : f ( u) = B lackgjj · 1 ;

áñï»Õ NG ( v ) = fu 2 V ( G ) : uv 2 E ( G ) g: G ·ñ³ýÇ f 0 2-ïñáÑáõÙÁ ÏáãíáõÙ ¿ ÉáϳÉ-
ѳí³ë³ñ³Ïßéí³Í ïñáÑáõÙ ÷³Ï ßñç³Ï³Ûùáí, »Ã» Ï³Ù³Û³Ï³Ý v 2 V ( G) ·³·³ÃÇ
ѳٳñ ï»ÕÇ áõÝÇ

jjfu 2 NG[v]: f 0 ( u ) = Whitegj ¡ jfu 2 NG[v]: f 0 ( u) = B lackgjj · 1 ;

áñï»Õ NG[v] = NG ( v ) [ fvg: ²Ûë ³ß˳ï³ÝùáõÙ ïñíáõÙ »Ý ÉñÇí µ³½Ù³ÏáÕÙ³ÝÇ
·ñ³ýÝ»ñÇ ÉáϳÉ-ѳí³ë³ñ³Ïßéí³Í ïñáÑáõÙÝ»ñÇ ·áÛáõÃÛ³Ý ³ÝÑñ³Å»ßï ¨ µ³í³ñ³ñ
å³ÛÙ³ÝÝ»ñ:

Î ëîêàëüíî-ñáàëàíñèðîâàííûx 2-ðàçáèåíèÿx
ïîëíûx ìíîãîäîëüíûx ãðàôîâ

À. Ãàðèáÿí è Ï. Ïåòðîñÿí

Àííîòàöèÿ

2-ðàçáèåíèåì ãðàôà G íàçûâàåòñÿ ôóíêöèÿ f : V ( G) ! fWhite; B lackg.
2-ðàçáèåíèå f ãðàôà G íàçûâàåòñÿ ëîêàëüíî-ñáàëàíñèðîâàííûì ñ îòêðûòîé
îêðåñòíîñòüþ, åñëè äëÿ ëþáîé âåðøèíû v 2 V ( G)

jjfu 2 NG ( v ) : f ( u ) = Whitegj ¡ jfu 2 NG ( v ) : f ( u) = B lackgjj · 1 ;

ãäå NG ( v ) = fu 2 V ( G ) : uv 2 E ( G) g. 2-ðàçáèåíèå f 0 ãðàôà G íàçûâàåòñÿ ëîêàëüíî-
ñáàëàíñèðîâàííûì ñ çàêðûòîé îêðåñòíîñòüþ, åñëè äëÿ ëþáîé âåðøèíû v 2 V ( G )

jjfu 2 NG[v]: f 0 ( u ) = Whitegj ¡ jfu 2 NG[v]: f 0 ( u) = B lackgjj · 1 ;

ãäå NG[v] = NG ( v ) [ fvg. Â íàñòîÿùåé ðàáîòå äàþòñÿ íåîáõîäèìûå è
äîñòàòî÷íûå óñëîâèÿ ñóùåñòâîâàíèÿ ëîêàëüíî-ñáàëàíñèðîâàííûõ 2-ðàçáèåíèé
ïîëíûõ ìíîãîäîëüíûõ ãðàôîâ.