D:\FINAL_TEX\...\article.DVI


Mathematical Problems of Computer Science 42, 28{42, 2014.

I nter val T otal Color ings of Complete M ultipar tite

Gr aphs and H yper cubes

P e t r o s A . P e t r o s ya n 1; 2 a n d N e r s e s A . K h a c h a t r ya n 2

1Institute for Informatics and Automation Problems of NAS RA
2Department of Informatics and Applied Mathematics, YSU

e-mail: pet petros@ipia.sci.am, xachnerses@gmail.com

Abstract

A total coloring of a graph G is a coloring of its vertices and edges such that no
adjacent vertices, edges, and no incident vertices and edges obtain the same color. An
interval total t-coloring of a graph G is a total coloring of G with colors 1; : : : ; t such
that all colors are used, 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 all complete multipartite graphs with the same number of
vertices in each part are interval total colorable. Moreover, we also give some bounds
for the minimum and the maximum span in interval total colorings of these graphs.
Next, we investigate interval total colorings of hypercubes Qn. In particular, we prove
that Qn (n ¸ 3) has an interval total t-coloring if and only if n + 1 · t · (n+1)(n+2)2 .

Keywords: Total coloring, Interval total coloring, Interval coloring, Complete
multipartite graph, Hypercube.

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 p a p e r 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 G, r e s p e c t ive ly. L e t
V E ( G ) d e n o t e t h e s e t V ( G ) [ E ( G ) . Th e d e g r e e o f a ve r t e x v in G is d e n o t e d b y dG ( v ) , t h e
m a xim u m d e g r e e o f ve r t ic e s in G b y ¢ ( G) a n d t h e t o t a l c h r o m a t ic n u m b e r o f G b y Â00 ( G) .
Fo r S µ V ( G) , le t G[S] d e n o t e t h e s u b g r a p h o f G in d u c e d b y S, t h a t is , V ( G[S]) = S a n d
E ( G[S]) c o n s is t s o f t h o s e e d g e s o f E ( G ) fo r wh ic h b o t h e n d s a r e in S. Fo r F µ E ( G ) , t h e
s u b g r a p h o b t a in e d b y d e le t in g t h e e d g e s o f F fr o m G is d e n o t e d b y G ¡ F . 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 [1 , 2 0 , 2 1 ].

L e t bac d e n o t e t h e la r g e s t in t e g e r le s s t h a n o r e qu a l t o a. Fo r t wo p o s it ive in t e g e r s a a n d
b wit h a · b, t h e s e t fa; : : : ; bg is d e n o t e d b y [a; b] a n d c a lle d a n in t e r va l. Fo r a n in t e r va l
[a; b] a n d a n o n n e g a t ive n u m b e r p, t h e n o t a t io n [a; b] © p m e a n s [a + p; b + p].

A p r o p e r e d g e -c o lo r in g o f a g r a p h G is a c o lo r in g o f t h e e d g e s o f G s u c h t h a t n o t wo
a d ja c e n t e d g e s r e c e ive t h e s a m e c o lo r . If ® is a p r o p e r e d g e -c o lo r in g o f G a n d v 2 V ( G ) , t h e n
S ( v; ® ) d e n o t e s t h e s e t o f c o lo r s a p p e a r in g o n e d g e s in c id e n t t o v. A p r o p e r e d g e -c o lo r in g
o f a g r a p h G is a n in t e r va l t-c o lo r in g [2 ] if a ll c o lo r s a r e u s e d , a n d fo r a n y v 2 V ( G ) , t h e
s e t S ( v; ®) is a n in t e r va l o f in t e g e r s . A g r a p h G is in t e r va l c o lo r a b le if it h a s a n in t e r va l

2 8



P. Petrosyan and N. Khachatryan 2 9

t-c o lo r in g fo r s o m e p o s it ive in t e g e r t. Th e s e t o f a ll in t e r va l c o lo r a b le g r a p h s is d e n o t e d b y
N . Fo r a g r a p h G 2 N , t h e le a s t ( t h e m in im u m s p a n ) a n d t h e g r e a t e s t ( t h e m a xim u m
s p a n ) va lu e s o f t fo r wh ic h G h a s a n in t e r va l t-c o lo r in g a r e d e n o t e d b y w ( G) a n d W ( G) ,
r e s p e c t ive ly. A t o t a l c o lo r in g o f a g r a p h G is a c o lo r in g o f it s ve r t ic e s a n d e d g e s s u c h t h a t
n o a d ja c e n t ve r t ic e s , e d g e s , a n d n o in c id e n t ve r t ic e s a n d e d g e s o b t a in t h e s a m e c o lo r . If ®
is a t o t a l c o lo r in g o f a g r a p h G, t h e n S [v; ®] d e n o t e s t h e s e t S ( v; ® ) [ f®( v ) g.

A g r a p h Kn1;:::;nr is a c o m p le t e r-p a r t it e ( r ¸ 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 r in d e p e n d e n t s e t s V1; : : : ; Vr wit h jVij = ni ( 1 · i · r ) s u c h t h a t e a c h ve r t e x in Vi 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 Vj fo r 1 · i < j · r. A c o m p le t e r-p a r t it e g r a p h Kn;:::;n
is a c o m p le t e b a la n c e d r-p a r t it e g r a p h if jV1j = jV2j = ¢ ¢ ¢ = jVrj = n. Cle a r ly, if Kn;:::;n is a
c o m p le t e b a la n c e d r-p a r t it e g r a p h wit h n ve r t ic e s in e a c h p a r t , t h e n ¢ ( Kn;:::;n ) = ( r ¡ 1 ) n.
N o t e t h a t t h e c o m p le t e g r a p h Kn a n d t h e c o m p le t e b a la n c e d b ip a r t it e g r a p h Kn;n a r e s p e c ia l
c a s e s o f t h e c o m p le t e b a la n c e d r-p a r t it e g r a p h . Th e t o t a l c h r o m a t ic n u m b e r s o f c o m p le t e
a n d c o m p le t e b ip a r t it e g r a p h s we r e d e t e r m in e d b y B e h z a d , Ch a r t r a n d a n d Co o p e r [3 ]. Th e y
p r o ve d t h e fo llo win g t h e o r e m s :

T heor em 1: F or any n 2 N , we have

Â00 ( Kn ) =

(
n, if n is odd,
n + 1 , if n is even.

T heor em 2: F or any m; n 2 N , we have

Â00 ( Km;n ) =

(
m a xfm; ng + 1 , if m 6= n,
n + 2 , if m = n.

A m o r e g e n e r a l r e s u lt o n t o t a l c h r o m a t ic n u m b e r s o f c o m p le t e b a la n c e d m u lt ip a r t it e
g r a p h s wa s o b t a in e d b y B e r m o n d [4 ].

T heor em 3: F or any complete balanced r-partite graph Kn;:::;n (r ¸ 2 ; n 2 N ), we have

Â00 ( Kn;:::;n ) =

(
( r ¡ 1 ) n + 2 , if r = 2 or r is even and n is odd,
( r ¡ 1 ) n + 1 , otherwise.

A n in t e r va l t o t a l t-c o lo r in g o f a g r a p h G is a t o t a l c o lo r in g ® o f G wit h c o lo r s 1 ; : : : ; t
s u c h t h a t a ll c o lo r s a r e u s e d , a n d fo r a n y v 2 V ( G ) , t h e s e t S [v; ®] is a n in t e r va l o f in t e g e r s .
A g r a p h G is in t e r va l t o t a l c o lo r a b le if it h a s a n in t e r va l t o t a l t-c o lo r in g fo r s o m e p o s it ive
in t e g e r t. Th e s e t o f a ll in t e r va l t o t a l c o lo r a b le g r a p h s is d e n o t e d b y T . Fo r a g r a p h G 2 T ,
t h e le a s t ( t h e m in im u m s p a n ) a n d t h e g r e a t e s t ( t h e m a xim u m s p a n ) va lu e s o f t fo r wh ic h G
h a s a n in t e r va l t o t a l t-c o lo r in g a r e d e n o t e d b y w¿ ( G) a n d W¿ ( G) , r e s p e c t ive ly. Cle a r ly,

Â00 ( G ) · w¿ ( G) · W¿ ( G) · jV ( G) j + jE ( G) j fo r e ve r y g r a p h G 2 T .
Th e c o n c e p t o f in t e r va l t o t a l c o lo r in g wa s in t r o d u c e d b y P e t r o s ya n [5 ]. In [5 , 6 ], t h e

a u t h o r p r o ve d t h a t if m + n + 2 ¡ g c d ( m; n) · t · m + n + 1 , t h e n t h e c o m p le t e b ip a r t it e
g r a p h Km;n h a s a n in t e r va l t o t a l t-c o lo r in g . L a t e r , P e t r o s ya n a n d To r o s ya n [1 8 ] o b t a in e d
t h e fo llo win g r e s u lt s :

T heor em 4: F or any m; n 2 N , we have

W¿ ( Km;n ) =

(
m + n + 1 , if m = n = 1 ,
m + n + 2 , otherwise.



3 0 Interval Total Colorings of Complete Multipartite Graphs and Hypercubes

T heor em 5: F or any n 2 N , we have

(1) Kn;n 2 T ,
(2) w¿ ( Kn;n ) = Â

00 ( Kn;n ) = n + 2 ,

(3) W¿ ( Kn;n ) =

(
2 n + 1 , if n = 1 ,
2 n + 2 , if n ¸ 2 ,

(4) if w¿ ( Kn;n ) · t · W¿ ( Kn;n ) , then Kn;n has an interval total t-coloring.

In [6 ], P e t r o s ya n in ve s t ig a t e d 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 g r a p h s a n d h yp e r c u b e s ,
wh e r e h e p r o ve d t h e fo llo win g t wo t h e o r e m s :

T heor em 6: F or any n 2 N , we have

(1) Kn 2 T ,

(2) w¿ ( Kn ) =

(
n, if n is odd,
3
2
n, if n is even,

(3) W¿ ( Kn ) = 2 n ¡ 1 .

T heor em 7: F or any n 2 N , we have

(1) Qn 2 T ,

(2) w¿ ( Qn ) = Â
00 ( Qn ) =

(
n + 2 , if n · 2 ,
n + 1 , if n ¸ 3 ,

(3) W¿ ( Qn ) ¸ (n+1)(n+2)2 ,
(4) if w¿ ( Qn ) · t · (n+1)(n+2)2 , then Qn has an interval total t-coloring.

L a t e r , P e t r o s ya n a n d To r o s ya n [1 8 ] s h o we d t h a t if w¿ ( Kn ) · t · W¿ ( Kn ) , t h e n t h e
c o m p le t e g r a p h Kn h a s a n in t e r va l t o t a l t-c o lo r in g . In [1 3 ], P e t r o s ya n a n d S h a s h ikya n
p r o ve d t h a t t r e e s h a ve a n in t e r va l t o t a l c o lo r in g . In [1 4 , 1 5 , 1 6 ], P e t r o s ya n a n d S h a s h ikya n
in ve s t ig a t e d in t e r va l t o t a l c o lo r in g s o f b ip a r t it e g r a p h s . In p a r t ic u la r , t h e y p r o ve d t h a t
r e g u la r b ip a r t it e g r a p h s , s u b c u b ic b ip a r t it e g r a p h s , d o u b ly c o n ve x b ip a r t it e g r a p h s , ( 2 ; b) -
b ir e g u la r b ip a r t it e g r a p h s a n d s o m e c la s s e s 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 4 h a ve
in t e r va l t o t a l c o lo r in g s . Th e y a ls o s h o we d t h a t t h e r e a r e b ip a r t it e g r a p h s t h a t h a ve n o
in t e r va l t o t a l c o lo r in g . Th e s m a lle s t kn o wn b ip a r t it e g r a p h wit h 2 6 ve r t ic e s a n d m a xim u m
d e g r e e 1 8 t h a t is n o t in t e r va l t o t a l c o lo r a b le wa s o b t a in e d b y S h a s h ikya n [1 9 ].

On e o f t h e le s s -in ve s t ig a t e d p r o b le m s r e la t e d t o in t e r va l t o t a l c o lo r in g s is a p r o b le m
o f d e t e r m in in g t h e e xa c t va lu e s o f t h e m in im u m a n d t h e m a xim u m s p a n in in t e r va l t o t a l
c o lo r in g s o f g r a p h s . Th e e xa c t va lu e s o f t h e s e p a r a m e t e r s a r e kn o wn o n ly fo r p a t h s , c yc le s ,
t r e e s [1 3 , 1 4 ], wh e e ls [1 0 ], c o m p le t e a n d c o m p le t e b a la n c e d b ip a r t it e g r a p h s [5 , 6 , 1 8 ]. In
s o m e p a p e r s [8 , 1 1 , 1 2 , 1 7 ] lo we r a n d u p p e r b o u n d s a r e fo u n d fo r t h e m in im u m a n d t h e
m a xim u m s p a n in 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 .

In t h is p a p e r we p r o ve t h a t a ll c o m p le t e b a la n c e d m u lt ip a r t it e g r a p h s a r e in t e r va l t o t a l
c o lo r a b le a n d we d e r ive s o m e b o u n d s fo r t h e m in im u m a n d t h e m a xim u m s p a n in in t e r va l
t o t a l c o lo r in g s o f t h e s e g r a p h s . N e xt , we in ve s t ig a t e in t e r va l t o t a l c o lo r in g s o f h yp e r c u b e s
Qn a n d we s h o w t h a t W¿ ( Qn ) =

(n+1)(n+2)
2

fo r a n y n 2 N .



P. Petrosyan and N. Khachatryan 3 1

2 . In t e r va l To t a l Co lo r in g s o f Co m p le t e Mu lt ip a r t it e Gr a p h s

W e ¯ r s t c o n s id e r 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 . It is kn o wn t h a t
Km;n 2 T a n d w¿ ( Km;n ) · m + n + 2 ¡ g c d ( m; n) fo r a n y m; n 2 N , b u t in g e n e r a l t h e e xa c t
va lu e o f w¿ ( Km;n ) is u n kn o wn . Ou r ¯ r s t r e s u lt g e n e r a liz e s t h e p o in t ( 2 ) o f Th e o r e m 5 .

T heor em 8: F or any n; l 2 N , we have w¿ ( Kn;n¢l ) = Â00 ( Kn;n¢l ) .

N o w we a s s u m e t h a t l ¸ 2 .
L e t V ( Kn;n¢l ) = fu1; : : : ; un; v1; : : : ; vn¢lg a n d E ( Kn;n¢l ) = fuivjj 1 · i · n; 1 · j · n¢lg.

A ls o , le t G = Kn;n¢l [fu1; : : : ; un; v1; : : : ; vng]. Cle a r ly, G is is o m o r p h ic t o t h e g r a p h Kn;n.
N o w we d e ¯ n e a n e d g e -c o lo r in g ® o f G a s fo llo ws : fo r 1 · i · n a n d 1 · j · n, le t

® ( uivj ) =

(
i + j ¡ 1 ( m o d n) , if i + j 6= n + 1 ,
n, if i + j = n + 1 .

It is e a s y t o s e e t h a t ® is a p r o p e r e d g e -c o lo r in g o f G a n d S ( ui; ®) = S ( vi; ® ) = [1 ; n] fo r
1 · i · n.

N e xt we c o n s t r u c t a n in t e r va l t o t a l ( n¢l +1 ) -c o lo r in g o f Kn;n¢l. B e fo r e we g ive t h e e xp lic it
d e ¯ n it io n o f t h e c o lo r in g , we n e e d t wo a u xilia r y fu n c t io n s . Fo r i 2 N , we d e ¯ n e a fu n c t io n
f1 ( i) a s fo llo ws : f1 ( i) = 1 + ( i ¡ 1 ) ( m o d n) . Fo r j 2 N , we d e ¯ n e a fu n c t io n f2 ( j ) a s
fo llo ws : f2 ( j ) =

j
j¡1
n

k
.

N o w we a r e a b le t o d e ¯ n e a t o t a l c o lo r in g ¯ o f Kn;n¢l.
Fo r 1 · i · n, le t

¯ ( ui ) = n ¢ l + 1 .

Fo r 1 · j · n ¢ l, le t

¯ ( vj ) =

(
n + 1 , if 1 · j · n,
n ¢ f2 ( j ) , if n + 1 · j · n ¢ l.

Fo r 1 · i · n a n d 1 · j · n ¢ l, le t

¯ ( uivj ) = ®
³
uf1(i)vf1(j)

´
+ n ¢ f2 ( j ) .

L e t u s p r o ve t h a t ¯ is a n in t e r va l t o t a l ( n ¢ l + 1 ) -c o lo r in g o f Kn;n¢l.
B y t h e d e ¯ n it io n o f ¯ a n d t a kin g in t o a c c o u n t t h a t S ( ui; ® ) = S ( vi; ®) = [1 ; n] fo r

1 · i · n, we h a ve

S[ui; ¯] = S ( ui; ¯ ) [ f¯ ( ui ) g =
³Sl

k=1 S
³
uf1(i); ®

´
© n( k ¡ 1 )

´
[ f¯ ( ui ) g =

= [1 ; n ¢ l] [ fn ¢ l + 1 g = [1 ; n ¢ l + 1 ] fo r 1 · i · n,
S[vj ; ¯] = S ( vj ; ® ) [ f¯ ( vj ) g = [1 ; n] [ fn + 1 g = [1 ; n + 1 ] fo r 1 · j · n, a n d

S[vj ; ¯] = S ( vj; ¯ ) [ f¯ ( vj ) g =
³
S

³
vf1(j); ®

´
© n ¢ f2 ( j )

´
[ f¯ ( vj ) g =

= [1 + n ¢ f2 ( j ) ; n + n ¢ f2 ( j ) ] [ fn ¢ f2 ( j ) g = [n ¢ f2 ( j ) ; n + n ¢ f2 ( j ) ] fo r n + 1 · j · n ¢ l.

P r oof: Fir s t o f a ll le t u s c o n s id e r t h e c a s e l = 1 . B y Th e o r e m 5 , we o b t a in w¿ ( Kn;n ) =
Â00 ( Kn;n ) = n + 2 fo r a n y n 2 N .



3 2 Interval Total Colorings of Complete Multipartite Graphs and Hypercubes

Th is s h o ws t h a t ¯ is a n in t e r va l t o t a l ( n¢l+1 ) -c o lo r in g o f Kn;n¢l. Th u s , w¿ ( Kn;n¢l ) · n¢l+1 .
On t h e o t h e r h a n d , b y Th e o r e m 2 , w¿ ( Kn;n¢l ) ¸ Â00 ( Kn;n¢l ) = n ¢ l + 1 fo r l ¸ 2 a n d h e n c e ,
w¿ ( Kn;n¢l ) = Â

00 ( Kn;n¢l ) .

N e xt , we s h o w t h a t t h e d i®e r e n c e b e t we e n w¿ ( Km;n ) a n d Â
00 ( Km;n ) fo r s o m e m a n d n

c a n b e a r b it r a r ily la r g e .

T heor em 9: F or any l 2 N , there exists a graph G such that G 2 T and w¿ ( G) ¡Â00 ( G ) ¸ l.

2 n + 1 .
B y Th e o r e m 4 , we h a ve Kn+l;2n 2 T . W e n o w s h o w t h a t w¿ ( Kn+l;2n ) ¸ 2 n + 1 + l.
S u p p o s e , t o t h e c o n t r a r y, t h a t Kn+l;2n h a s a n in t e r va l t o t a l t-c o lo r in g ®, wh e r e 2 n + 1 ·

t · 2 n + l.
L e t u s c o n s id e r S[v; ®] fo r a n y v 2 V ( Kn+l;2n ) . It is e a s y t o s e e t h a t [t ¡ n¡l; n + l + 1 ] µ

S[v; ®] fo r a n y v 2 V ( Kn+l;2n ) . S in c e t · 2 n + l, we h a ve [n; n + l + 1 ] µ S[v; ®] fo r a n y
v 2 V ( Kn+l;2n ) . Th is im p lie s t h a t fo r e a c h c 2 [n; n + l + 1 ], t h e r e a r e n ¡ l ve r t ic e s in
Y c o lo r e d b y c. On t h e o t h e r h a n d , s in c e jY j = 2 n, we h a ve 2 n ¸ ( l + 2 ) ( n ¡ l ) , wh ic h
c o n t r a d ic t s t h e e qu a lit y n = l + 3 .

Th is s h o ws t h a t w¿ ( Kn+l;2n ) ¸ 2 n+1 +l. W e t a ke G = Kn+l;2n. H e n c e , w¿ ( G) ¡Â00 ( G) ¸ l.

N o w we c o n s id e r 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 r-p a r t it e g r a p h s wit h n ve r t ic e s in
e a c h p a r t .

T heor em 10: If r = 2 or r is even and n is odd, then Kn;:::;n 2 T and

w¿ ( Kn;:::;n ) ·
³

3
2
r ¡ 2

´
n + 2 .

N o w we a s s u m e t h a t r is e ve n a n d n is o d d . Cle a r ly, fo r t h e p r o o f o f t h e t h e o r e m , it
s u ± c e s t o p r o ve t h a t Kn;:::;n h a s a n in t e r va l t o t a l

³³
3
2
r ¡ 2

´
n + 2

´
-c o lo r in g .

L e t V ( Kn;:::;n ) =
n
v

(i)
j j 1 · i · r; 1 · j · n

o
a n d

E ( Kn;:::;n ) =
n
v(i)p v

(j)
q j 1 · i < j · r; 1 · p · n; 1 · q · n

o
.

D e ¯ n e a t o t a l c o lo r in g ® o f Kn;:::;n. Fir s t we c o lo r t h e ve r t ic e s o f t h e g r a p h a s fo llo ws :

®
³
v

(1)
j

´
= 1 fo r 1 · j · n a n d ®

³
v

(2)
j

´
= ( r ¡ 1 ) n + 2 fo r 1 · j · n,

®
³
v

(i+1)
j

´
= ( i ¡ 1 ) n + 1 fo r 2 · i · r

2
¡ 1 a n d 1 · j · n,

®
µ
v

( r
2
+i¡1)

j

¶
= ( r + i ¡ 2 ) n + 2 fo r 2 · i · r

2
¡ 1 a n d 1 · j · n,

®
³
v

(r¡1)
j

´
=

³
r
2
¡ 1

´
n + 1 fo r 1 · j · n a n d ®

³
v

(r)
j

´
=

³
3
2
r ¡ 2

´
n + 2 fo r 1 · j · n.

N e xt we c o lo r t h e e d g e s o f t h e g r a p h . Fo r e a c h e d g e v(i)p v
(j)
q 2 E ( Kn;:::;n ) wit h

1 · i < j · r a n d p = 1 ; : : : ; n, q = 1 ; : : : ; n, d e ¯ n e a c o lo r ®
³
v(i)p v

(j)
q

´
a s fo llo ws :

P r oof: L e t n = l + 3 . Cle a r ly, n ¸ 4 . Co n s id e r t h e c o m p le t e b ip a r t it e g r a p h Kn+l;2n wit h
b ip a r t it io n ( X; Y ) , wh e r e jXj = n + l a n d jY j = 2 n. B y Th e o r e m 2 , we h a ve Â00 ( Kn+l;2n ) =

P r oof: Fir s t le t u s n o t e t h a t t h e t h e o r e m is t r u e fo r t h e c a s e r = 2 , s in c e w¿ ( Kn;n ) =
Â00 ( Kn;n ) = n + 2 fo r a n y n 2 N , b y Th e o r e m 5 .



P. Petrosyan and N. Khachatryan 3 3

fo r i = 1 ; : : : ;
j

r
4

k
, j = 2 ; : : : ; r

2
, i + j · r

2
+ 1 , le t

®
³
v(i)p v

(j)
q

´
= ( i + j ¡ 3 ) n +

(
1 + ( p + q ¡ 1 ) ( m o d n) , if p + q 6= n + 1 ,
n + 1 , if p + q = n + 1 ;

fo r i = 2 ; : : : ; r
2
¡ 1 , j =

j
r
4

k
+ 2 ; : : : ; r

2
, i + j ¸ r

2
+ 2 , le t

®
³
v(i)p v

(j)
q

´
=

³
i + j + r

2
¡ 4

´
n +

(
1 + ( p + q ¡ 1 ) ( m o d n) , if p + q 6= n + 1 ,
n + 1 , if p + q = n + 1 ;

fo r i = 3 ; : : : ; r
2
, j = r

2
+ 1 ; : : : ; r ¡ 2 , j ¡ i · r

2
¡ 2 , le t

®
³
v(i)p v

(j)
q

´
=

³
r
2

+ j ¡ i ¡ 1
´
n +

(
1 + ( p + q ¡ 1 ) ( m o d n) , if p + q 6= n + 1 ,
n + 1 , if p + q = n + 1 ;

fo r i = 1 ; : : : ; r
2
, j = r

2
+ 1 ; : : : ; r, j ¡ i ¸ r

2
, le t

®
³
v(i)p v

(j)
q

´
= ( j ¡ i ¡ 1 ) n +

(
1 + ( p + q ¡ 1 ) ( m o d n) , if p + q 6= n + 1 ,
n + 1 , if p + q = n + 1 ;

fo r i = 2 ; : : : ; 1 +
j

r¡2
4

k
, j = r

2
+ 1 ; : : : ; r

2
+

j
r¡2
4

k
, j ¡ i = r

2
¡ 1 , le t

®
³
v(i)p v

(j)
q

´
= ( 2 i ¡ 3 ) n +

(
1 + ( p + q ¡ 1 ) ( m o d n) , if p + q 6= n + 1 ,
n + 1 , if p + q = n + 1 ;

fo r i =
j

r¡2
4

k
+ 2 ; : : : ; r

2
, j = r

2
+ 1 +

j
r¡2
4

k
; : : : ; r ¡ 1 , j ¡ i = r

2
¡ 1 , le t

®
³
v(i)p v

(j)
q

´
= ( i + j ¡ 3 ) n +

(
1 + ( p + q ¡ 1 ) ( m o d n) , if p + q 6= n + 1 ,
n + 1 , if p + q = n + 1 ;

fo r i = r
2

+ 1 ; : : : ; r
2

+
j

r
4

k
¡ 1 , j = r

2
+ 2 ; : : : ; r ¡ 2 , i + j · 3

2
r ¡ 1 , le t

®
³
v(i)p v

(j)
q

´
= ( i + j ¡ r ¡ 1 ) n +

(
1 + ( p + q ¡ 1 ) ( m o d n) , if p + q 6= n + 1 ,
n + 1 , if p + q = n + 1 ;

fo r i = r
2

+ 1 ; : : : ; r ¡ 1 , j = r
2

+
j

r
4

k
+ 1 ; : : : ; r, i + j ¸ 3

2
r, le t

®
³
v(i)p v

(j)
q

´
=

³
i + j ¡ r

2
¡ 2

´
n +

(
1 + ( p + q ¡ 1 ) ( m o d n) , if p + q 6= n + 1 ,
n + 1 , if p + q = n + 1 .

L e t u s p r o ve t h a t ® is a n in t e r va l t o t a l
³³

3
2
r ¡ 2

´
n + 2

´
-c o lo r in g o f Kn;:::;n.

Fir s t we s h o w t h a t fo r e a c h c 2
h
1 ;

³
3
2
r ¡ 2

´
n + 2

i
, t h e r e is ve 2 V E ( Kn;:::;n ) wit h

®( ve) = c.

Co n s id e r t h e ve r t ic e s v
(1)
1 a n d v

(r)
1 . B y t h e d e ¯ n it io n o f ®, we h a ve

S
h
v

(1)
1 ; ®

i
= S

³
v

(1)
1 ; ®

´
[

n
®

³
v

(1)
1

´o
=

³Sr¡1
l=1 ( [2 ; n + 1 ] © ( l ¡ 1 ) n)

´
[ f 1 g =

= [2 ; ( r ¡ 1 ) n + 1 ] [ f 1 g = [1 ; ( r ¡ 1 ) n + 1 ] a n d
S

h
v

(r)
1 ; ®

i
= S

³
v

(r)
1 ; ®

´
[

n
®

³
v

(r)
1

´o
=
µS 3

2
r¡2

l= r
2

( [2 ; n + 1 ] © ( l ¡ 1 ) n)
¶
[

n³
3
2
r ¡ 2

´
n + 2

o
=

=
h³

r
2
¡ 1

´
n + 2 ;

³
3
2
r ¡ 2

´
n + 1

i
[

n³
3
2
r ¡ 2

´
n + 2

o
=

h³
r
2
¡ 1

´
n + 2 ;

³
3
2
r ¡ 2

´
n + 2

i
.



3 4 Interval Total Colorings of Complete Multipartite Graphs and Hypercubes

It is s t r a ig h t fo r wa r d t o c h e c k t h a t S
h
v

(1)
1 ; ®

i
[ S

h
v

(r)
1 ; ®

i
=

h
1 ;

³
3
2
r ¡ 2

´
n + 2

i
, s o fo r

e a c h c 2
h
1 ;

³
3
2
r ¡ 2

´
n + 2

i
, t h e r e is ve 2 V E ( Kn;:::;n ) wit h ®( ve) = c.

N e xt we s h o w t h a t t h e e d g e s in c id e n t t o e a c h ve r t e x o f Kn;:::;n t o g e t h e r wit h t h is ve r t e x
a r e c o lo r e d b y ( r ¡ 1 ) n + 1 c o n s e c u t ive c o lo r s .

L e t v
(i)
j 2 V ( Kn;:::;n ) , wh e r e 1 · i · r, 1 · j · n.

Case 1. 1 · i · 2 , 1 · j · n.
B y t h e d e ¯ n it io n o f ®, we h a ve

S
h
v

(1)
j ; ®

i
= S

³
v

(1)
j ; ®

´
[

n
®

³
v

(1)
j

´o
=

³Sr¡1
l=1 ( [2 ; n + 1 ] © ( l ¡ 1 ) n)

´
[ f 1 g =

= [2 ; ( r ¡ 1 ) n + 1 ] [ f1 g = [1 ; ( r ¡ 1 ) n + 1 ] a n d
S

h
v

(2)
j ; ®

i
= S

³
v

(2)
j ; ®

´
[

n
®

³
v

(2)
j

´o
=

³Sr¡1
l=1 ( [2 ; n + 1 ] © ( l ¡ 1 ) n)

´
[ f ( r ¡ 1 ) n + 2 g =

= [2 ; ( r ¡ 1 ) n + 1 ] [ f ( r ¡ 1 ) n + 2 g = [2 ; ( r ¡ 1 ) n + 2 ].

Case 2. 3 · i · r
2
, 1 · j · n.

B y t h e d e ¯ n it io n o f ®, we h a ve

S
h
v

(i)
j ; ®

i
= S

³
v

(i)
j ; ®

´
[

n
®

³
v

(i)
j

´o
=

³Sr¡3+i
l=i¡1 ( [2 ; n + 1 ] © ( l ¡ 1 ) n)

´
[ f ( i ¡ 2 ) n + 1 g =

= [( i ¡ 2 ) n + 2 ; ( r ¡ 3 + i) n + 1 ] [ f ( i ¡ 2 ) n + 1 g = [( i ¡ 2 ) n + 1 ; ( r ¡ 3 + i ) n + 1 ].

Case 3. r
2

+ 1 · i · r ¡ 2 , 1 · j · n.
B y t h e d e ¯ n it io n o f ®, we h a ve

S
h
v

(i)
j ; ®

i
= S

³
v

(i)
j ; ®

´
[

n
®

³
v

(i)
j

´o
=

µS r
2
¡1+i

l=i¡ r
2
+1 ( [2 ; n + 1 ] © ( l ¡ 1 ) n)

¶
[

n³
r
2

+ i ¡ 1
´
n + 2

o
=

h³
i ¡ r

2

´
n + 2 ;

³
r
2

+ i ¡ 1
´
n + 1

i
[

n³
r
2

+ i ¡ 1
´
n + 2

o
=

h³
i ¡ r

2

´
n + 2 ;

³
r
2

+ i ¡ 1
´
n + 2

i
.

Case 4. r ¡ 1 · i · r; 1 · j · n.
B y t h e d e ¯ n it io n o f ®, we h a ve

S
h
v

(r¡1)
j ; ®

i
= S

³
v

(r¡1)
j ; ®

´
[

n
®

³
v

(r¡1)
j

´o
=

µS 3
2
r¡2

l= r
2

( [2 ; n + 1 ] © ( l ¡ 1 ) n)
¶
[

n³
r
2
¡ 1

´
n + 1

o
=

h³
r
2
¡ 1

´
n + 2 ;

³
3
2
r ¡ 2

´
n + 1

i
[

n³
r
2
¡ 1

´
n + 1

o
=

h³
r
2
¡ 1

´
n + 1 ;

³
3
2
r ¡ 2

´
n + 1

i
a n d

S
h
v

(r)
j ; ®

i
= S

³
v

(r)
j ; ®

´
[

n
®

³
v

(r)
j

´o
=
µS 3

2
r¡2

l= r
2

( [2 ; n + 1 ] © ( l ¡ 1 ) n)
¶
[

n³
3
2
r ¡ 2

´
n + 2

o
=

h³
r
2
¡ 1

´
n + 2 ;

³
3
2
r ¡ 2

´
n + 1

i
[

n³
3
2
r ¡ 2

´
n + 2

o
=

h³
r
2
¡ 1

´
n + 2 ;

³
3
2
r ¡ 2

´
n + 2

i
.

Th is s h o ws t h a t ® is a n in t e r va l t o t a l
³³

3
2
r ¡ 2

´
n + 2

´
-c o lo r in g o f Kn;:::;n; t h u s , Kn;:::;n 2

T a n d w¿ ( Kn;:::;n ) ·
³

3
2
r ¡ 2

´
n + 2 .

N o t e t h a t t h e u p p e r b o u n d in Th e o r e m 1 0 is s h a r p wh e n r = 2 o r n = 1 . A ls o , b y
Th e o r e m 1 0 , we h a ve t h a t if r = 2 o r r is e ve n a n d n is o d d , t h e n Kn;:::;n 2 T ; o t h e r wis e ,
b y Th e o r e m 3 a n d t a kin g in t o a c c o u n t t h a t Kn;:::;n is a n ( r ¡ 1 ) n-r e g u la r g r a p h , we h a ve
Kn;:::;n 2 T a n d w¿ ( Kn;:::;n ) = Â00 ( Kn;:::;n ) = ( r ¡ 1 ) n + 1 . Ou r n e xt r e s u lt g ive s a lo we r b o u n d
fo r W¿ ( Kn;:::;n ) wh e n n ¢ r is e ve n .

T heor em 11: If r ¸ 2 ; n 2 N and n ¢ r is even, then W¿ ( Kn;:::;n ) ¸
³

3
2
r ¡ 1

´
n + 1 .



P. Petrosyan and N. Khachatryan 3 5

n
v

(i)
j j 1 · i · r; 1 · j · n

o
a n d

E ( Kn;:::;n ) =
n
v(i)p v

(j)
q j 1 · i < j · r; 1 · p · n; 1 · q · n

o
.

D e ¯ n e a t o t a l c o lo r in g ® o f Kn;:::;n. Fir s t we c o lo r t h e ve r t ic e s o f t h e g r a p h a s fo llo ws :

®
³
v

(1)
j

´
= j fo r 1 · j · n a n d ®

³
v

(2)
j

´
= ( r ¡ 1 ) n + 1 + j fo r 1 · j · n,

®
³
v

(i+1)
j

´
= ( i ¡ 1 ) n + j fo r 2 · i · r

2
¡ 1 a n d 1 · j · n,

®
µ
v

( r
2
+i¡1)

j

¶
= ( r + i ¡ 2 ) n + 1 + j fo r 2 · i · r

2
¡ 1 a n d 1 · j · n,

®
³
v

(r¡1)
j

´
=

³
r
2
¡ 1

´
n + j fo r 1 · j · n a n d ®

³
v

(r)
j

´
=

³
3
2
r ¡ 2

´
n + 1 + j fo r 1 · j · n.

N e xt we c o lo r t h e e d g e s o f t h e g r a p h . Fo r e a c h e d g e v(i)p v
(j)
q 2 E ( Kn;:::;n ) wit h

1 · i < j · r a n d p = 1 ; : : : ; n, q = 1 ; : : : ; n, d e ¯ n e a c o lo r ®
³
v(i)p v

(j)
q

´
a s fo llo ws :

fo r i = 1 ; : : : ;
j

r
4

k
, j = 2 ; : : : ; r

2
, i + j · r

2
+ 1 , le t

®
³
v(i)p v

(j)
q

´
= ( i + j ¡ 3 ) n + p + q;

fo r i = 2 ; : : : ; r
2
¡ 1 , j =

j
r
4

k
+ 2 ; : : : ; r

2
, i + j ¸ r

2
+ 2 , le t

®
³
v(i)p v

(j)
q

´
=

³
i + j + r

2
¡ 4

´
n + p + q;

fo r i = 3 ; : : : ; r
2
, j = r

2
+ 1 ; : : : ; r ¡ 2 , j ¡ i · r

2
¡ 2 , le t

®
³
v(i)p v

(j)
q

´
=

³
r
2

+ j ¡ i ¡ 1
´
n + p + q;

fo r i = 1 ; : : : ; r
2
, j = r

2
+ 1 ; : : : ; r, j ¡ i ¸ r

2
, le t

®
³
v(i)p v

(j)
q

´
= ( j ¡ i ¡ 1 ) n + p + q;

fo r i = 2 ; : : : ; 1 +
j

r¡2
4

k
, j = r

2
+ 1 ; : : : ; r

2
+

j
r¡2
4

k
, j ¡ i = r

2
¡ 1 , le t

®
³
v(i)p v

(j)
q

´
= ( 2 i ¡ 3 ) n + p + q;

fo r i =
j

r¡2
4

k
+ 2 ; : : : ; r

2
, j = r

2
+ 1 +

j
r¡2
4

k
; : : : ; r ¡ 1 , j ¡ i = r

2
¡ 1 , le t

®
³
v(i)p v

(j)
q

´
= ( i + j ¡ 3 ) n + p + q;

fo r i = r
2

+ 1 ; : : : ; r
2

+
j

r
4

k
¡ 1 , j = r

2
+ 2 ; : : : ; r ¡ 2 , i + j · 3

2
r ¡ 1 , le t

®
³
v(i)p v

(j)
q

´
= ( i + j ¡ r ¡ 1 ) n + p + q;

fo r i = r
2

+ 1 ; : : : ; r ¡ 1 , j = r
2

+
j

r
4

k
+ 1 ; : : : ; r, i + j ¸ 3

2
r, le t

P r oof: W e c o n s id e r t wo c a s e s .
Case 1: r is e ve n .
L e t V ( Kn;:::;n ) =



3 6 Interval Total Colorings of Complete Multipartite Graphs and Hypercubes

®
³
v(i)p v

(j)
q

´
=

³
i + j ¡ r

2
¡ 2

´
n + p + q.

L e t u s p r o ve t h a t ® is a n in t e r va l t o t a l
³³

3
2
r ¡ 1

´
n + 1

´
-c o lo r in g o f Kn;:::;n.

Fir s t we s h o w t h a t fo r e a c h c 2
h
1 ;

³
3
2
r ¡ 1

´
n + 1

i
, t h e r e is ve 2 V E ( Kn;:::;n ) wit h

®( ve) = c.

Co n s id e r t h e ve r t ic e s v
(1)
1 ; : : : ; v

(1)
n a n d v

(r)
1 ; : : : ; v

(r)
n . B y t h e d e ¯ n it io n o f ®, fo r 1 · j · n,

we h a ve

S
h
v

(1)
j ; ®

i
= S

³
v

(1)
j ; ®

´
[

n
®

³
v

(1)
j

´o
=

³Sr¡1
l=1 ( [j + 1 ; j + n] © ( l ¡ 1 ) n)

´
[ fjg =

= [j + 1 ; ( r ¡ 1 ) n + j] [ fjg = [j; ( r ¡ 1 ) n + j] a n d S
h
v

(r)
j ; ®

i
= S

³
v

(r)
j ; ®

´
[

n
®

³
v

(r)
j

´o
=

=
µS 3

2
r¡2

l= r
2

( [j + 1 ; j + n] © ( l ¡ 1 ) n)
¶
[

n³
3
2
r ¡ 2

´
n + 1 + j

o
=

=
h³

r
2
¡ 1

´
n + 1 + j;

³
3
2
r ¡ 2

´
n + j

i
[

n³
3
2
r ¡ 2

´
n + 1 + j

o
=

=
h³

r
2
¡ 1

´
n + 1 + j;

³
3
2
r ¡ 2

´
n + 1 + j

i
.

L e t C =
Sn

j=1 S
h
v

(1)
j ; ®

i
a n d C =

Sn
j=1 S

h
v

(r)
j ; ®

i
. It is s t r a ig h t fo r wa r d t o c h e c k t h a t

C [ C =
h
1 ;

³
3
2
r ¡ 1

´
n + 1

i
, s o fo r e a c h c 2

h
1 ;

³
3
2
k ¡ 1

´
n + 1

i
, t h e r e is ve 2 V E ( Kn;:::;n )

wit h ®( ve) = c.
N e xt we s h o w t h a t t h e e d g e s in c id e n t t o e a c h ve r t e x o f Kn;:::;n t o g e t h e r wit h t h is ve r t e x

a r e c o lo r e d b y ( r ¡ 1 ) n + 1 c o n s e c u t ive c o lo r s .
L e t v

(i)
j 2 V ( Kn;:::;n ) , wh e r e 1 · i · r, 1 · j · n.

Subcase 1.1. 1 · i · 2 , 1 · j · n.
B y t h e d e ¯ n it io n o f ®, we h a ve

S
h
v

(1)
j ; ®

i
= S

³
v

(1)
j ; ®

´
[

n
®

³
v

(1)
j

´o
=

³Sr¡1
l=1 ( [j + 1 ; j + n] © ( l ¡ 1 ) n)

´
[ fjg =

= [j + 1 ; ( r ¡ 1 ) n + j] [ fjg = [j; ( r ¡ 1 ) n + j] a n d
S

h
v

(2)
j ; ®

i
= S

³
v

(2)
j ; ®

´
[

n
®

³
v

(2)
j

´o
=

³Sr¡1
l=1 ( [j + 1 ; j + n] © ( l ¡ 1 ) n)

´
[f ( r¡ 1 ) n+1 +jg =

= [j + 1 ; ( r ¡ 1 ) n + 1 + j].

Subcase 1.2. 3 · i · r
2
, 1 · j · n.

B y t h e d e ¯ n it io n o f ®, we h a ve

S
h
v

(i)
j ; ®

i
= S

³
v

(i)
j ; ®

´
[

n
®

³
v

(i)
j

´o
=

³Sr¡3+i
l=i¡1 ( [j + 1 ; j + n] © ( l ¡ 1 ) n)

´
[ f( i ¡ 2 ) n + jg =

= [( i ¡ 2 ) n + 1 + j; ( r ¡ 3 + i ) n + j] [ f ( i ¡ 2 ) n + jg = [( i ¡ 2 ) n + j; ( r ¡ 3 + i ) n + j].

Subcase 1.3. r
2

+ 1 · i · r ¡ 2 , 1 · j · n.
B y t h e d e ¯ n it io n o f ®, we h a ve

S
h
v

(i)
j ; ®

i
= S

³
v

(i)
j ; ®

´
[

n
®

³
v

(i)
j

´o
=

=
µS r

2
¡1+i

l=i¡ r
2
+1 ( [j + 1 ; j + n] © ( l ¡ 1 ) n)

¶
[

n³
r
2

+ i ¡ 1
´
n + 1 + j

o
=

=
h³

i ¡ r
2

´
n + 1 + j;

³
r
2

+ i ¡ 1
´
n + j

i
[

n³
r
2

+ i ¡ 1
´
n + 1 + j

o
=

h³
i ¡ r

2

´
n + 1 + j;

³
r
2

+ i ¡ 1
´
n + 1 + j

i
.

Subcase 1.4. r ¡ 1 · i · r; 1 · j · n.
B y t h e d e ¯ n it io n o f ®, we h a ve



P. Petrosyan and N. Khachatryan 3 7

S
h
v

(r¡1)
j ; ®

i
= S

³
v

(r¡1)
j ; ®

´
[

n
®

³
v

(r¡1)
j

´o
=

µS 3
2
r¡2

l= r
2

( [j + 1 ; j + n] © ( l ¡ 1 ) n )
¶
[

n³
r
2
¡ 1

´
n + j

o
=

h³
r
2
¡ 1

´
n + 1 + j;

³
3
2
r ¡ 2

´
n + j

i
[

n³
r
2
¡ 1

´
n + j

o
=

h³
r
2
¡ 1

´
n + j;

³
3
2
r ¡ 2

´
n + j

i
a n d

S
h
v

(r)
j ; ®

i
= S

³
v

(r)
j ; ®

´
[

n
®

³
v

(r)
j

´o
=
µS 3

2
r¡2

l= r
2

( [j + 1 ; j + n] © ( l ¡ 1 ) n)
¶
[

n³
3
2
r ¡ 2

´
n + 1 + j

o
=

h³
r
2
¡ 1

´
n + 1 + j;

³
3
2
r ¡ 2

´
n + j

i
[

n³
3
2
r ¡ 2

´
n + 1 + j

o
=

h³
r
2
¡ 1

´
n + 1 + j;

³
3
2
r ¡ 2

´
n + 1 + j

i
.

Th is s h o ws t h a t ® is a n in t e r va l t o t a l
³³

3
2
r ¡ 1

´
n + 1

´
-c o lo r in g o f Kn;:::;n; t h u s ,

W¿ ( Kn;:::;n ) ¸
³

3
2
r ¡ 1

´
n + 1 fo r e ve n r ¸ 2 .

Case 2: n is e ve n .
L e t n = 2 m, m 2 N . L e t Si =

n
u

(i)
1 ; : : : ; u

(i)
m ; u

(r+i)
1 ; : : : ; u

(r+i)
m

o
( 1 · i · r ) b e t h e

r in d e p e n d e n t s e t s o f ve r t ic e s o f Kn;:::;n. Fo r i = 1 ; : : : ; 2 r, d e ¯ n e t h e s e t Ui a s fo llo ws :

Ui =
n
u

(i)
1 ; : : : ; u

(i)
m

o
. Cle a r ly, V ( Kn;:::;n ) =

S2r
i=1 Ui. Fo r 1 · i < j · 2 r, d e ¯ n e ( Ui; Uj ) a s t h e

s e t o f a ll e d g e s b e t we e n Ui a n d Uj . It is e a s y t o s e e t h a t fo r 1 · i < j · 2 r, j ( Ui; Uj ) j = m2
e xc e p t fo r j( Ui; Ur+i ) j = 0 wh e n e ve r i = 1 ; : : : ; r. If we c o n s id e r t h e s e t s Ui a s t h e ve r t ic e s
a n d t h e s e t s ( Ui; Uj ) a s t h e e d g e s , t h e n we o b t a in t h a t Kn;:::;n is is o m o r p h ic t o t h e g r a p h
K2r ¡ F , wh e r e F is a p e r fe c t m a t c h in g o f K2r. N o w we d e ¯ n e a t o t a l c o lo r in g ¯ o f t h e
g r a p h Kn;:::;n. Fir s t we c o lo r t h e ve r t ic e s o f t h e g r a p h a s fo llo ws :

¯
³
u

(1)
j

´
= j fo r 1 · j · m a n d ¯

³
u

(2)
j

´
= ( 2 r ¡ 2 ) m + 1 + j fo r 1 · j · m,

¯
³
u

(i+1)
j

´
= ( i ¡ 1 ) m + j fo r 2 · i · r ¡ 1 a n d 1 · j · m,

¯
³
u

(r+i¡1)
j

´
= ( 2 r + i ¡ 3 ) m + 1 + j fo r 2 · i · r ¡ 1 a n d 1 · j · m,

¯
³
u

(2r¡1)
j

´
= ( r ¡ 1 ) m + j fo r 1 · j · m a n d ¯

³
u

(2r)
j

´
= ( 3 r ¡ 3 ) m + 1 + j fo r 1 · j · m.

N e xt we c o lo r t h e e d g e s o f t h e g r a p h . Fo r e a c h e d g e u(i)p u
(j)
q 2 E ( Kn;:::;n ) wit h

1 · i < j · 2 r a n d p = 1 ; : : : ; m, q = 1 ; : : : ; m, d e ¯ n e a c o lo r ¯
³
u(i)p u

(j)
q

´
a s fo llo ws :

fo r i = 1 ; : : : ;
j

r
2

k
, j = 2 ; : : : ; r, i + j · r + 1 , le t

¯
³
u(i)p u

(j)
q

´
= ( i + j ¡ 3 ) m + p + q;

fo r i = 2 ; : : : ; r ¡ 1 , j =
j

r
2

k
+ 2 ; : : : ; r, i + j ¸ r + 2 , le t

¯
³
u(i)p u

(j)
q

´
= ( i + j + r ¡ 5 ) m + p + q;

fo r i = 3 ; : : : ; r, j = r + 1 ; : : : ; 2 r ¡ 2 , j ¡ i · r ¡ 2 , le t

¯
³
u(i)p u

(j)
q

´
= ( r + j ¡ i ¡ 2 ) m + p + q;

fo r i = 1 ; : : : ; r ¡ 1 , j = r + 2 ; : : : ; 2 r, j ¡ i ¸ r + 1 , le t

¯
³
u(i)p u

(j)
q

´
= ( j ¡ i ¡ 2 ) m + p + q;



3 8 Interval Total Colorings of Complete Multipartite Graphs and Hypercubes

fo r i = 2 ; : : : ; 1 +
j

r¡1
2

k
, j = r + 1 ; : : : ; r +

j
r¡1
2

k
, j ¡ i = r ¡ 1 , le t

¯
³
u(i)p u

(j)
q

´
= ( 2 i ¡ 3 ) m + p + q;

fo r i =
j

r¡1
2

k
+ 2 ; : : : ; r, j = r + 1 +

j
r¡1
2

k
; : : : ; 2 r ¡ 1 , j ¡ i = r ¡ 1 , le t

¯
³
u(i)p u

(j)
q

´
= ( i + j ¡ 4 ) m + p + q;

fo r i = r + 1 ; : : : ; r +
j

r
2

k
¡ 1 , j = r + 2 ; : : : ; 2 r ¡ 2 , i + j · 3 r ¡ 1 , le t

¯
³
u(i)p u

(j)
q

´
= ( i + j ¡ 2 r ¡ 1 ) m + p + q;

fo r i = r + 1 ; : : : ; 2 r ¡ 1 , j = r +
j

r
2

k
+ 1 ; : : : ; 2 r, i + j ¸ 3 r, le t

¯
³
u(i)p u

(j)
q

´
= ( i + j ¡ r ¡ 3 ) m + p + q.

L e t u s p r o ve t h a t ¯ is a n in t e r va l t o t a l
³³

3
2
r ¡ 1

´
n + 1

´
-c o lo r in g o f t h e g r a p h Kn;:::;n.

Fir s t we s h o w t h a t fo r e a c h c 2
h
1 ;

³
3
2
r ¡ 1

´
n + 1

i
, t h e r e is ve 2 V E ( Kn;:::;n ) wit h

¯ ( ve) = c.

Co n s id e r t h e ve r t ic e s u
(1)
1 ; : : : ; u

(1)
m a n d u

(2r)
1 ; : : : ; u

(2r)
m . B y t h e d e ¯ n it io n o f ¯, fo r 1 · j ·

m, we h a ve

S
h
u

(1)
j ; ¯

i
= S

³
u

(1)
j ; ¯

´
[

n
¯

³
u

(1)
j

´o
=

³S2r¡2
l=1 ( [j + 1 ; j + m] © ( l ¡ 1 ) m )

´
[ fjg =

[j + 1 ; ( 2 r ¡ 2 ) m + j] [ fjg = [j; ( 2 r ¡ 2 ) m + j] a n d
S

h
u

(2r)
j ; ¯

i
= S

³
u

(2r)
j ; ¯

´
[

n
¯

³
u

(2r)
j

´o
=

³S3r¡3
l=r ( [j + 1 ; j + m] © ( l ¡ 1 ) m )

´
[f ( 3 r ¡ 3 ) m +

1 +jg = [( r¡ 1 ) m+1 +j; ( 3 r¡ 3 ) m+j][f ( 3 r¡ 3 ) m+1 +jg = [( r¡ 1 ) m+1 +j; ( 3 r¡ 3 ) m+1 +j].

L e t ~C =
Sm

j=1 S
h
u

(1)
j ; ¯

i
a n d

~ ~C =
Sm

j=1 S
h
u

(2r)
j ; ¯

i
. It is s t r a ig h t fo r wa r d t o c h e c k t h a t

~C [ ~ ~C =
h
1 ;

³
3
2
r ¡ 1

´
n + 1

i
, s o fo r e a c h c 2

h
1 ;

³
3
2
r ¡ 1

´
n + 1

i
, t h e r e is ve 2 V E ( Kn;:::;n )

wit h ¯ ( ve) = c.
N e xt we s h o w t h a t t h e e d g e s in c id e n t t o e a c h ve r t e x o f Kn;:::;n t o g e t h e r wit h t h is ve r t e x

a r e c o lo r e d b y ( r ¡ 1 ) n + 1 c o n s e c u t ive c o lo r s .
L e t v

(i)
j 2 V ( Kn;:::;n ) , wh e r e 1 · i · 2 r, 1 · j · m.

Subcase 2.1. 1 · i · 2 , 1 · j · m.
B y t h e d e ¯ n it io n o f ¯, we h a ve

S
h
v

(1)
j ; ¯

i
= S

³
u

(1)
j ; ¯

´
[

n
¯

³
u

(1)
j

´o
=

³S2r¡2
l=1 ( [j + 1 ; j + m] © ( l ¡ 1 ) m )

´
[ fjg =

[j + 1 ; ( 2 r ¡ 2 ) m + j] [ fjg = [j; ( 2 r ¡ 2 ) m + j] a n d
S

h
u

(2)
j ; ¯

i
= S

³
u

(2)
j ; ¯

´
[

n
¯

³
u

(2)
j

´o
=

³S2r¡2
l=1 ( [j + 1 ; j + m] © ( l ¡ 1 ) m )

´
[ f ( 2 r ¡ 2 ) m +

1 + jg = [j + 1 ; ( 2 r ¡ 2 ) m + j] [ f ( 2 r ¡ 2 ) m + 1 + jg = [j + 1 ; ( 2 r ¡ 2 ) m + 1 + j].

Subcase 2.2. 3 · i · r, 1 · j · m.
B y t h e d e ¯ n it io n o f ¯, we h a ve



P. Petrosyan and N. Khachatryan 3 9

S
h
u

(i)
j ; ¯

i
= S

³
u

(i)
j ; ¯

´
[

n
¯

³
u

(i)
j

´o
=

³S2r¡4+i
l=i¡1 ( [j + 1 ; j + m] © ( l ¡ 1 ) m )

´
[f ( i¡ 2 ) m+jg =

[( i ¡ 2 ) m + 1 + j; ( 2 r ¡ 4 + i ) m + j] [ f ( i ¡ 2 ) m + jg = [( i ¡ 2 ) m + j; ( 2 r ¡ 4 + i ) m + j].

Subcase 2.3. r + 1 · i · 2 r ¡ 2 , 1 · j · m.
B y t h e d e ¯ n it io n o f ¯, we h a ve

S
h
u

(i)
j ; ¯

i
= S

³
u

(i)
j ; ¯

´
[

n
¯

³
u

(i)
j

´o
=

³Sr¡2+i
l=i¡r+1 ( [j + 1 ; j + m] © ( l ¡ 1 ) m)

´
[ f ( r + i ¡

2 ) m + 1 + jg = [( i ¡ r ) m + 1 + j; ( r + i ¡ 2 ) m + j] [ f ( r + i ¡ 2 ) m + 1 + jg =
[( i ¡ r ) m + 1 + j; ( r + i ¡ 2 ) m + 1 + j].

Subcase 2.4. 2 r ¡ 1 · i · 2 r; 1 · j · m.
B y t h e d e ¯ n it io n o f ¯, we h a ve

S
h
u

(2r¡1)
j ; ¯

i
= S

³
u

(2r¡1)
j ; ¯

´
[

n
¯

³
u

(2r¡1)
j

´o
=

³S3r¡3
l=r ( [j + 1 ; j + m] © ( l ¡ 1 ) m )

´
[ f ( r ¡

1 ) m + jg = [( r ¡ 1 ) m + 1 + j; ( 3 r ¡ 3 ) m + j] [ f ( r ¡ 1 ) m + jg = [( r ¡ 1 ) m + j; ( 3 r ¡ 3 ) m + j]
a n d

S
h
u

(2r)
j ; ¯

i
= S

³
u

(2r)
j ; ¯

´
[

n
¯

³
u

(2r)
j

´o
=

³S3r¡3
l=r ( [j + 1 ; j + m] © ( l ¡ 1 ) m )

´
[f ( 3 r ¡ 3 ) m +

1 +jg = [( r¡ 1 ) m+1 +j; ( 3 r¡ 3 ) m+j][f ( 3 r¡ 3 ) m+1 +jg = [( r¡ 1 ) m+1 +j; ( 3 r¡ 3 ) m+1 +j].

Th is s h o ws t h a t ¯ is a n in t e r va l t o t a l
³³

3
2
r ¡ 1

´
n + 1

´
-c o lo r in g o f Kn;:::;n; t h u s ,

W¿ ( Kn;:::;n ) ¸
³

3
2
r ¡ 1

´
n + 1 fo r e ve n n ¸ 2 .

3 . In t e r va l To t a l Co lo r in g s o f H yp e r c u b e s

In [7 ], t h e ¯ r s t a u t h o r in ve s t ig a t e d in t e r va l c o lo r in g s o f h yp e r c u b e s Qn. In p a r t ic u la r , h e

p r o ve d t h a t Qn 2 N a n d w ( Qn ) = n, W ( Qn ) ¸ n(n+1)2 fo r a n y n 2 N . In t h e s a m e p a p e r
h e a ls o c o n je c t u r e d t h a t W ( Qn ) =

n(n+1)
2

fo r a n y n 2 N . In [9 ], t h e a u t h o r s c o n ¯ r m e d t h is
c o n je c t u r e . H e r e , we p r o ve t h a t W¿ ( Qn ) =

(n+1)(n+2)
2

fo r a n y n 2 N .

T heor em 12: If n 2 N , then W¿ ( Qn ) = (n+1)(n+2)2 .

2
fo r a n y n 2 N , b y Th e o r e m 7 .

Fo r t h e p r o o f o f t h e t h e o r e m , it s u ± c e s t o s h o w t h a t W¿ ( Qn ) · (n+1)(n+2)2 fo r a n y n 2 N .
L e t ' b e a n in t e r va l t o t a l W¿ ( Qn ) -c o lo r in g o f Qn.

L e t i = 0 o r 1 a n d Q
(i)
n+1 b e a s u b g r a p h o f t h e g r a p h Qn+1, in d u c e d b y t h e ve r t ic e s

f ( i; ®2; ®3; : : : ; ®n+1 ) j ( ®2; ®3; : : : ; ®n+1 ) 2 f 0 ; 1 gng. Cle a r ly, Q(i)n+1 is is o m o r p h ic t o Qn fo r
i 2 f0 ; 1 g.

L e t u s d e ¯ n e a n e d g e c o lo r in g à o f t h e g r a p h Qn+1 in t h e fo llo win g wa y:

(1) fo r i = 0 ; 1 a n d e ve r y e d g e ( i; ¹®)
³
i; ¹̄

´
2 E

³
Q

(i)
n+1

´
, le t

Ã
³
( i; ¹® )

³
i; ¹̄

´´
= '

³
¹® ¹̄

´
;

(2) fo r e ve r y ¹® 2 f0 ; 1 gn, le t

P r oof: Fir s t o f a ll le t u s n o t e t h a t W¿ ( Qn ) ¸ (n+1)(n+2)



4 0 Interval Total Colorings of Complete Multipartite Graphs and Hypercubes

à ( ( 0 ; ¹® ) ( 1 ; ¹® ) ) = ' ( ¹® ) .

It is n o t d i± c u lt t o s e e t h a t à is a n in t e r va l W¿ ( Qn ) -c o lo r in g o f t h e g r a p h Qn+1. Th u s ,

W¿ ( Qn ) · W ( Qn+1 ) = (n+1)(n+2)2 fo r a n y n 2 N .

B y Th e o r e m s 7 a n d 1 2 , we h a ve t h a t Qn h a s a n in t e r va l t o t a l t-c o lo r in g if a n d o n ly if
w¿ ( Qn ) · t · W¿ ( Qn ) .

Refer ences

[1 ] A . S . A s r a t ia n , T.M.J. D e n le y a n d R . H a g g kvis t , B ipartite Graphs and their Applica-
tions, Ca m b r id g e U n ive r s it y P r e s s , Ca m b r id g e , 1 9 9 8 .

[2 ] A .S . A s r a t ia n a n d R .R . K a m a lia n , \ In t e r va l c o lo r in g s o f e d g e s o f a m u lt ig r a p h " , Appl.
M ath., vo l. 5 , p p . 2 5 -3 4 , 1 9 8 7 .

[3 ] M. B e h z a d , G. Ch a r t r a n d a n d J.K . Co o p e r , \ Th e c o lo u r n u m b e r s o f c o m p le t e g r a p h s " ,
J . L ondon M ath. Soc., vo l. 4 2 , p p . 2 2 6 -2 2 8 , 1 9 6 7 .

[4 ] J. C. B e r m o n d , \ N o m b r e c h r o m a t iqu e t o t a l d u g r a p h e r -p a r t i c o m p le t " , J . L ondon
M ath. Soc., vo l. 2 , n o . 9 , p p . 2 7 9 -2 8 5 , 1 9 7 4 .

[5 ] 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, Y e r e va n , p p . 8 4 -8 5 , 2 0 0 7 .

[6 ] 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, vo l. 3 1 , p p . 1 2 2 -1 2 9 , 2 0 0 8 .

[7 ] P . A . P e t r o s ya n , \ In t e r va l e d g e -c o lo r in g s o f c o m p le t e g r a p h s a n d n-d im e n s io n a l c u b e s " ,
D iscrete M ath. 310, p p . 1 5 8 0 -1 5 8 7 , 2 0 1 0 .

[8 ] P . A . P e t r o s ya n a n d H . H . K h a c h a t r ia 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 m u lt ip a r -
t it e g r a p h s " , 4-th P olish Combinatorial Conference, B e d le wo , P o la n d , p . 3 5 , 2 0 1 2 .

[9 ] P . A . P e t r o s ya n , H . H . K h a c h a t r ia n a n d H .G. Ta n a n ya n , \ In t e r va l e d g e -c o lo r in g s o f
Ca r t e s ia n p r o d u c t s o f g r a p h s I" , D iscussiones M athematicae Graph Theory, vo l. 3 3 , n o .
3 , p p . 6 1 3 -6 3 2 , 2 0 1 3 .

[1 0 ] P . A . P e t r o s ya n a n d N . A . K h a c h a t r ya n ,\ In t e r va l t o t a l c o lo r in g s o f g r a p h s wit h a s p a n -
n in g s t a r " , M athematical P roblems of Computer Science, vo l. 3 2 , p p . 7 8 -8 5 , 2 0 0 9 .

[1 1 ] P . A . P e t r o s ya n a n d N .A . K h a c h a t r ya n , \ U p p e r b o u n d s fo r t h e m a xim u m s p a n in
in t e r va l t o t a l c o lo r in g s o f g r a p h s " , M athematical P roblems of Computer Science, vo l.
3 5 , p p . 1 9 -2 5 , 2 0 1 1 .

[1 2 ] P . A . P e t r o s ya n a n d N . A . K h a c h a t r ya n , \ On in t e r va l t o t a l c o lo r in g s o f t h e Ca r t e s ia n
p r o d u c t s o f g r a p h s " , P roceedings of the CSIT Conference, Y e r e va n , p p . 8 5 -8 6 , 2 0 1 3 .

[1 3 ] P . A . P e t r o s ya n a n d A . S . S h a s h ikya n ,\ On in t e r va l t o t a l c o lo r in g s o f t r e e s " , M athe-
matical P roblems of Computer Science, vo l. 3 2 , p p . 7 0 -7 3 , 2 0 0 9 .

[1 4 ] P .A . P e t r o s ya n a n d A .S . S h a s h ikya n ,\ On in t e r va l t o t a l c o lo r in g s o f b ip a r t it e g r a p h s " ,
P roceedings of the CSIT Conference, Y e r e va n , p p . 9 5 -9 8 , 2 0 0 9 .

[1 5 ] P .A . P e t r o s ya n a n d A .S . S h a s h ikya n , \ On in t e r va l t o t a l c o lo r in g s o f d o u b ly c o n ve x
b ip a r t it e g r a p h s " , M athematical P roblems of Computer Scienc, vo l. 3 3 , p p . 5 4 -5 8 , 2 0 1 0 .



P. Petrosyan and N. Khachatryan 4 1

[1 6 ] P . A . P e t r o s ya n , A . S . S h a s h ikya n a n d A .Y u . To 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
b ip a r t it e g r a p h s " , P roceedings of the 9th Cologne-Twente W orkshop on Graphs and
Combinatorial Optimization, Co lo g n e , Ge r m a n y, p p . 1 3 3 -1 3 6 , 2 0 1 0 .

[1 7 ] P . A . P e t r o s ya n , A . S . S h a s h ikya n , A .Y u . To r o s ya n a n d N .A . K h a c h a t r ya n , \ In t e r va l
t o t a l c o lo r in g s o f g r a p h s " , 6th Cracow Conference on Graph Theory "Zgorzelisko '10",
Zg o r z e lis ko , P o la n d , p . 1 1 , 2 0 1 0 .

[1 8 ] P .A . P e t r o s ya n a n d A .Y u . To 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 g r a p h s " , P ro-
ceedings of the CSIT Conference, Y e r e va n , p p . 9 9 -1 0 2 , 2 0 0 9 .

[1 9 ] A .S . S h a s h ikya n ,\ On in t e r va l t o t a l c o lo r in g s o f b ip a r t it e g r a p h s " , Ma s t e r 's Th e s is , Y e r e -
va n S t a t e U n ive r s it y, 2 9 p , 2 0 0 9 .

[2 0 ] D .B . W e s t , Introduction to Graph Theory, P rentice-Hall, N e w Je r s e y, 1 9 9 6 .

[2 1 ] H .P . Y a p , Total Colorings of Graphs, 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 .

Submitted 05.08.2014, accepted 27.11.2014.

ÈñÇí µ³½Ù³ÏáÕÙ³ÝÇ ·ñ³ýÝ»ñÇ ¨ ÑÇå»ñËáñ³Ý³ñ¹Ý»ñÇ
ÙÇç³Ï³Ûù³ÛÇÝ Édzϳï³ñ Ý»ñÏáõÙÝ»ñ

ä. ä»ïñáëÛ³Ý ¨ Ü. ʳã³ïñÛ³Ý

²Ù÷á÷áõÙ

G ·ñ³ýÇ Édzϳï³ñ Ý»ñÏáõÙÁ ³Û¹ ·ñ³ýÇ ³ÛÝ Ý»ñÏáõÙÝ ¿, áñÇ ¹»åùáõ٠ѳñ¨³Ý
·³·³ÃÝ»ñÁ ¨ ÏáÕ»ñÁ Ý»ñÏí³Í »Ý ï³ñµ»ñ ·áõÛÝ»ñáí ¨ ó³Ýϳó³Í ·³·³Ã ¨ Ýñ³Ý
ÏÇó ÏáÕ»ñÁ ¨ë Ý»ñÏí³Í »Ý ï³ñµ»ñ ·áõÛÝ»ñáí: G ·ñ³ýÇ Édzϳï³ñ Ý»ñÏáõÙÁ
1 ; : : : ; t ·áõÛÝ»ñáí ϳÝí³Ý»Ýù ÙÇç³Ï³Ûù³ÛÇÝ Édzϳï³ñ t–Ý»ñÏáõÙ, »Ã» µáÉáñ ·áõÛÝ»ñÁ
û·ï³·áñÍí»É »Ý, ¨ Ûáõñ³ù³ÝãÛáõñ v ·³·³ÃÇÝ ÏÇó ÏáÕ»ñÁ ¨ ³Û¹ ·³·³ÃÁ Ý»ñÏí³Í »Ý
dG ( v ) + 1 ѳçáñ¹³Ï³Ý ·áõÛÝ»ñáí, áñï»Õ dG ( v ) -áí Ý߳ݳÏí³Í ¿ v ·³·³ÃÇ ³ëïÇ׳ÝÁ
G ·ñ³ýáõÙ: ²Ûë ³ß˳ï³ÝùáõÙ ³å³óáõóíáõÙ ¿, áñ Ûáõñ³ù³ÝãÛáõñ ÏáÕÙáõÙ ÙǨÝáõÛÝ
ù³Ý³ÏÇ ·³·³ÃÝ»ñ å³ñáõݳÏáÕ ÉñÇí µ³½Ù³ÏáÕÙ³ÝÇ ·ñ³ýÝ»ñÝ áõÝ»Ý ÙÇç³Ï³Ûù³ÛÇÝ
Édzϳï³ñ Ý»ñÏáõÙ: ²í»ÉÇÝ, ³ß˳ï³ÝùáõÙ ïñíáõÙ »Ý áñáß ·Ý³Ñ³ï³Ï³ÝÝ»ñ ³Ûë
·ñ³ýÝ»ñÇ ÙÇç³Ï³Ûù³ÛÇÝ Édzϳï³ñ Ý»ñÏáõÙÝ»ñáõÙ Ù³ëݳÏóáÕ ·áõÛÝ»ñÇ Ýí³½³·áõÛÝ
¨ ³é³í»É³·áõÛÝ Ñݳñ³íáñ ÃíÇ Ñ³Ù³ñ: ²ß˳ï³ÝùáõÙ áõëáõÙݳëÇñíáõÙ »Ý ݳ¨
Qn ÑÇå»ñËáñ³Ý³ñ¹Ý»ñÇ ÙÇç³Ï³Ûù³ÛÇÝ Édzϳï³ñ Ý»ñÏáõÙÝ»ñ: سëݳíáñ³å»ë,
³å³óáõóíáõÙ ¿, áñ Qn (n ¸ 3 ) ÑÇå»ñËáñ³Ý³ñ¹Ý áõÝÇ ÙÇç³Ï³Ûù³ÛÇÝ Édzϳï³ñ t–
Ý»ñÏáõÙ ³ÛÝ ¨ ÙdzÛÝ ³ÛÝ ¹»åùáõÙ, »ñµ n + 1 · t · (n+1)(n+2)

2



4 2 Interval Total Colorings of Complete Multipartite Graphs and Hypercubes

Èíòåðâàëüíûå òîòàëüíûå ðàñêðàñêè ïîëíûx
ìíîãîäîëüíûx ãðàôîâ è ãèïåðêóáîâ

Ï. Ïåòðîñÿí è Í. Xà÷àòðÿí

Àííîòàöèÿ

Òîòàëüíîé ðàñêðàñêîé ãðàôà G íàçîâåì òàêóþ ðàñêðàñêó âåðøèí è ðåáåð
ãðàôà G, ïðè êîòîðîé ñìåæíûå âåðøèíû, ñìåæíûå ðåáðà è âåðøèíû,
èíöèäåíòíûå ðåáðàì, îêðàøåíû â ðàçëè÷íûå öâåòà. Èíòåðâàëüíîé òîòàëüíîé
t– ðàñêðàñêîé ãðàôà G íàçîâåì òîòàëüíóþ ðàñêðàñêó ãðàôà G â öâåòà 1 ; : : : ; t
ïðè êîòîðîé âñå öâåòà èñïîëüçîâàíû, è ðåáðà, èíöèäåíòíûå êàæäîé âåðøèíå
v âìåñòå ñ v, îêðàøåíû â dG ( v ) + 1 ïîñëåäîâàòåëüíûx öâåòîâ, ãäå dG ( v ) -
ýòî ñòåïåíü âåðøèíû v â ãðàôå G. Â íàñòîÿùåé ðàáîòå äîêàçàíî, ÷òî âñå
ïîëíûå ìíîãîäîëüíûå ãðàôû ñ îäèíàêîâûì êîëè÷åñòâîì âåðøèí â êàæäîé äîëå
èìåþò èíòåðâàëüíóþ òîòàëüíóþ ðàñêðàñêó. Êðîìå òîãî, ïîëó÷åíû íåêîòîðûå
îöåíêè íàèìåíüøåãî è íàèáîëüøåãî âîçìîæíîãî ÷èñëà öâåòîâ â èíòåðâàëüíûõ
òîòàëüíûõ ðàñêðàñêàõ ýòèõ ãðàôîâ. Â ðàáîòå òàêæå èññëåäîâàíû èíòåðâàëüíûå
òîòàëüíûå ðàñêðàñêè ãèïåðêóáîâ Qn.  ÷àñòíîñòè, äîêàçàíî, ÷òî ãèïåðêóá Qn
(n ¸ 3 ) èìååò èíòåðâàëüíóþ òîòàëüíóþ ðàñêðàñêó òîãäà è òîëüêî òîãäà, êîãäà
n + 1 · t · (n+1)(n+2)

2
.