# MuLan: A Joint Embedding of Music Audio and Natural Language

###### Abstract

Music tagging and content-based retrieval systems have traditionally been
constructed using pre-defined ontologies covering a rigid set of music
attributes or text queries. This paper presents MuLan: a first attempt at a
new generation of acoustic models that link music audio directly to
unconstrained natural language music descriptions. MuLan takes the form of a
two-tower, joint audio-text embedding model trained using 44 million music
recordings (370K hours) and weakly-associated, free-form text annotations.
Through its compatibility with a wide range of music genres and text styles
(including conventional music tags), the resulting audio-text representation
subsumes existing ontologies while graduating to true zero-shot
functionalities. We demonstrate the versatility of the MuLan embeddings with a
range of experiments including transfer learning, zero-shot music tagging,
language understanding in the music domain, and cross-modal retrieval
applications.

##  1 Introduction

Classifiers are generally trained to label examples with predefined and fixed
class inventories, which are often manually specified as a structured ontology
indicating inter-class relationships. Empowered by recent advances in neural
language modeling and their demonstrated transfer learning competence,
researchers have begun exploring less restrictive natural language interfaces
to access the categorical information underlying raw content signals. The
majority of this work has been in the visual and audio event domain, where a
recent series of studies have demonstrated the utility of jointly embedding
media content with natural language captions [1, 2, 3, 4, 5]. These joint
embeddings have demonstrated strong capabilities in a range of applications,
including transfer learning, cross-modal retrieval, automatic captioning, and
zero-shot classification.

The success of these efforts strongly depends on large-scale training
resources and hefty neural network architectures that are flexible enough to
model the complex, non-monotonic relationship between language and other
modalities. In particular, the visual domain has greatly benefited from the
availability of large amounts of captioned images available across the web
[1]. However, in the general environmental audio domain, such large-scale
audio-caption pairs are less readily available and related efforts have relied
on small captioned datasets [6, 7]. Critically, these datasets do not span the
diversity of sound-descriptive language and their success in the more
difficult zero-shot setting has been lacking [8, 9, 3].

This paper considers this task of jointly embedding audio and natural
language, but focuses specifically on the music domain. Our goal is to produce
a flexible language interface with which any musical concept can be linked to
related music audio. We face similar training data prerequisites to works
listed above. However, while general environmental audio consists of
background sounds that are unlikely to elicit unprompted description, music
audio is often a central focus. Consequently, text associated with music
videos is much more likely to relate to the underlying musical concepts that
we aim to model (e.g., genres, artists, moods, structure). Thus, our strategy
is to assemble a collection of textual annotations extracted from metadata,
comments, and playlist data and map them to a training set of over 44 million
internet music videos. As was the case with image-text model training in [1],
our text data only truly refers to the musical content in a fraction of cases.
Therefore, we also explore text pre-filtering using a text classifier
separately trained to identify music descriptions.

We use this large-scale dataset to train MuLan, a new generation of
semantically-structured music audio embedding model equipped with a natural
language interface. MuLan employs a two-tower parallel encoder architecture,
using a contrastive loss objective that elicits a shared embedding space
between music audio and text. We demonstrate that MuLan not only leads to
state-of-the-art performance in transfer learning for various music
information retrieval tasks, but also enables a range of functionalities in
cross-modal text-to-music retrieval, zero-shot music tagging, and music-domain
language understanding.

##  2 Related Work

Audio representation learning. Transfer learning using large-scale, task-
agnostic pretraining of general-purpose content representations has become a
dominant approach in several fields. Audio representation learning has been no
exception, including both general environmental audio [10, 11] and music audio
[12, 13, 14, 15]. Different pretraining mechanisms have been explored. In
supervised pretraining, an Audio Spectrogram Transformer (AST) [10],
pretrained on ImageNet [16] and AudioSet [17], achieved state-of-the-art
results in various tagging tasks. A strong early baseline for music audio
representation learning was provided in [13], using the Million Song Database
[18].

In unsupervised and self-supervised pretraining, both discriminative and
generative model approaches have been demonstrated to be successful.
Discriminative training was explored in [19, 20, 21, 22] where the models
tried to learn representations that assign higher similarity to audio segments
extracted from the same recording compared to segments from different
recordings. SSAST [11] explored similar discriminative losses, as well as
generative masked spectrogram patch modeling. It was shown in [23] that the
intermediate embedding of a generative model also provides a strong audio
representation for downstream classification. Various forms of weak
supervision, such as user interaction statistics and visual cues, have also
been examined in [24, 25, 26].

Our work focuses on developing a recipe of cross-modal supervision using an
abundance of text annotations that are weakly associated with the music audio.
We benchmark the transfer learning capabilities of the learned representations
against analogous past work, and also evaluate different audio encoder
architectures.

Cross-modal contrastive learning. Spurred by the success of using contrastive
learning to align image features and free-form natural language using large-
scale data [1, 2], tri-modal architectures were proposed in [27] and [5] where
an audio tower was introduced to the image-text model and contrastive learning
is used to enforce the cross-modal alignment. Along the same line in the audio
domain, [8] used contrastive learning to align the latent representation of
audio and associated tags. The tags come from a fixed vocabulary of size 1K
from Freesound [28], and the input to the text encoder was the multi-hot
encoded tags. Follow up work in [9] uses a pretrained, non-contextual word
embedding (Word2Vec) model to support generalization to new terms beyond the
1K tags. However, this still does not support generalization to free-form
natural language. Contrastive learning was also explored in [29] for zero-shot
audio classification, using AudioSet and ESC-50[30] data. Our method focuses
on mining a much larger scale collection of audio-text pairs specifically for
the music domain. Our data scale supports using state-of-the-art Transformer-
based audio and contextual language encoders, which led to a truly arbitrary
zero-shot music tagging and retrieval for the first time.

Music text joint embedding models. Content-based music information retrieval
requires linking the rich semantics expressible to free-form text with both
broad and fine-grained musical properties. One approach is to consider a large
number of text label classes and try to ground the semantics in music with a
multi-label classification task. In [25], a large vocabulary of 100K $n$-grams
was mined from noisy natural language text associated with music videos. Then,
a cross entropy loss was employed to train the music audio encoder, where the
softmax layer weights served as text label embeddings that were aligned with
audio features by construction. The work in [31] explored various training
tasks (classification, regression, metric learning) to align free-form text
and music audio, relying on pre-existing emotion labels to connect the
modalities.

Closest to our work is MuLaP[32], where 250K audio-caption pairs were mined
from a private production music library and used to train a multimodal
Transformer with early fusion of the two modalities. Their choice of early
fusion, as accomplished with cross-attention layers, restricts the utility of
the resulting embeddings to transfer learning applications. Critically, our
two-tower parallel encoder approach results in a joint embedding space that
provides a natural language interface to arbitrary music audio. This opens up
downstream opportunities for cross-modal retrieval, zero-shot tagging, and
language understanding.

Figure 1: Learning framework diagram.

##  3 Proposed approach

Our goal is to construct a shared embedding space for music audio and free-
form natural language text, in which proximity is predictive of shared
semantics both within and across modalities. To accomplish this, we rely on
cross-modal contrastive learning and a simple two-tower architecture. This is
a highly data-intensive endeavor, which we support by mining a large-scale
training dataset of (audio, text) pairs. We describe these components in turn
below.

###  3.1 Learning Framework

Figure 1 shows a high-level schematic of the learning framework. Each MuLan
model consists of two separate embedding networks for the audio and text input
modalities. These networks share no weights, but each terminates in
$\ell_{2}$-normalized embedding spaces with the same dimensionality, $d$. The
audio embedding network, $f:\mathbb{R}^{F\times T}\rightarrow\mathbb{R}^{d}$,
takes as input log mel spectrogram context windows with $F$ mel channels and
$T$ frames. The text embedding network,
$g:\mathcal{A}^{n}\rightarrow\mathbb{R}^{d}$ takes as input a null-padded text
token sequence of length $n$ over a token vocabulary $\mathcal{A}$.

Given a set of music recordings and the associated text elements for each
recording, we construct a cross-modal training dataset of (audio, text) pairs
as follows. For each recording, we compute an $F$-channel log mel spectrogram
and extract a collection of $T$-frame context windows. We null-pad or truncate
each associated text element to a fixed length $n$. Then, each mini-batch
$\mathcal{B}$ consists of a set of $B$ target audio-text pairs of the form
$\\{(\mathbf{x}^{(i)},\mathbf{t}^{(i)})\\}_{i=1}^{B}$. Here, each target pair
is sampled by first selecting a random recording and sample a random
spectrogram context window ${\mathbf{x}^{(i)}}\in\mathbb{R}^{F\times T}$ from
it. Next, we randomly select one of its associated text elements
${\mathbf{t}^{(i)}}\in\mathcal{A}^{n}$. This sampling scheme means that
multiple epochs are required to cover the entirety of the training audio and
all the associated text. We also experimented with concatenating multiple text
annotations for each example, but it did not generally work as well.

We train to minimize a batch-wise Contrastive Multiview Coding loss function
[33], which is a cross-modal extension of the popular InfoNCE and NT-Xent
losses [34, 35]. For each batch $\mathcal{B}$, this loss
$\mathcal{L}(\mathcal{B})$ takes the form

$\displaystyle\sum_{i=1}^{B}-\log\left[\frac{h[f({\mathbf{x}^{(i)}}),g({\mathbf{t}^{(i)}})]}{\sum\limits_{j\neq
i}h[f({\mathbf{x}^{(i)}}),g({\mathbf{t}^{(j)}})]+h[f({\mathbf{x}^{(j)}}),g({\mathbf{t}^{(i)}})]}\right],$

where $h$ is a critic function given by
$h[\mathbf{a},\mathbf{b}]=\exp(\mathbf{a}^{T}\mathbf{b}/\tau)$ for
$\mathbf{a},\mathbf{b}\in\mathbb{R}^{d}$, and $\tau\in(0,1]$ is a trainable
temperature hyperparameter. For our $\ell_{2}$-normalized embedding model
outputs, the inner product is effectively cosine similarity. The critic’s goal
is to produce a large positive value for target audio-text pairs, and a small
value close to zero for all non-target pairs constructed within the batch.
Temperature values less than one function to increase the output range of $h$.
Previous research[36, 35] demonstrated that a large batch size is beneficial
to contrastive loss optimization.

###  3.2 Audio Embedding Network

For the audio embedding tower, $f$, we consider two proven audio
architectures. Following its introduction to the audio machine learning
community [37], the _Resnet-50_ architecture has become a common and well-
performing option. It is a straightforward adaptation of the original vision
architecture: as in [37], we remove the stride of 2 in the first convolutional
layer and apply to log mel spectrograms ($F\\!=\\!64$ mel channels, 25 ms
Hanning window, 10 ms step size) treated as grayscale images. Unlike the
Resnet-50 model in [37] which operated on 0.96-second context windows, in
order to allow the modeling of longer-term musical structure, our
implementation takes as input 10-second windows (randomly selected from each
training clip), in the form of $(F\\!=\\!64)\times(T\\!=\\!1000)$ spectrogram
patches. During training, we apply SpecAugment to each spectrogram using the
parameters from [10] before passing it into the embedding network. A final
mean pooling operation is applied across time and mel channels, followed by a
linear fully connected layer with $d=128$ units, whose output is
$\ell_{2}$-normalized. We pretrain all but the final linear transform layer
via logistic regression on AudioSet [17], including all 527 classes, and
discard the final classifier layer before fine-tuning for our task.

_Audio Spectrogram Transformer_ (AST) is a port of the successful Vision
Transformer (ViT) base architecture and is currently the state-of-the-art in
the audio event classification space [10]. AST consists of a stack of 12
Transformer blocks (hidden dimension 768, 12 self-attention heads) that are
applied to a sequence of “tokens” corresponding to a flattened set of linear-
transformed $16\times 16$ (stride 10 along both axes) time-frequency patches
extracted from the $(F\\!=\\!128)\times(T\\!=\\!1000)$ log mel spectrogram
context windows. We again apply SpecAugment during training. Similar to the
Transformer-based language models, trainable positional encodings are added to
the sequence of patch tokens, and a [CLS] token is prepended to the sequence
as a summary of the contextual patch embeddings. We apply a linear fully-
connected layer with $d=128$ units and $\ell_{2}$-normalization to the final
768-dimensional encoding at the [CLS] token position, and this forms the
output of audio embedding network $f$. We warm-start training for all but the
final linear transform layer using the public AST checkpoint [10].

###  3.3 Text Embedding Network

For the text embedding model, we consider the commonly-used Bidirectional
Encoder Transformer (BERT) with base-uncased architecture [38], which consists
of a stack of 12 Transformer blocks (hidden dimension of 768 and 12 self-
attention heads). We apply the BERT wordpiece tokenizer to convert a text
input string into a sequence of tokens ($n=512$). The output of the text
embedding network is defined to be the [CLS] token embedding, linearly
transformed to the shared audio-text embedding space of dimension $d=128$ and
subsequently $\ell_{2}$-normalized. We warm-start our text embedding network
using the publicly available checkpoint [39].

###  3.4 Training Dataset Mining

To assemble a large-scale collection of (audio, text) pairs needed to train
our MuLan embedding models, we start with a collection of 50 million internet
music videos. From the soundtrack of each video, we extract a 30-second clip
starting at the 30 second mark. We then apply a pre-existing music audio
detector and discard any clip that is less than half music content. After this
filtering, we are left with approximately 44 million 30-second clips, which
amounts to nearly 370K hours of audio.

Table 1: Text annotation examples. Type | Examples
---|---
Short-form (SF) | tags like genre, mood, instrument, artist name,
| song title, album name
Long-form (LF) | ‘Hip-hop features rap with an electronic backing.’
| ‘The melody is so nostalgic and unforgettable.’
Playlist (PL) | ‘Feel-good mandopop indie’, ‘Latin workout’
| ‘Salsa for broken hearts’, ‘Piano for study’
Table 2: Statistics for text data sources. Tokens counts (in billions) are across all 44M videos. APV is the average number of text annotations (i.e. separate free-form strings) per video, including those with none. | Pre-filter | Post-filter
---|---|---
Type | Tokens (B) | APV | Tokens (B) | APV
Short-form | 31.2 | 42.9 | 5.4 | 29.6
Long-form | 30.7 | 70.7 | 0.2 | 0.4
Playlists | 2.5 | 24.3 | - | -

For each music video, we consider 3 sources of noisy text data: (i) _short-
form_ (SF) text including video titles and tags; (ii) _long-form_ (LF) text
including video descriptions and comments; and (iii) titles of 171 million
_playlists_ (PL) that are linked to the internet music videos in our dataset.
None of these text sources is guaranteed to be referring to the musical
properties of the soundtrack. In particular, comments data contains the most
noise, and can be subjective or less directly related to the music content. In
Table 1, we show examples that are indeed music-related to give the readers a
flavor of each type of text annotation.

In observance of the highly noisy text, we experimented with training MuLan
with the SF and LF text data filtered to a cleaner set of music-descriptive
annotations (PL is used unfiltered). For this, we fine-tune a pre-trained BERT
model with a binary classification task on a small curated set of 700
sentences, which are manually labeled to be music-descriptive or not. We then
apply this text classifier to filter the sentences in the LF annotations.
Separately, we apply a set of rule-based filtering heuristics to clean up the
SF annotations. Table 2 shows the size and coverage of each of these text
sources, both before and after filtering. Note that playlist titles and
filtered long-form annotations are only available for a minority of recordings
in the dataset (18M and 6.8M out of the total 44M, respectively).

We also convert AudioSet into a set of audio-text pairs, denoted below as
ASET. Specifically, we include all examples for all 527 classes, using each
label string attached to an example as an associated text annotation. This
results in a set of approximately 2 million 10-second clips for training, each
with 1.8 label annotations on average. Given the great scale imbalance of
these four different data sources, which is often at odds with their
linguistic richness and quality, we construct each mini-batch with a
prescribed set of proportions that were chosen without any optimization:
2:2:1:1 for SF:LF:PL:ASET. This means that despite its small scale, the (e.g.)
filtered LF annotations still comprise 1/3 of each mini-batch.

##  4 Experiments

We evaluate MuLan using both the Resnet-50 audio encoder (M-Resnet-50) and AST
audio encoder (M-AST). In both cases we use the BERT-base-uncased architecture
as the text encoder. We train all models for 14 epochs on the collection of
audio-text pairs mined from the 44M music recordings and the processed text
labels in all categories: AudioSet (ASET), short-form tags (SF), long-form
sentences (LF), playlist information (PL). We use the Adam optimizer with a
step decay learning rate schedule using a decay factor 0.9 applied every 40K
steps and initial values of $5\\!\times\\!10^{-5}$ for M-Resnet-50 and
$4\\!\times\\!10^{-5}$ for M-AST. The temperature parameter is initialized to
$\tau=0.1$ for all models. M-Resnet-50 is trained with a batch size of
$B=6144$ pairs, while $B=5120$ pairs were used for M-AST due to memory
limitations. Since M-AST and M-Resnet-50 show roughly similar performance in
the evaluation tasks considered, we use M-Resnet-50 throughout the text
ablation study for its better training efficiency.

###  4.1 Evaluation Tasks

####  4.1.1 Zero-shot Music Tagging

Given a music clip and a set of candidate text label tags, we define each
prediction score as the cosine similarity between the audio embedding of the
music clip and the text embedding of each tag string. The generalization
ability of the proposed method to potentially unseen target labels is achieved
through (i) the use of a contextual text encoder, which provides a flexible
prediction space, and (ii) the use of cross-modal contrastive learning to
anchor the language semantics to an audio representation.

We conduct this evaluation with two music tagging benchmarks: MagnaTagATune
(MTAT) [40] and the music related portion of AudioSet [17]. For MagnaTagATune,
we consider both the well-exercised top-50 tag set, as well as the full 188
tag set. We use standard train/validation/test partitions (note that zero-shot
experiments do not use train/validation) and report class-balanced area under
the receiver operating characteristic curve (AUC-ROC) on the test set. The
audio clips in MagnaTagATune are 29 seconds long, so we split each into 3 non-
overlapping 10-second segments and average the segment-level embeddings to get
the clip-level embedding. For AudioSet, we consider a 25-way genre tagging
task (Gen-25) as studied in [25], and a richer 141-way tagging task (Mu-141)
that includes the entire music subtree of AudioSet ontology.

It is important to note that AudioSet is included in contrastive training, and
a fraction of MTAT classes overlap with the AudioSet ontology. As a result,
AudioSet and (to lesser extent) MTAT evaluations are not strictly zero-shot
from a label exposure perspective. However, the explicit, matched AudioSet
supervision is diluted by the abundance of free-form language supervision
during MuLan training. Therefore, by comparing MuLan models and conventional
AudioSet classifiers, we can measure the cost of moving to a flexible natural
language interface that additionally supports classes outside the AudioSet
ontology.

####  4.1.2 Transfer Learning with Linear Probes

In addition to the zero-shot experiments introduced above, we also evaluate
the audio encoder as a general purpose feature extractor for downstream
tagging tasks. We again consider the two benchmarks of MagnaTagATune and
AudioSet, and use the training datasets to train an independent per-class
logistic regression layer on top of the frozen 128-dimensional audio
embeddings. We follow the same evaluation protocol of past transfer learning
studies using these datasets, allowing for a direct comparison of performance.

####  4.1.3 Music Retrieval from Text Queries

Given a music search collection and a text query, MuLan provides the ability
to retrieve the music clips that are closest to the query in the embedding
space. This evaluation is relevant to music retrieval applications, where
content features can offer finer-grained and more complete similarity
information when compared with metadata-based methods [41]. We consider a
proprietary collection of 7,000 expert-curated playlists, which do not overlap
with the playlist information used in training. Each expert-curated playlist
has a title and a description, and consists of 10-100 music recordings. The
playlist titles are usually short phrases, including a mixture of genres, sub-
genres, moods, activities, artist names, and compositional elements (e.g.
_‘Indie Pop Workout’_ , _‘Relaxing Korean Pop’_). Playlist descriptions
consist of one or more complete sentences (see pos/neg entries of "Playlist"
row of Table 3 for examples). The playlist evaluation includes approximately
100K unique recordings.

We construct two cross-modal retrieval evaluation sets from the expert-curated
playlist data, one using titles as queries and the other using descriptions.
For each dataset, we use the recordings belonging to the corresponding
playlist as the ground truth retrieval targets, and all the 100K recordings as
the pool of candidates. We report both AUC-ROC and mean average precision
(mAP). We use the same embedding averaging and cosine similarity-based scoring
mechanism as in the zero-shot tagging case. However, the playlist information
is of substantially different nature compared to the tags involved in the
music tagging benchmarks. Instead of a small vocabulary of mostly basic genres
and instruments, the playlist titles and descriptions have much finer-grained
information and are similar to queries that are presented to music search
engines.

Table 3: Text triplet evaluation examples. Eval Set |  Anchor / Positive / Negative
---|---
Ontology |  Steelpan / Sounds of a tuned percussion instrument originally constructed from steel oil drums by hammering out small patches on the head to produce separate pitches. / The sound of a musical instrument that produces sound by vibration of air in a tubular resonator in sympathy with the vibration of the player’s lips.
Playlist |  Relaxing Korean Pop / Lets make your chill mood with a collection of easy-going sounds from Korean artists. / These fun and upbeat songs from the alternative side of the pop music spectrum will keep you energized while you exercise.
Table 4: Music tagging results reported in AUC-ROC.

| AudioSet | MTAT
---|---|---
Model | Gen-25 | Mu-141 | Top-50 | All-188
(a) Zero-shot (Trained w/ ASET + SF + LF + PL)
M-AST | 0.840 | 0.909 | 0.778 | 0.776
M-Resnet-50 | 0.840 | 0.899 | 0.782 | 0.772
(b) Text ablation (using M-Resnet-50 Zero-shot) |
ASET + SF + LF | 0.839 | 0.907 | 0.760 | 0.756
ASET + SF | 0.839 | 0.885 | 0.754 | 0.747
ASET | 0.886 | 0.942 | 0.753 | 0.771
SF/LF Unfiltered | 0.845 | 0.908 | 0.774 | 0.766
(c) Linear probe |
M-AST | 0.906 | 0.942 | 0.925 | 0.953
M-Resnet-50 | 0.910 | 0.940 | 0.927 | 0.954
_Baselines:_ |  |  |  |
Hybrid [25] | 0.904 | 0.920 | 0.915 | 0.941
JukeBox [15, 23] | - | - |  0.915∗ | -
MuLaP [32] | - | - |  0.893∗ | -
CLMR [22] | - | - |  0.866∗ | -
(d) End-to-end training baselines |
AST [10] | 0.888 | 0.949 | - | -
SC-CNN [42] | - | - | 0.913∗ | -

∗ indicates that the number is brought from the original paper.

####  4.1.4 Text Triplet Classification

Compared to the conventional pre-trained BERT model, our text encoder is fine-
tuned using in-domain music data and cross-modal contrastive loss. Note that
there are no text-only training objectives. To measure whether our proposed
method deepens the text encoder’s understanding of music related text, we
directly evaluate the text embeddings with a triplet classification task. Each
triplet consists of 3 text strings of the form of (anchor, pos, neg), and it
is considered correct if pos is closer than neg to anchor in the text
embedding space. We derive two such text triplet evaluation sets. The first
uses the AudioSet ontology [17]: for each of the 141 music related classes, we
use its label string as the anchor text, its long-form description as the
positive text, and sample 5 random class’s long-form description as the
negative text to construct 5 triplets. For the second set, we sample 1,000
triplets from the expert-curated playlist data in a similar fashion: we first
sample a playlist, set the anchor and positive text to be its title and
description, respectively, and then set the negative text to be the
description of another randomly sampled playlist. Examples of both sets are
shown in Table 3.

###  4.2 Results and Discussion

####  4.2.1 Music Tagging

Table 4(a) shows the zero-shot tagging metrics, where M-Resnet-50 and M-AST
obtain comparable performance. Note that there can be a significant
misalignment between the word sense of a label in the tagging evaluation
compared to that in our training text. This can lead to a degradation in
performance relative to the explicitly supervised linear probe setting where
the task-expected tag semantics can be learned. The MTAT gap is substantially
larger than AudioSet’s, driven by particularly bad performance for (i) MTAT
tags with nonspecific meaning or multiple senses, e.g. “weird” and “beats”;
and (ii) MTAT tags involving simple negation (e.g. “not rock”, “no piano”).
This is a result of the text encoder not adequarely modeling the meaning of
these negated concepts, which is a well known problem with BERT [43, 44] (the
text embedding of “not rock” is similar to “rock” and performance suffers).

Table 4(b) shows the results of the text ablation study, which aims to
understand the benefits of different sources of text labels. Note that as we
remove each dataset we maintain the same proportions described in Section 3.4.
Unsurprisingly, training with AudioSet alone gets the highest AUC in AudioSet
evaluation, with the text encoder learning the exact label semantics reflected
in the test data. On the other hand, including more data sources in general
improves performance on all other downstream tasks (MTAT, retrieval/text
triplet evaluations in Tables 5 and 6) and the loss on AudioSet AUC is
relatively minor. We observe that for the music tagging tasks considered,
training with unfiltered data actually achieves comparable performance
compared to the filtered version. That the model learns similarly useful
associations without being overwhelmed by the sheer amount of noise in the raw
text data came as a surprise. We speculate that our text filtering was too
aggressive, having removed annotations that were not obviously music-related,
but semantically important nonetheless. Since contrastive learning is highly
noise tolerant, the gain from restricting to more strongly aligned audio-text
pairs may have been offset by the loss of a large set of additional useful
pairs.

Table 5: Text query music retrieval evaluation results. Text ablation/unfiltered models use M-Resnet-50. | Title | Description
---|---|---
Model | AUC | mAP | AUC | mAP
M-AST | 0.933 | 0.110 | 0.903 | 0.090
M-Resnet-50 | 0.931 | 0.104 | 0.901 | 0.084
_Text Ablation:_ |  |  |  |
ASET+SF+LF | 0.917 | 0.101 | 0.892 | 0.077
ASET+SF | 0.913 | 0.089 | 0.867 | 0.060
ASET | 0.626 | 0.005 | 0.688 | 0.009
_SF/LF Unfiltered_ | 0.933 | 0.111 | 0.897 | 0.081
Table 6: Text triplet classification accuracy AudioSet ontology evaluation and Playlist title to description evaluation. Text ablation/unfiltered models use M-Resnet-50. Model | Playlist | AudioSet
---|---|---
M-AST | 0.959 | 0.962
M-Resnet-50 | 0.945 | 0.951
_Text Ablation:_ |  |
ASET + SF + LF | 0.935 | 0.952
ASET + SF | 0.910 | 0.938
ASET | 0.693 | 0.818
_SF/LF Unfiltered_ | 0.949 | 0.959
_Baselines:_ |  |
SimCSE [45] | 0.950 | 0.938
SBERT [46] | 0.942 | 0.889
USE [47] | 0.918 | 0.946
BERT [38] | 0.850 | 0.847

Table 4(c) shows that when applying linear probes on MuLan audio embeddings,
we achieve SOTA transfer learning performance on all tagging tasks. This
demonstrates that MuLan’s pretrained audio encoder continues to produce high
quality general-purpose music audio embeddings, while also supporting new
natural language applications. Finally, Table 4(d) lists end-to-end training
baselines for 3 of these tasks. Our linear probe results exceed 2 of 3, and
only slightly trails a SOTA AST AudioSet classifier.

####  4.2.2 Music Retrieval from Text Queries

In Table 5, we evaluate MuLan models (including with text/filter ablation) on
the query retrieval evaluation tasks introduced in Section 4.1.3. Even though
we start with a BERT checkpoint pretrained with massive language resources,
training MuLan with only AudioSet clips and label annotations provides very
limited ability to ground in-domain natural language to music. Such limited
cross-modal supervision does not generalize to the rich semantics that appear
in the playlist titles and descriptions, which are more in line with the
complex queries that are presented to real-world music search engines. We
observe significant gain after including the large-scale short-form tags mined
from the internet, which helps the model learn to ground more fine-grained
music concepts. There is additional gain when including comments and playlist
data, where the complete sentences are helpful for grounding the more complex
queries, including multi-term queries (e.g._‘instrumental action movie
soundtrack’_), compositional queries (e.g. _‘classical music with middle
eastern influence’_), and even queries with negation (e.g. _‘hard rock without
vocals’_). Again, we find that training is surprisingly robust to annotation
noise, achieving similar performance using unfiltered training text.

####  4.2.3 Text Triplet Classification

Table 6 lists triplet classification accuracy on evaluations introduced in
Section 4.1.4. We compare MuLan text embedding against the following
baselines: Sentence Transformer [46], SimCSE [45], Universal Sentence
Embedding [47], and the average token embedding of BERT-base-uncased (this
outperforms the [CLS] encoding by a large margin). All baselines are
Transformer-based models with similar size to ours. The first three were
trained with sentence-level contrastive loss, while BERT is trained with
masked language prediction. We warmstart the MuLan text encoder using this
same BERT baseline, but it is subsequently only trained with the cross-modal
loss. We find that when including our long-form text annotations, the
resulting text embedding model, which is now specialized to the music domain,
outperforms the generic sentence embedding models. While it is not surprising
in-domain text is helpful, it is remarkable that successful specialization is
accomplished without using any text-only fine-tuning loss.

##  5 Conclusions

We presented a music audio and natural language joint embedding model trained
with an unprecedented scale of weakly paired text and audio data. Our
experiments demonstrate the versatility of the natural language interface in a
range of applications. The pretrained audio embeddings also achieve SOTA
transfer learning performance on music tagging benchmarks. This is a first
attempt at building a free-form natural language interface for music audio and
there is plenty of room for improvement. Specifically, we believe improved
text filtering methods that better distinguish weak signal from absolute noise
will result in better handling of rare and subtle language constructs.

## References

  * [1] C. Jia, Y. Yang, Y. Xia, Y.-T. Chen, Z. Parekh, H. Pham, Q. Le, Y.-H. Sung, Z. Li, and T. Duerig, “Scaling up visual and vision-language representation learning with noisy text supervision,” in _Proc. of the International Conference on Machine Learning (ICML)_ , 2021.
  * [2] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark _et al._ , “Learning transferable visual models from natural language supervision,” in _Proc. of the International Conference on Machine Learning (ICML)_ , 2021.
  * [3] A. S. Koepke, A.-M. Oncescu, J. Henriques, Z. Akata, and S. Albanie, “Audio retrieval with natural language queries: A benchmark study,” _IEEE Transactions on Multimedia_ , 2022.
  * [4] K. Kilgour, B. Gfeller, Q. Huang, A. Jansen, S. Wisdom, and M. Tagliasacchi, “Text-driven separation of arbitrary sounds,” _arXiv:2204.05738_ , 2022\.
  * [5] A. Nagrani, P. H. Seo, B. Seybold, A. Hauth, S. Manen, C. Sun, and C. Schmid, “Learning audio-video modalities from image captions,” _arXiv:2204.00679_ , 2022.
  * [6] K. Drossos, S. Lipping, and T. Virtanen, “Clotho: An audio captioning dataset,” in _Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2020.
  * [7] C. D. Kim, B. Kim, H. Lee, and G. Kim, “AudioCaps: Generating captions for audios in the wild,” in _Proc. of the Conference of the North American Chapter of the Association for Computational Linguistics (NAACL): Human Language Technologies_ , 2019.
  * [8] X. Favory, K. Drossos, T. Virtanen, and X. Serra, “COALA: Co-aligned autoencoders for learning semantically enriched audio representations,” _arXiv:2006.08386_ , 2020.
  * [9] ——, “Learning contextual tag embeddings for cross-modal alignment of audio and tags,” in _Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2021.
  * [10] Y. Gong, Y.-A. Chung, and J. Glass, “AST: Audio spectrogram transformer,” _arXiv:2104.01778_ , 2021.
  * [11] Y. Gong, C.-I. J. Lai, Y.-A. Chung, and J. Glass, “SSAST: Self-supervised audio spectrogram transformer,” _arXiv:2110.09784_ , 2021.
  * [12] P. Hamel, M. E. Davies, K. Yoshii, and M. Goto, “Transfer learning in MIR: Sharing learned latent representations for music audio classification and similarity,” in _Proc. of International Conference on Music Information Retrieval (ISMIR)_ , 2013.
  * [13] A. Van Den Oord, S. Dieleman, and B. Schrauwen, “Transfer learning by supervised pre-training for audio-based music classification,” in _Proc. of International Conference on Music Information Retrieval (ISMIR)_ , 2014.
  * [14] K. Choi, G. Fazekas, M. Sandler, and K. Cho, “Transfer learning for music classification and regression tasks,” in _Proc. of International Conference on Music Information Retrieval (ISMIR)_ , 2017.
  * [15] P. Dhariwal, H. Jun, C. Payne, J. W. Kim, A. Radford, and I. Sutskever, “Jukebox: A generative model for music,” _arXiv:2005.00341_ , 2020.
  * [16] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “ImageNet: A large-scale hierarchical image database,” in _Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2009.
  * [17] J. F. Gemmeke, D. P. Ellis, D. Freedman, A. Jansen, W. Lawrence, R. C. Moore, M. Plakal, and M. Ritter, “AudioSet: An ontology and human-labeled dataset for audio events,” in _Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2017.
  * [18] T. Bertin-Mahieux, D. P. Ellis, B. Whitman, and P. Lamere, “The million song dataset,” in _Proc. of International Conference on Music Information Retrieval (ISMIR)_ , 2011.
  * [19] A. Jansen, M. Plakal, R. Pandya, D. P. Ellis, S. Hershey, J. Liu, R. C. Moore, and R. A. Saurous, “Unsupervised learning of semantic audio representations,” in _Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2018.
  * [20] A. Saeed, D. Grangier, and N. Zeghidour, “Contrastive learning of general-purpose audio representations,” in _Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2021.
  * [21] N. Turpault, R. Serizel, and E. Vincent, “Semi-supervised triplet loss based learning of ambient audio embeddings,” in _Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2019.
  * [22] J. Spijkervet and J. A. Burgoyne, “Contrastive learning of musical representations,” _arXiv:2103.09410_ , 2021.
  * [23] R. Castellon, C. Donahue, and P. Liang, “Codified audio language modeling learns useful representations for music information retrieval,” in _Proc. of International Conference on Music Information Retrieval (ISMIR)_ , 2021.
  * [24] S. Oramas, O. Nieto, F. Barbieri, and X. Serra, “Multi-label music genre classification from audio, text, and images using deep features,” in _Proc. of International Conference on Music Information Retrieval (ISMIR)_ , 2017.
  * [25] Q. Huang, A. Jansen, L. Zhang, D. P. Ellis, R. A. Saurous, and J. Anderson, “Large-scale weakly-supervised content embeddings for music recommendation and tagging,” in _Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2020.
  * [26] A. Ferraro, X. Favory, K. Drossos, Y. Kim, and D. Bogdanov, “Enriched music representations with multiple cross-modal contrastive learning,” _IEEE Signal Processing Letters_ , vol. 28, pp. 733–737, 2021.
  * [27] A. Guzhov, F. Raue, J. Hees, and A. Dengel, “Audioclip: Extending CLIP to image, text and audio,” in _Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2022.
  * [28] F. Font, G. Roma, and X. Serra, “Freesound technical demo,” in _Proc. of the ACM International conference on Multimedia (MM)_ , 2013.
  * [29] H. Xie and T. Virtanen, “Zero-shot audio classification via semantic embeddings,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 29, pp. 1233–1242, 2021.
  * [30] K. J. Piczak, “ESC: Dataset for environmental sound classification,” in _Proc. of the ACM International Conference on Multimedia (MM)_ , 2015.
  * [31] M. Won, J. Salamon, N. J. Bryan, G. J. Mysore, and X. Serra, “Emotion embedding spaces for matching music to stories,” in _Proc. of International Conference on Music Information Retrieval (ISMIR)_ , 2021.
  * [32] I. Manco, E. Benetos, E. Quinton, and G. Fazekas, “Learning music audio representations via weak language supervision,” in _Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2022.
  * [33] Y. Tian, D. Krishnan, and P. Isola, “Contrastive multiview coding,” in _Proc. of European Conference on Computer Vision (ECCV)_ , 2020.
  * [34] A. v. d. Oord, Y. Li, and O. Vinyals, “Representation learning with contrastive predictive coding,” _arXiv:1807.03748_ , 2018.
  * [35] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, “A simple framework for contrastive learning of visual representations,” in _Proc. of International Conference on Machine Learning (ICML)_ , 2020.
  * [36] H. Lee, J. Lee, J. Y.-H. Ng, and P. Natsev, “Large scale video representation learning via relational graph clustering,” in _Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * [37] S. Hershey, S. Chaudhuri, D. P. Ellis, J. F. Gemmeke, A. Jansen, R. C. Moore, M. Plakal, D. Platt, R. A. Saurous, B. Seybold _et al._ , “CNN architectures for large-scale audio classification,” in _Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2017.
  * [38] M.-W. C. Kenton, Jacob Devlin and L. K. Toutanova, “BERT: Pre-training of deep bidirectional transformers for language understanding,” in _Proceedings of NAACL-HLT_ , 2019, pp. 4171–4186.
  * [39] TensorflowHub, “https://tfhub.dev/tensorflow/bert_en_uncased_L-12_H-768_A-12/4,” 2022\.
  * [40] E. Law and L. Von Ahn, “Input-agreement: a new mechanism for collecting data using human computation games,” in _Proc. of the ACM SIGCHI Conference on Human Factors in Computing Systems_ , 2009.
  * [41] R. Typke, F. Wiering, R. C. Veltkamp, J. D. Reiss, G. A. Wiggins _et al._ , “A survey of music information retrieval systems,” in _Proc. of International Conference on Music Information Retrieval (ISMIR)_ , 2005.
  * [42] M. Won, A. Ferraro, D. Bogdanov, and X. Serra, “Evaluation of cnn-based automatic music tagging models,” _arXiv:2006.00751_ , 2020.
  * [43] A. Ettinger, “What BERT is not: Lessons from a new suite of psycholinguistic diagnostics for language models,” _Transactions of the Association for Computational Linguistics_ , vol. 8, pp. 34–48, 2020.
  * [44] G. N. C. Tejada, J. Scholtes, and G. Spanakis, “A study of BERT’s processing of negations to determine sentiment,” in _Proc. of the Benelux Conference on Artificial Intelligence and Belgian-Dutch Conference on Machine Learning_ , 2021.
  * [45] T. Gao, X. Yao, and D. Chen, “SimCSE: Simple contrastive learning of sentence embeddings,” in _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , 2021, pp. 6894–6910.
  * [46] N. Reimers and I. Gurevych, “Sentence-BERT: Sentence embeddings using siamese bert-networks,” in _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , 2019, pp. 3982–3992.
  * [47] D. Cer, Y. Yang, S.-y. Kong, N. Hua, N. Limtiaco, R. S. John, N. Constant, M. Guajardo-Cespedes, S. Yuan, C. Tar _et al._ , “Universal sentence encoder,” _arXiv:1803.11175_ , 2018.


$Id:espcrc1.tex,v1.22004/02/2411:22:11speppingExp$ Interval edge-colorings of
Cartesian products of graphs I Petros A. Petrosyan, Hrant H. Khachatrian and
Hovhannes G. Tananyan

# Interval edge-colorings of Cartesian products of graphs I

Petros A. Petrosyan, Hrant H. Khachatrian[MCSD], Hovhannes G. Tananyan email:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Department of Informatics and Applied Mathematics,
Yerevan State University, 0025, Armenia  Institute for Informatics and
Automation Problems,
National Academy of Sciences, 0014, Armenia  Department of Applied Mathematics
and Informatics,
Russian-Armenian State University, 0051, Armenia

###### Abstract

An edge-coloring of a graph $G$ with colors $1,\ldots,t$ is an interval
$t$-coloring if all colors are used, and the colors of edges incident to each
vertex of $G$ are distinct and form an interval of integers. A graph $G$ is
interval colorable if $G$ has an interval $t$-coloring for some positive
integer $t$. Let $\mathfrak{N}$ be the set of all interval colorable graphs.
For a graph $G\in\mathfrak{N}$, the least and the greatest values of $t$ for
which $G$ has an interval $t$-coloring are denoted by $w(G)$ and $W(G)$,
respectively. In this paper we first show that if $G$ is an $r$-regular graph
and $G\in\mathfrak{N}$, then $W(G\square P_{m})\geq W(G)+W(P_{m})+(m-1)r$
($m\in\mathbb{N}$) and $W(G\square C_{2n})\geq W(G)+W(C_{2n})+nr$ ($n\geq 2$).
Next, we investigate interval edge-colorings of grids, cylinders and tori. In
particular, we prove that if $G\square H$ is planar and both factors have at
least $3$ vertices, then $G\square H\in\mathfrak{N}$ and $w(G\square H)\leq
6$. Finally, we confirm the first author’s conjecture on the $n$-dimensional
cube $Q_{n}$ and show that $Q_{n}$ has an interval $t$-coloring if and only if
$n\leq t\leq\frac{n\left(n+1\right)}{2}$.

Keywords: edge-coloring, interval coloring, grid, cylinder, torus,
$n$-dimensional cube

AMS Subject Classification: 05C15, 05C76

##  1 Introduction

An edge-coloring of a graph $G$ with colors $1,\ldots,t$ is an interval
$t$-coloring if all colors are used, and the colors of edges incident to each
vertex of $G$ are distinct and form an interval of integers. A graph $G$ is
interval colorable if $G$ has an interval $t$-coloring for some positive
integer $t$. Let $\mathfrak{N}$ be the set of all interval colorable graphs
[1, 14]. For a graph $G\in\mathfrak{N}$, the least and the greatest values of
$t$ for which $G$ has an interval $t$-coloring are denoted by $w(G)$ and
$W(G)$, respectively. The concept of interval edge-coloring was introduced by
Asratian and Kamalian [1]. In [1], they proved the following:

###### Theorem 1

If $G$ is a regular graph, then

(1)

$G\in\mathfrak{N}$ if and only if $\chi^{\prime}(G)=\Delta(G)$.

(2)

If $G\in\mathfrak{N}$ and $w(G)\leq t\leq W(G)$, then $G$ has an interval
$t$-coloring.

In [2], Asratian and Kamalian investigated interval edge-colorings of
connected graphs. In particular, they obtained the following two results.

###### Theorem 2

If $G$ is a connected graph and $G\in\mathfrak{N}$, then

$W(G)\leq\left(\mathrm{diam}(G)+1\right)\left(\Delta(G)-1\right)+1$.

###### Theorem 3

If $G$ is a connected bipartite graph and $G\in\mathfrak{N}$, then

$W(G)\leq\mathrm{diam}(G)\left(\Delta(G)-1\right)+1$.

Recently, Kamalian and Petrosyan [16] showed that these upper bounds cannot be
significantly improved.

In [13], Kamalian investigated interval colorings of complete bipartite graphs
and trees. In particular, he proved the following:

###### Theorem 4

For any $r,s\in\mathbb{N}$, the complete bipartite graph $K_{r,s}$ is interval
colorable, and

(1)

$w\left(K_{r,s}\right)=r+s-\gcd(r,s)$,

(2)

$W\left(K_{r,s}\right)=r+s-1$,

(3)

if $w\left(K_{r,s}\right)\leq t\leq W\left(K_{r,s}\right)$, then $K_{r,s}$ has
an interval $t$-coloring.

In [21], Petrosyan investigated interval colorings of complete graphs and
$n$-dimensional cubes. In particular, he obtained the following two results.

###### Theorem 5

If $n=p2^{q}$, where $p$ is odd and $q$ is nonnegative, then

$W\left(K_{2n}\right)\geq 4n-2-p-q$.

###### Theorem 6

$W\left(Q_{n}\right)\geq\frac{n(n+1)}{2}$ for any $n\in\mathbb{N}$.

The $NP$-completeness of the problem of the existence of an interval edge-
coloring of an arbitrary bipartite graph was shown in [24]. A similar result
for regular graphs was obtained in [1, 2]. In [19, 22, 23], interval edge-
colorings of various products of graphs were investigated. Some interesting
results on interval colorings were also obtained in [3, 4, 6, 7, 8, 9, 10, 14,
15, 16, 17, 18, 19, 20]. Surveys on this topic can be found in some books [3,
12, 19].

In this paper we focus only on interval edge-colorings of Cartesian products
of graphs.

##  2 Notations, definitions and auxiliary results

Throughout this paper all graphs are finite, undirected, and have no loops or
multiple edges. Let $V(G)$ and $E(G)$ denote the sets of vertices and edges of
$G$, respectively. The degree of a vertex $v$ in $G$ is denoted by $d_{G}(v)$,
the maximum degree of $G$ by $\Delta(G)$, and the chromatic index of $G$ by
$\chi^{\prime}(G)$. If $G$ is a connected graph, then the distance between two
vertices $u$ and $v$ in $G$, we denote by $d(u,v)$, and the diameter of $G$ by
$\mathrm{diam}(G)$. We use the standard notations $P_{n}$, $C_{n}$, $K_{n}$
and $Q_{n}$ for the simple path, simple cycle, complete graph on vertices and
the $n$-dimensional cube, respectively. A partial edge-coloring of a graph $G$
is a coloring of some of the edges of $G$ such that no two adjacent edges
receive the same color. If $\alpha$ is a partial edge-coloring of $G$ and
$v\in V(G)$, then $S\left(v,\alpha\right)$ denotes the set of colors appearing
on colored edges incident to $v$.

Let $[t]$ denote the set of the first $t$ natural numbers. Let $\left\lfloor
a\right\rfloor$ ($\left\lceil a\right\rceil$) denote the largest (least)
integer less (greater) than or equal to $a$. For two positive integers $a$ and
$b$ with $a\leq b$, the set $\left\\{a,\ldots,b\right\\}$ is denoted by
$\left[a,b\right]$. The terms and concepts that we do not define can be found
in [25].

Let $G$ and $H$ be graphs. The Cartesian product $G\square H$ is defined as
follows:

$V(G\square H)=V(G)\times V(H)$,

$E(G\square
H)=\\{(u_{1},v_{1})(u_{2},v_{2})\colon\,u_{1}=u_{2}~{}and~{}v_{1}v_{2}\in
E(H)~{}or~{}v_{1}=v_{2}~{}and~{}u_{1}u_{2}\in E(G)\\}$.

Clearly, if $G$ and $H$ are connected graphs, then $G\square H$ is connected,
too. Moreover, $\Delta(G\square H)=\Delta(G)+\Delta(H)$ and
$\mathrm{diam}(G\square H)=\mathrm{diam}(G)+\mathrm{diam}(H)$. The
$k$-dimensional grid $G(n_{1},n_{2},\ldots,n_{k})$, $n_{i}\in\mathbb{N}$ is
the Cartesian product of paths $P_{n_{1}}\square P_{n_{2}}\square\cdots\square
P_{n_{k}}$. The cylinder $C(n_{1},n_{2})$ is the Cartesian product
$P_{n_{1}}\square C_{n_{2}}$, and the torus $T(n_{1},n_{2})$ is the Cartesian
product of cycles $C_{n_{1}}\square C_{n_{2}}$.

We also need the following two lemmas.

###### Lemma 7

If $\alpha$ is an edge-coloring of a connected graph $G$ with colors
$1,\ldots,t$ such that the edges incident to each vertex $v\in V(G)$ are
colored by distinct and consecutive colors, and $\min_{e\in
E(G)}\\{\alpha(e)\\}=1$, $\max_{e\in E(G)}\\{\alpha(e)\\}=t$, then $\alpha$ is
an interval $t$-coloring of $G$.

  * Proof.

For the proof of the lemma, it suffices to show that all colors are used in
the coloring $\alpha$ of $G$.

Let $u$ and $w$ be vertices such that $1\in S(u,\alpha)$ and $t\in
S(w,\alpha)$. Also, let $P=v_{1},\ldots,v_{k}$, where $u=v_{1}$ and $v_{k}=w$
be a $u,w$-path in $G$. If $k=1$, then $t\in S(u,\alpha)$ and all colors
appear on edges incident to $u$. Assume that $k\geq 2$. The sets
$S(v_{i},\alpha)$ for $v_{i}\in V(P)$ are intervals, and for $2\leq i\leq k$,
intervals $S(v_{i-1},\alpha)$ and $S(v_{i},\alpha)$ share a color. Thus, the
sets $S(v_{1},\alpha),\ldots,S(v_{k},\alpha)$ cover $[1,t]$. $\square$

The next lemma was proved by Behzad and Mahmoodian in [5].

###### Lemma 8

If both $G$ and $H$ have at least $3$ vertices, then the Cartesian product
$G\square H$ is planar if and only if $G\square H=G(m,n)$ or $G\square
H=C(m,n)$.

##  3 The Cartesian product of regular graphs

Interval edge-colorings of Cartesian products of graphs were first
investigated by Giaro and Kubale in [7], where they proved the following:

###### Theorem 9

If $G\in\mathfrak{N}$, then $G\square P_{m}\in\mathfrak{N}$ $(m\in\mathbb{N})$
and $G\square C_{2n}\in\mathfrak{N}$ $(n\geq 2)$.

It is well-known that $P_{m},C_{2n}\in\mathfrak{N}$ and
$W\left(P_{m}\right)=m-1$, $W\left(C_{2n}\right)=n+1$ for $m\in\mathbb{N}$ and
$n\geq 2$. Later, Giaro and Kubale [9, 19] proved a more general result.

###### Theorem 10

If $G,H\in\mathfrak{N}$, then $G\square H\in\mathfrak{N}$. Moreover,
$w(G\square H)\leq w(G)+w(H)$ and $W(G\square H)\geq W(G)+W(H)$.

Let us note that if $G\in\mathfrak{N}$ and $H=P_{m}$ or $H=C_{2n}$, then, by
Theorem 10, we obtain $w(G\square H)\leq w(G)+2$ and $W(G\square P_{m})\geq
W(G)+m-1$, $W(G\square C_{2n})\geq W(G)+n+1$. Now we improve the lower bound
in Theorem 10 for $W\left(G\square P_{m}\right)$ and $W\left(G\square
C_{2n}\right)$ when $G$ is a regular graph and $G\in\mathfrak{N}$. More
precisely, we show that the following two theorems hold.

###### Theorem 11

If $G$ is an $r$-regular graph and $G\in\mathfrak{N}$, then $G\square
P_{m}\in\mathfrak{N}$ $(m\in\mathbb{N})$ and $W\left(G\square P_{m}\right)\geq
W(G)+W\left(P_{m}\right)+(m-1)r$.

  * Proof.

For the proof, we construct an edge-coloring of the graph $G\square P_{m}$
that satisfies the specified conditions.

Let $V(G)=\left\\{v_{1},\ldots,v_{n}\right\\}$ and $V\left(G\square
P_{m}\right)=\bigcup_{i=1}^{m}V^{i}$, where
$V^{i}=\left\\{v_{j}^{(i)}\colon\,1\leq j\leq n\right\\}$. Also, let
$E\left(G\square
P_{m}\right)=\bigcup_{i=1}^{m}E^{i}\cup\bigcup_{j=1}^{n}E_{j}$, where

$E^{i}=\left\\{v_{j}^{(i)}v_{k}^{(i)}\colon\,v_{j}v_{k}\in E(G)\right\\}$ and
$E_{j}=\left\\{v_{j}^{(i)}v_{j}^{(i+1)}\colon\,1\leq i\leq m-1\right\\}$.

For $1\leq i\leq m$, define a subgraph $G^{i}$ of the graph $G\square P_{m}$
as follows: $G^{i}=\left(V^{i},E^{i}\right)$. Clearly, $G^{i}$ is isomorphic
to $G$ for $1\leq i\leq m$. Since $G\in\mathfrak{N}$, there exists an interval
$W(G)$-coloring $\alpha$ of $G$. Now we define an edge-coloring $\beta$ of the
subgraphs $G^{1},\ldots,G^{m}$.

For $1\leq i\leq m$ and for every edge $v_{j}^{(i)}v_{k}^{(i)}\in E(G^{i})$,
let

$\beta\left(v_{j}^{(i)}v_{k}^{(i)}\right)=\alpha(v_{j}v_{k})+(i-1)(r+1)$.

It is easy to see that the color of each edge of the subgraph $G^{i}$ is
obtained by shifting the color of the associated edge of $G$ by $(i-1)(r+1)$,
thus the set $S\left(v_{j}^{(i)},\beta\right)$ is an interval for each vertex
$v_{j}^{(i)}\in V(G^{i})$, where $1\leq i\leq m$, $1\leq j\leq n$. Now we
define an edge-coloring $\gamma$ of the graph $G\square P_{m}$.

For every $e\in E\left(G\square P_{m}\right)$, let

$\gamma(e)=\left\\{\begin{tabular}[]{ll}$\beta(e)$,&if $e\in E(G^{i}),$\\\
$\max S\left(v_{j}^{(i)},\beta\right)+1$,&if $e=v_{j}^{(i)}v_{j}^{(i+1)}\in
E_{j}$,\\\ \end{tabular}\right.$

where $1\leq i\leq m,1\leq j\leq n$.

Let us prove that $\gamma$ is an interval
$\left(W(G)+W\left(P_{m}\right)+(m-1)r\right)$-coloring of the graph $G\square
P_{m}$ for $m\in\mathbb{N}$.

First we show that the set $S\left(v_{j}^{(i)},\gamma\right)$ is an interval
for each vertex $v_{j}^{(i)}\in V\left(G\square P_{m}\right)$, where $1\leq
i\leq m,1\leq j\leq n$.

Case 1: $i=1$, $1\leq j\leq n$.

By the definition of $\gamma$ and taking into account that $\max
S\left(v_{j},\alpha\right)-\min S\left(v_{j},\alpha\right)=r-1$ for $1\leq
j\leq n$, we have

$\displaystyle S\left(v_{j}^{(1)},\gamma\right)$ $\displaystyle=$
$\displaystyle\left\\{\min S\left(v_{j},\alpha\right),\ldots,\max
S\left(v_{j},\alpha\right)\right\\}\cup\left\\{\max
S\left(v_{j},\alpha\right)+1\right\\}$ $\displaystyle=$ $\displaystyle[\min
S\left(v_{j},\alpha\right),\max S\left(v_{j},\alpha\right)+1].$

Case 2: $2\leq i\leq m-1$, $1\leq j\leq n$.

By the definition of $\gamma$ and taking into account that $\max
S\left(v_{j},\alpha\right)-\min S\left(v_{j},\alpha\right)=r-1$ for $1\leq
j\leq n$, we have

$\displaystyle S\left(v_{j}^{(i)},\gamma\right)$ $\displaystyle=$
$\displaystyle\left\\{\min S\left(v_{j},\alpha\right)+(i-1)(r+1),\ldots,\max
S\left(v_{j},\alpha\right)+(i-1)(r+1)\right\\}$ $\displaystyle\cup\left\\{\max
S\left(v_{j},\alpha\right)+(i-2)(r+1)+1\right\\}\cup\left\\{\max
S\left(v_{j},\alpha\right)+(i-1)(r+1)+1\right\\}$ $\displaystyle=$
$\displaystyle\left\\{\min S\left(v_{j},\alpha\right)+(i-1)(r+1),\ldots,\max
S\left(v_{j},\alpha\right)+(i-1)(r+1)+1\right\\}$
$\displaystyle\cup\left\\{\max
S\left(v_{j},\alpha\right)+(i-2)(r+1)+1\right\\}$ $\displaystyle=$
$\displaystyle\left\\{\min S\left(v_{j},\alpha\right)+(i-1)(r+1)-1,\ldots,\max
S\left(v_{j},\alpha\right)+(i-1)(r+1)+1\right\\}$ $\displaystyle=$
$\displaystyle[\min S\left(v_{j},\alpha\right)+(i-1)(r+1)-1,\max
S\left(v_{j},\alpha\right)+(i-1)(r+1)+1].$

Case 3: $i=m$, $1\leq j\leq n$.

By the definition of $\gamma$ and taking into account that $\max
S\left(v_{j},\alpha\right)-\min S\left(v_{j},\alpha\right)=r-1$ for $1\leq
j\leq n$, we have

$\displaystyle S\left(v_{j}^{(m)},\gamma\right)$ $\displaystyle=$
$\displaystyle\left\\{\min S\left(v_{j},\alpha\right)+(m-1)(r+1),\ldots,\max
S\left(v_{j},\alpha\right)+(m-1)(r+1)\right\\}$ $\displaystyle\cup\left\\{\max
S\left(v_{j},\alpha\right)+(m-2)(r+1)+1\right\\}$ $\displaystyle=$
$\displaystyle\left\\{\min S\left(v_{j},\alpha\right)+(m-1)(r+1)-1,\ldots,\max
S\left(v_{j},\alpha\right)+(m-1)(r+1)\right\\}$ $\displaystyle=$
$\displaystyle[\min S\left(v_{j},\alpha\right)+(m-1)(r+1)-1,\max
S\left(v_{j},\alpha\right)+(m-1)(r+1)].$

Next we prove that in the coloring $\gamma$ all colors are used. Clearly,
there exists an edge $v_{j_{0}}^{(1)}v_{k_{0}}^{(1)}\in E(G^{1})$ such that
$\gamma\left(v_{j_{0}}^{(1)}v_{k_{0}}^{(1)}\right)=1$, since in the coloring
$\alpha$ there exists an edge $v_{j_{0}}v_{k_{0}}$ with
$\alpha\left(v_{j_{0}}v_{k_{0}}\right)=1$ and
$\gamma\left(v_{j_{0}}^{(1)}v_{k_{0}}^{(1)}\right)=\beta\left(v_{j_{0}}^{(1)}v_{k_{0}}^{(1)}\right)=\alpha\left(v_{j_{0}}v_{k_{0}}\right)$.
Similarly, there exists an edge $v_{j_{1}}^{(m)}v_{k_{1}}^{(m)}\in E(G^{m})$
such that
$\gamma\left(v_{j_{1}}^{(m)}v_{k_{1}}^{(m)}\right)=W(G)+(m-1)(r+1)=W(G)+W\left(P_{m}\right)+(m-1)r$,
since in the coloring $\alpha$ there exists an edge $v_{j_{1}}v_{k_{1}}$ with
$\alpha\left(v_{j_{1}}v_{k_{1}}\right)=W(G)$ and
$\gamma\left(v_{j_{1}}^{(m)}v_{k_{1}}^{(m)}\right)=\beta\left(v_{j_{1}}^{(m)}v_{k_{1}}^{(m)}\right)=\alpha\left(v_{j_{1}}v_{k_{1}}\right)+(m-1)(r+1)$.
Now, by Lemma 7, we have that for each
$t\in[W(G)+W\left(P_{m}\right)+(m-1)r]$, there is an edge $e\in
E\left(G\square P_{m}\right)$ with $\gamma(e)=t$.

This shows that $\gamma$ is an interval
$\left(W(G)+W\left(P_{m}\right)+(m-1)r\right)$-coloring of the graph $G\square
P_{m}$ for $m\in\mathbb{N}$. Thus, $G\square P_{m}\in\mathfrak{N}$ and
$W\left(G\square P_{m}\right)\geq W(G)+W\left(P_{m}\right)+(m-1)r$. $\square$

###### Corollary 12

If $G$ is an $r$-regular graph and $G\in\mathfrak{N}$, then $G\square
Q_{n}\in\mathfrak{N}$ $(n\in\mathbb{N})$ and

$W\left(G\square Q_{n}\right)\geq W(G)+\frac{n(n+2r+1)}{2}$.

###### Theorem 13

If $G$ is an $r$-regular graph and $G\in\mathfrak{N}$, then $G\square
C_{2n}\in\mathfrak{N}$ $(n\geq 2)$ and $W\left(G\square C_{2n}\right)\geq
W(G)+W\left(C_{2n}\right)+nr$.

  * Proof.

For the proof, we construct an edge-coloring of the graph $G\square C_{2n}$
that satisfies the specified conditions.

Let $V(G)=\left\\{v_{1},\ldots,v_{p}\right\\}$ and $V\left(G\square
C_{2n}\right)=\bigcup_{i=1}^{2n}V^{i}$, where
$V^{i}=\left\\{v_{j}^{(i)}\colon\,1\leq j\leq p\right\\}$. Also, let
$E\left(G\square
C_{2n}\right)=\bigcup_{i=1}^{2n}E^{i}\cup\bigcup_{j=1}^{p}E_{j}$, where

$E^{i}=\left\\{v_{j}^{(i)}v_{k}^{(i)}\colon\,v_{j}v_{k}\in E(G)\right\\}$ and
$E_{j}=\left\\{v_{j}^{(i)}v_{j}^{(i+1)}\colon\,1\leq i\leq
2n-1\right\\}\cup\left\\{v_{j}^{(1)}v_{j}^{(2n)}\right\\}$.

For $1\leq i\leq 2n$, define a subgraph $G^{i}$ of the graph $G\square C_{2n}$
as follows: $G^{i}=\left(V^{i},E^{i}\right)$. Clearly, $G^{i}$ is isomorphic
to $G$ for $1\leq i\leq 2n$. Since $G\in\mathfrak{N}$, there exists an
interval $W(G)$-coloring $\alpha$ of $G$. Now we define an edge-coloring
$\beta$ of the subgraphs $G^{1},\ldots,G^{2n}$.

For $1\leq i\leq 2n$ and for every edge $v_{j}^{(i)}v_{k}^{(i)}\in E(G^{i})$,
let

$\beta\left(v_{j}^{(i)}v_{k}^{(i)}\right)=\left\\{\begin{tabular}[]{ll}$\alpha\left(v_{j}v_{k}\right)$,&if
$i=1$,\\\ $\alpha\left(v_{j}v_{k}\right)+(i-1)(r+1)+1$,&if $2\leq i\leq
n+1$,\\\ $\alpha\left(v_{j}v_{k}\right)+(2n+1-i)(r+1)$,&if $n+2\leq i\leq
2n$.\\\ \end{tabular}\right.$

It is easy to see that the color of each edge of the subgraph $G^{i}$ is
obtained by shifting the color of the associated edge of $G$ by $(i-1)(r+1)+1$
for $2\leq i\leq n+1$, and by $(2n-i+1)(r+1)$ for $n+2\leq i\leq 2n$, thus the
set $S\left(v_{j}^{(i)},\beta\right)$ is an interval for each vertex
$v_{j}^{(i)}\in V(G^{i})$, where $1\leq i\leq 2n$, $1\leq j\leq p$. Now we
define an edge-coloring $\gamma$ of the graph $G\square C_{2n}$.

For every $e\in E\left(G\square C_{2n}\right)$, let

$\gamma(e)=\left\\{\begin{tabular}[]{ll}$\beta(e)$,&if $e\in E(G^{i}),$\\\
$\max S\left(v_{j}^{(1)},\beta\right)+1$,&if $e=v_{j}^{(1)}v_{j}^{(2n)}\in
E_{j}$,\\\ $\max S\left(v_{j}^{(1)},\beta\right)+2$,&if
$e=v_{j}^{(1)}v_{j}^{(2)}\in E_{j}$,\\\ $\max
S\left(v_{j}^{(i)},\beta\right)+1$,&if $e=v_{j}^{(i)}v_{j}^{(i+1)}\in
E_{j},2\leq i\leq n$,\\\ $\max S\left(v_{j}^{(i)},\beta\right)+1$,&if
$e=v_{j}^{(i-1)}v_{j}^{(i)}\in E_{j},n+2\leq i\leq 2n$,\\\
\end{tabular}\right.$

where $1\leq i\leq 2n,1\leq j\leq p$.

Let us prove that $\gamma$ is an interval
$\left(W(G)+W\left(C_{2n}\right)+nr\right)$-coloring of the graph $G\square
C_{2n}$ for $n\geq 2$.

First we show that the set $S\left(v_{j}^{(i)},\gamma\right)$ is an interval
for each vertex $v_{j}^{(i)}\in V\left(G\square C_{2n}\right)$, where $1\leq
i\leq 2n,1\leq j\leq p$.

Case 1: $i=1$, $1\leq j\leq p$.

By the definition of $\gamma$ and taking into account that $\max
S\left(v_{j},\alpha\right)-\min S\left(v_{j},\alpha\right)=r-1$ for $1\leq
j\leq p$, we have

$\displaystyle S\left(v_{j}^{(1)},\gamma\right)$ $\displaystyle=$
$\displaystyle\left\\{\min S\left(v_{j},\alpha\right),\ldots,\max
S\left(v_{j},\alpha\right)\right\\}\cup\left\\{\max
S\left(v_{j},\alpha\right)+2\right\\}\cup\left\\{\max
S\left(v_{j},\alpha\right)+1\right\\}$ $\displaystyle=$ $\displaystyle[\min
S\left(v_{j},\alpha\right),\max S\left(v_{j},\alpha\right)+2].$

Case 2: $2\leq i\leq n$, $1\leq j\leq p$.

By the definition of $\gamma$ and taking into account that $\max
S\left(v_{j},\alpha\right)-\min S\left(v_{j},\alpha\right)=r-1$ for $1\leq
j\leq p$, we have

$\displaystyle S\left(v_{j}^{(i)},\gamma\right)$ $\displaystyle=$
$\displaystyle\left\\{\min S\left(v_{j},\alpha\right)+(i-1)(r+1)+1,\ldots,\max
S\left(v_{j},\alpha\right)+(i-1)(r+1)+1\right\\}$
$\displaystyle\cup\left\\{\max
S\left(v_{j},\alpha\right)+(i-2)(r+1)+2\right\\}\cup\left\\{\max
S\left(v_{j},\alpha\right)+(i-1)(r+1)+2\right\\}$ $\displaystyle=$
$\displaystyle[\min S\left(v_{j},\alpha\right)+(i-1)(r+1),\max
S\left(v_{j},\alpha\right)+(i-1)(r+1)+2].$

Case 3: $i=n+1$, $1\leq j\leq p$.

By the definition of $\gamma$ and taking into account that $\max
S\left(v_{j},\alpha\right)-\min S\left(v_{j},\alpha\right)=r-1$ for $1\leq
j\leq p$, we have

$\displaystyle S\left(v_{j}^{(n+1)},\gamma\right)$ $\displaystyle=$
$\displaystyle\left\\{\min S\left(v_{j},\alpha\right)+n(r+1)+1,\ldots,\max
S\left(v_{j},\alpha\right)+n(r+1)+1\right\\}$ $\displaystyle\cup\left\\{\max
S\left(v_{j},\alpha\right)+(n-1)(r+1)+2\right\\}\cup\left\\{\max
S\left(v_{j},\alpha\right)+(n-1)(r+1)+1\right\\}$ $\displaystyle=$
$\displaystyle[\min S\left(v_{j},\alpha\right)+n(r+1)-1,\max
S\left(v_{j},\alpha\right)+n(r+1)+1].$

Case 4: $n+2\leq i\leq 2n$, $1\leq j\leq p$.

By the definition of $\gamma$ and taking into account that $\max
S\left(v_{j},\alpha\right)-\min S\left(v_{j},\alpha\right)=r-1$ for $1\leq
j\leq p$, we have

$\displaystyle S\left(v_{j}^{(i)},\gamma\right)$ $\displaystyle=$
$\displaystyle\left\\{\min
S\left(v_{j},\alpha\right)+(2n+1-i)(r+1),\ldots,\max
S\left(v_{j},\alpha\right)+(2n+1-i)(r+1)\right\\}$
$\displaystyle\cup\left\\{\max
S\left(v_{j},\alpha\right)+(2n+1-i)(r+1)+1\right\\}\cup\left\\{\max
S\left(v_{j},\alpha\right)+(2n-i)(r+1)+1\right\\}$ $\displaystyle=$
$\displaystyle[\min S\left(v_{j},\alpha\right)+(2n-i+1)(r+1)-1,\max
S\left(v_{j},\alpha\right)+(2n-i+1)(r+1)+1].$

Next we prove that in the coloring $\gamma$ all colors are used. Clearly,
there exists an edge $v_{j_{0}}^{(1)}v_{k_{0}}^{(1)}\in E(G^{1})$ such that
$\gamma\left(v_{j_{0}}^{(1)}v_{k_{0}}^{(1)}\right)=1$, since in the coloring
$\alpha$ there exists an edge $v_{j_{0}}v_{k_{0}}$ with
$\alpha\left(v_{j_{0}}v_{k_{0}}\right)=1$ and
$\gamma\left(v_{j_{0}}^{(1)}v_{k_{0}}^{(1)}\right)=\beta\left(v_{j_{0}}^{(1)}v_{k_{0}}^{(1)}\right)=\alpha\left(v_{j_{0}}v_{k_{0}}\right)$.
Similarly, there exists an edge $v_{j_{1}}^{(n+1)}v_{k_{1}}^{(n+1)}\in
E(G^{n+1})$ such that
$\gamma\left(v_{j_{1}}^{(n+1)}v_{k_{1}}^{(n+1)}\right)=W(G)+n(r+1)+1=W(G)+W\left(C_{2n}\right)+nr$,
since in the coloring $\alpha$ there exists an edge $v_{j_{1}}v_{k_{1}}$ with
$\alpha\left(v_{j_{1}}v_{k_{1}}\right)=W(G)$ and
$\gamma\left(v_{j_{1}}^{(n+1)}v_{k_{1}}^{(n+1)}\right)=\beta\left(v_{j_{1}}^{(n+1)}v_{k_{1}}^{(n+1)}\right)=\alpha\left(v_{j_{1}}v_{k_{1}}\right)+n(r+1)+1$.
Now, by Lemma 7, we have that for each $t\in[W(G)+W\left(C_{2n}\right)+nr]$,
there is an edge $e\in E\left(G\square C_{2n}\right)$ with $\gamma(e)=t$.

This shows that $\gamma$ is an interval
$\left(W(G)+W\left(C_{2n}\right)+nr\right)$-coloring of the graph $G\square
C_{2n}$ for $n\geq 2$. Thus, $G\square C_{2n}\in\mathfrak{N}$ and
$W\left(G\square C_{2n}\right)\geq W(G)+W\left(C_{2n}\right)+nr$. $\square$

From Theorems 5 and 13, we have:

###### Corollary 14

If $n=p2^{q}$, where $p$ is odd and $q$ is nonnegative, then

$W\left(K_{2n}\square C_{2n}\right)\geq 2n^{2}+4n-1-p-q$.

Note that the lower bound in Corollary 14 is close to the upper bound for
$W\left(K_{2n}\square C_{2n}\right)$, since $\Delta\left(K_{2n}\square
C_{2n}\right)=2n+1$ and $\mathrm{diam}\left(K_{2n}\square C_{2n}\right)=n+1$,
by Theorem 2, we have $W\left(K_{2n}\square C_{2n}\right)\leq 2n^{2}+4n+1$.

##  4 Grids, cylinders and tori

Interval edge-colorings of grids, cylinders and tori were first considered by
Giaro and Kubale in [7], where they proved the following:

###### Theorem 15

If $G=G(n_{1},n_{2},\ldots,n_{k})$ or $G=C(m,2n)$, $m\in\mathbb{N},n\geq 2$,
or $G=T(2m,2n)$, $m,n\geq 2$, then $G\in\mathfrak{N}$ and $w(G)=\Delta(G)$.

For the greatest possible number of colors in interval colorings of cylinders
and tori, Petrosyan and Karapetyan [20] proved the following theorems:

###### Theorem 16

For any $m\in\mathbb{N},n\geq 2$, we have $W(C(m,2n))\geq 3m+n-2$.

###### Theorem 17

For any $m,n\geq 2$, we have $W(T(2m,2n))\geq\max\\{3m+n,3n+m\\}$.

First we consider grids. It is easy to see that $W\left(G(2,n)\right)=2n-1$
for any $n\in\mathbb{N}$. Now we provide a lower bound for
$W\left(G(m,n)\right)$ when $m,n\geq 2$.

###### Theorem 18

For any $m,n\geq 2$, we have $W(G(m,n))\geq 2(m+n-3)$.

  * Proof.

For the proof, we are going to construct an edge-coloring of the graph
$G(m,n)$ that satisfies the specified conditions.

Let $V(G(m,n))=\left\\{v_{j}^{(i)}\colon\,1\leq i\leq m,1\leq j\leq
n\right\\}$ and $E(G(m,n))=\bigcup_{i=1}^{m}E^{i}\cup\bigcup_{j=1}^{n}E_{j}$,
where

$E^{i}=\left\\{v_{j}^{(i)}v_{j+1}^{(i)}\colon\,1\leq j\leq n-1\right\\}$ and
$E_{j}=\left\\{v_{j}^{(i)}v_{j}^{(i+1)}\colon\,1\leq i\leq m-1\right\\}$.

Define an edge-coloring $\alpha$ of $G(m,n)$ as follows:

(1)

for $i=1,\ldots,m-1$, $j=1,\ldots,n-1$, let

$\alpha\left(v_{j}^{(i)}v_{j}^{(i+1)}\right)=2(i+j)-3$;

(2)

for $i=1,\ldots,m-1$, let

$\alpha\left(v_{n}^{(i)}v_{n}^{(i+1)}\right)=2(n+i)-5$;

(3)

for $j=1,\ldots,n-1$, let

$\alpha\left(v_{j}^{(1)}v_{j+1}^{(1)}\right)=2j$;

(4)

for $i=2,\ldots,m$, $j=1,\ldots,n-1$, let

$\alpha\left(v_{j}^{(i)}v_{j+1}^{(i)}\right)=2(i+j)-4$.

It is easy to see that $\alpha$ is an interval $(2(m+n-3))$-coloring of
$G(m,n)$ when $m,n\geq 2$. $\square$

Note that the lower bound in Theorem 18 is not far from the upper bound for
$W\left(G(m,n)\right)$, since $G(m,n)$ is bipartite,
$2\leq\Delta\left(G(m,n)\right)\leq 4$ and
$\mathrm{diam}\left(G(m,n)\right)=m+n-2$, by Theorem 3, we have
$W\left(G(m,n)\right)\leq 3(m+n-2)+1$.

From Theorems 10 and 18, we have:

###### Corollary 19

If $n_{1}\geq\cdots\geq n_{2k}\geq 2$ $(k\in\mathbb{N})$, then

$W(G(n_{1},n_{2},\ldots,n_{2k}))\geq 2\sum_{i=1}^{2k}n_{i}-6k$,

and if $n_{1}\geq\cdots\geq n_{2k+1}\geq 2$ $(k\in\mathbb{N})$, then

$W(G(n_{1},n_{2},\ldots,n_{2k+1}))\geq 2\sum_{i=1}^{2k}n_{i}+n_{2k+1}-6k-1$.

Next we consider cylinders. In [18], Khchoyan proved the following:

###### Theorem 20

For any $n\geq 3$, we have

(1)

$C(2,n)\in\mathfrak{N}$,

(2)

$w\left(C(2,n)\right)=3$,

(3)

$W\left(C(2,n)\right)=n+2$,

(4)

if $w\left(C(2,n)\right)\leq t\leq W\left(C(2,n)\right)$, then $C(2,n)$ has an
interval $t$-coloring.

Now we prove some general results on cylinders.

###### Theorem 21

For any $m\geq 3,n\in\mathbb{N}$, we have $C(m,2n+1)\in\mathfrak{N}$ and

$w\left(C(m,2n+1)\right)=\left\\{\begin{tabular}[]{ll}$4$,&if $m$ is even,\\\
$6$,&if $m$ is odd.\\\ \end{tabular}\right.$

  * Proof.

Let $V(C(m,2n+1))=\left\\{v_{j}^{(i)}\colon\,1\leq i\leq m,1\leq j\leq
2n+1\right\\}$ and
$E(C(m,2n+1))=\bigcup_{i=1}^{m}{E}^{i}\cup\bigcup_{j=1}^{2n+1}{E}_{j}$ , where

$E^{i}=\left\\{v_{j}^{(i)}v_{j+1}^{(i)}\colon\,1\leq j\leq
2n\right\\}\cup\left\\{v_{1}^{(i)}v_{2n+1}^{(i)}\right\\}$,
$E_{j}=\left\\{v_{j}^{(i)}v_{j}^{(i+1)}\colon\,1\leq i\leq m-1\right\\}$.

First we show that if $m$ is even, then $C(m,2n+1)$ has an interval
$4$-coloring.

For $1\leq i\leq\frac{m}{2}$, define a subgraph $C^{i}$ of the graph
$C(m,2n+1)$ as follows:

$C^{i}=\left(V^{2i-1}\cup V^{2i},E^{2i-1}\cup
E^{2i}\cup\left\\{v_{j}^{(2i-1)}v_{j}^{(2i)}\colon\,1\leq j\leq
2n+1\right\\}\right)$.

Clearly, $C^{i}$ is isomorphic to $C(2,2n+1)$ for $1\leq i\leq\frac{m}{2}$. By
Theorem 20, $C(2,2n+1)\in\mathfrak{N}$ and there exists an interval
$3$-coloring $\alpha$ of $C(2,2n+1)$. Now we define an edge-coloring $\beta$
of $C(m,2n+1)$. First we color the edges of $C^{i}$ according to $\alpha$ for
$1\leq i\leq\frac{m}{2}$. Then we color the edges
$v_{j}^{(2i)}v_{j}^{(2i+1)}\in E_{j}$ with color $4$ for $1\leq
i\leq\frac{m}{2}-1,1\leq j\leq 2n+1$. It is easy to see that $\beta$ is an
interval $4$-coloring of $C(m,2n+1)$. This shows that
$C(m,2n+1)\in\mathfrak{N}$ and $w(C(m,2n+1))\leq 4$. On the other hand,
$w(C(m,2n+1))\geq\Delta(C(m,2n+1))=4$; thus $w(C(m,2n+1))=4$ for even $m$.

Now assume that $m$ is odd.

First we show that $C(3,2n+1)$ has an interval $6$-coloring.

Define an edge-coloring $\gamma$ of $C(3,2n+1)$ as follows:

(1)

$\gamma\left(v_{1}^{(1)}v_{1}^{(2)}\right)=6$ and for
$j=2,\ldots,2\left\lfloor\frac{n+1}{2}\right\rfloor$, let
$\gamma\left(v_{j}^{(1)}v_{j}^{(2)}\right)=4$;

(2)

$\gamma\left(v_{2\left\lfloor\frac{n+1}{2}\right\rfloor+1}^{(1)}v_{2\left\lfloor\frac{n+1}{2}\right\rfloor+1}^{(2)}\right)=2$
and for $j=2\left\lfloor\frac{n+1}{2}\right\rfloor+2,\ldots,2n+1$, let
$\gamma\left(v_{j}^{(1)}v_{j}^{(2)}\right)=3$;

(3)

$\gamma\left(v_{1}^{(2)}v_{1}^{(3)}\right)=3$ and for
$j=2,\ldots,2\left\lfloor\frac{n+1}{2}\right\rfloor$, let
$\gamma\left(v_{j}^{(2)}v_{j}^{(3)}\right)=2$;

(4)

for $j=2\left\lfloor\frac{n+1}{2}\right\rfloor+1,\ldots,2n+1$, let
$\gamma\left(v_{j}^{(2)}v_{j}^{(3)}\right)=1$;

(5)

$j=1,\ldots,\left\lfloor\frac{n+1}{2}\right\rfloor$, let

$\gamma\left(v_{2j-1}^{(1)}v_{2j}^{(1)}\right)=\gamma\left(v_{2j-1}^{(2)}v_{2j}^{(2)}\right)=5$
and
$\gamma\left(v_{2j}^{(1)}v_{2j+1}^{(1)}\right)=\gamma\left(v_{2j}^{(2)}v_{2j+1}^{(2)}\right)=3$;

(6)

for $j=\left\lfloor\frac{n+1}{2}\right\rfloor+1,\ldots,n$, let

$\gamma\left(v_{2j-1}^{(1)}v_{2j}^{(1)}\right)=\gamma\left(v_{2j-1}^{(2)}v_{2j}^{(2)}\right)=4$
and
$\gamma\left(v_{1}^{(1)}v_{2n+1}^{(1)}\right)=\gamma\left(v_{1}^{(2)}v_{2n+1}^{(2)}\right)=4$;

(7)

for $j=\left\lfloor\frac{n+1}{2}\right\rfloor+1,\ldots,n$, let
$\gamma\left(v_{2j}^{(1)}v_{2j+1}^{(1)}\right)=\gamma\left(v_{2j}^{(2)}v_{2j+1}^{(2)}\right)=2$;

(8)

for $j=1,\ldots,\left\lfloor\frac{n+1}{2}\right\rfloor$, let
$\gamma\left(v_{2j-1}^{(3)}v_{2j}^{(3)}\right)=1$ and
$\gamma\left(v_{2j}^{(3)}v_{2j+1}^{(3)}\right)=3$;

(9)

for $j=\left\lfloor\frac{n+1}{2}\right\rfloor+1,\ldots,n$, let
$\gamma\left(v_{2j-1}^{(3)}v_{2j}^{(3)}\right)=2$ and
$\gamma\left(v_{1}^{(3)}v_{2n+1}^{(3)}\right)=2$;

(10)

for $j=\left\lfloor\frac{n+1}{2}\right\rfloor+1,\ldots,n$, let
$\gamma\left(v_{2j}^{(3)}v_{2j+1}^{(3)}\right)=3$.

It is not difficult to see that $\gamma$ is an interval $6$-coloring of
$C(3,2n+1)$ for which $S(v_{j}^{(3)},\gamma)=[1,3]$ when $1\leq j\leq 2n+1$.

Next we define an edge-coloring $\phi$ of $C(m,2n+1)$ as follows: first we
color the edges of the subgraph $C(3,2n+1)$ of $C(m,2n+1)$ according to
$\gamma$. Secondly, we color the edges of the remaining subgraph $C(m-3,2n+1)$
of $C(m,2n+1)$ according to $\beta$, and finally, we color the edges
$v_{j}^{(3)}v_{j}^{(4)}\in E_{j}$ with color $4$ for $1\leq j\leq 2n+1$. It is
easy to see that $\phi$ is an interval $6$-coloring of $C(m,2n+1)$. This shows
that $C(m,2n+1)\in\mathfrak{N}$ and $w(C(m,2n+1))\leq 6$.

Now we prove that $w(C(m,2n+1))\geq 6$ for odd $m$.

Let $\psi$ be an interval $w(C(m,2n+1))$-coloring of $C(m,2n+1)$ and
$w(C(m,2n+1))\leq 5$. Consider the set $S\left(v_{j}^{(i)},\psi\right)$ for
$1\leq i\leq m,1\leq j\leq 2n+1$. It is easy to see that if
$d\left(v_{j}^{(i)}\right)=3$, then $1\leq\min
S\left(v_{j}^{(i)},\psi\right)\leq 3$, and if $d\left(v_{j}^{(i)}\right)=4$,
then $1\leq\min S\left(v_{j}^{(i)},\psi\right)\leq 2$. Hence, $3\in
S\left(v_{j}^{(i)},\psi\right)$ for $1\leq i\leq m,1\leq j\leq 2n+1$, but this
implies that the edges with color $3$ form a perfect matching in $C(m,2n+1)$,
which contradicts the fact that $C(m,2n+1)$ does not have one. Thus,
$w(C(m,2n+1))=6$ for odd $m$. $\square$

Before we derive lower bounds for $W(C(2m,2n))$ and $W(C(2m,2n+1))$, let us
note that Lemma 8, Theorems 15 and 21 imply the following:

###### Corollary 22

If $G\square H$ is planar and both factors have at least $3$ vertices, then
$G\square H\in\mathfrak{N}$ and $w(G\square H)\leq 6$.

###### Theorem 23

If $m\in\mathbb{N},n\geq 2$, then $W(C(2m,2n))\geq 4m+2n-2$, and if
$m,n\in\mathbb{N}$, then $W(C(2m,2n+1))\geq 4m+2n-1$.

  * Proof.

For the proof of the theorem, it suffices to construct edge-colorings that
satisfies the specified conditions. Let
$V(C(2m,2n))=\left\\{v_{j}^{(i)}\colon\,1\leq i\leq 2m,1\leq j\leq
2n\right\\}$ and $V(C(2m,2n+1))=\left\\{u_{j}^{(i)}\colon\,1\leq i\leq
2m,1\leq j\leq 2n+1\right\\}$. Also, let
$E(C(2m,2n))=\bigcup_{i=1}^{2m}E^{i}\cup\bigcup_{j=1}^{2n}E_{j}$ and
$E(C(2m,2n+1))=\bigcup_{i=1}^{2m}\overline{E}^{i}\cup\bigcup_{j=1}^{2n+1}\overline{E}_{j}$
, where

$E^{i}=\left\\{v_{j}^{(i)}v_{j+1}^{(i)}\colon\,1\leq j\leq
2n-1,\right\\}\cup\left\\{v_{1}^{(i)}v_{2n}^{(i)}\right\\}$,
$E_{j}=\left\\{v_{j}^{(i)}v_{j}^{(i+1)}\colon\,1\leq i\leq 2m-1\right\\}$ and
$\overline{E}^{i}=\left\\{u_{j}^{(i)}u_{j+1}^{(i)}\colon\,1\leq j\leq
2n,\right\\}\cup\left\\{u_{1}^{(i)}u_{2n+1}^{(i)}\right\\}$,
$\overline{E}_{j}=\left\\{u_{j}^{(i)}u_{j}^{(i+1)}\colon\,1\leq i\leq
2m-1\right\\}$.

First we construct an interval $(4m+2n-2)$-coloring of $C(2m,2n)$ when
$m\in\mathbb{N},n\geq 2$.

Define an edge-coloring $\alpha$ of $C(2m,2n)$ as follows:

(1)

for $i=1,\ldots,m$, $j=1,\ldots,n$, let

$\alpha\left(v_{j}^{(2i-1)}v_{j+1}^{(2i-1)}\right)=\alpha\left(v_{j}^{(2i)}v_{j+1}^{(2i)}\right)=4i+2j-4$;

(2)

for $i=1,\ldots,m$, $j=n+1,\ldots,2n-1$, let

$\alpha\left(v_{j}^{(2i-1)}v_{j+1}^{(2i-1)}\right)=\alpha\left(v_{j}^{(2i)}v_{j+1}^{(2i)}\right)=4i-2j+4n-1$;

(3)

for $i=1,\ldots,m$, let

$\alpha\left(v_{1}^{(2i-1)}v_{2n}^{(2i-1)}\right)=\alpha\left(v_{1}^{(2i)}v_{2n}^{(2i)}\right)=4i-1$;

(4)

for $i=1,\ldots,m$, $j=1,\ldots,n$, let

$\alpha\left(v_{j}^{(2i-1)}v_{j}^{(2i)}\right)=4i+2j-5$;

(5)

for $i=1,\ldots,m$, $j=n+1,\ldots,2n$, let

$\alpha\left(v_{j}^{(2i-1)}v_{j}^{(2i)}\right)=4i-2j+4n$;

(6)

for $i=1,\ldots,m-1$, $j=2,\ldots,n+1$, let

$\alpha\left(v_{j}^{(2i)}v_{j}^{(2i+1)}\right)=4i+2j-3$;

(7)

for $i=1,\ldots,m-1$, $j=n+2,\ldots,2n$, let

$\alpha\left(v_{j}^{(2i)}v_{j}^{(2i+1)}\right)=4i-2j+4n+2$;

(8)

for $i=1,\ldots,m-1$, let

$\alpha\left(v_{1}^{(2i)}v_{1}^{(2i+1)}\right)=4i$.

Next we construct an interval $(4m+2n-1)$-coloring of $C(2m,2n+1)$ when
$m,n\in\mathbb{N}$.

Define an edge-coloring $\beta$ of $C(2m,2n+1)$ as follows:

(1)

for $i=1,\ldots,m$, $j=1,\ldots,n+1$, let

$\beta\left(u_{j}^{(2i-1)}u_{j+1}^{(2i-1)}\right)=\beta\left(u_{j}^{(2i)}u_{j+1}^{(2i)}\right)=4i+2j-4$;

(2)

for $i=1,\ldots,m$, $j=n+2,\ldots,2n$, let

$\beta\left(u_{j}^{(2i-1)}u_{j+1}^{(2i-1)}\right)=\beta\left(u_{j}^{(2i)}u_{j+1}^{(2i)}\right)=4i-2j+4n+1$;

(3)

for $i=1,\ldots,m$, let

$\beta\left(u_{1}^{(2i-1)}u_{2n+1}^{(2i-1)}\right)=\beta\left(u_{1}^{(2i)}u_{2n+1}^{(2i)}\right)=4i-1$;

(4)

for $i=1,\ldots,m$, $j=1,\ldots,n+2$, let

$\beta\left(u_{j}^{(2i-1)}u_{j}^{(2i)}\right)=4i+2j-5$;

(5)

for $i=1,\ldots,m$, $j=n+3,\ldots,2n+1$, let

$\beta\left(u_{j}^{(2i-1)}u_{j}^{(2i)}\right)=4i-2j+4n+2$;

(6)

for $i=1,\ldots,m-1$, $j=2,\ldots,n+1$, let

$\beta\left(u_{j}^{(2i)}u_{j}^{(2i+1)}\right)=4i+2j-3$;

(7)

for $i=1,\ldots,m-1$, $j=n+2,\ldots,2n+1$, let

$\beta\left(u_{j}^{(2i)}u_{j}^{(2i+1)}\right)=4i-2j+4n+4$;

(8)

for $i=1,\ldots,m-1$, let

$\beta\left(u_{1}^{(2i)}u_{1}^{(2i+1)}\right)=4i$.

It is straightforward to check that $\alpha$ is an interval
$(4m+2n-2)$-coloring of $C(2m,2n)$ when $m\in\mathbb{N},n\geq 2$, and $\beta$
is an interval $(4m+2n-1)$-coloring of $C(2m,2n+1)$ when $m,n\in\mathbb{N}$.
$\square$

Note that the lower bound in Theorem 23 is not so far from the upper bound for
$W\left(C(m,n)\right)$. Indeed, since $C(2m,2n)$ is bipartite,
$3\leq\Delta\left(C(2m,2n)\right)\leq 4$ and
$\mathrm{diam}\left(C(2m,2n)\right)=2m+n-1$, by Theorem 3, we have
$W\left(C(2m,2n)\right)\leq 3(2m+n-1)+1$. Similarly, since
$3\leq\Delta\left(C(2m,2n+1)\right)\leq 4$ and
$\mathrm{diam}\left(C(2m,2n+1)\right)=2m+n-1$, by Theorem 2, we have
$W\left(C(2m,2n+1)\right)\leq 3(2m+n)+1$. Next we would like to compare
obtained lower bounds for $W(C(m,n))$. If $m$ is even and $m<n$, then the
lower bound in Theorem 23 is better than in Theorem 16, if $m$ is even and
$m>n$, then the lower bound in Theorem 16 is better than in Theorem 23, and if
$m$ is even and $m=n$, then we obtain the same lower bound in both theorems.

In the following we consider tori. In [22], Petrosyan proved that the torus
$T(m,n)\in\mathfrak{N}$ if and only if $mn$ is even. Since $T(m,n)$ is
$4$-regular, by Theorem 1, we obtain that $w(T(m,n))=4$ when $mn$ is even. Now
we derive a new lower bound for $W(T(m,n))$ when $mn$ is even.

###### Theorem 24

For any $m,n\geq 2$, we have $W(T(2m,2n))\geq\max\\{3m+n+2,3n+m+2\\}$, and for
any $m\geq 2$, $n\in\mathbb{N}$, we have

$W\left(T(2m,2n+1)\right)\geq\left\\{\begin{tabular}[]{ll}$2m+2n+2$,&if $m$ is
odd,\\\ $2m+2n+3$,&if $m$ is even.\\\ \end{tabular}\right.$

  * Proof.

First note that the lower bound for $W(T(2m,2n))$ $(m,n\geq 2)$ follows from
Theorem 13. For the proof of a second part of the theorem, it suffices to
construct an edge-coloring of $T(2m,2n+1)$ that satisfies the specified
conditions.

Let $V(T(2m,2n+1))=\left\\{v_{j}^{(i)}\colon\,1\leq i\leq 2m,1\leq j\leq
2n+1\right\\}$ and
$E(T(2m,2n+1))=\bigcup_{i=1}^{2m}E^{i}\cup\bigcup_{j=1}^{2n+1}E_{j}$, where

$E^{i}=\left\\{v_{j}^{(i)}v_{j+1}^{(i)}\colon\,1\leq j\leq
2n\right\\}\cup\left\\{v_{1}^{(i)}v_{2n+1}^{(i)}\right\\}$,
$E_{j}=\left\\{v_{j}^{(i)}v_{j}^{(i+1)}\colon\,1\leq i\leq
2m-1\right\\}\cup\left\\{v_{j}^{(1)}v_{j}^{(2m)}\right\\}$.

Define an edge-coloring $\alpha$ of $T(2m,2n+1)$ as follows:

(1)

for $j=1,\ldots,n+1$, let

$\alpha\left(v_{j}^{(1)}v_{j+1}^{(1)}\right)=\alpha\left(v_{j}^{(2m)}v_{j+1}^{(2m)}\right)=2j$;

(2)

for $j=n+2,\ldots,2n$, let

$\alpha\left(v_{j}^{(1)}v_{j+1}^{(1)}\right)=\alpha\left(v_{j}^{(2m)}v_{j+1}^{(2m)}\right)=2(2n+1-j)+3$
and

$\alpha\left(v_{1}^{(1)}v_{2n+1}^{(1)}\right)=\alpha\left(v_{1}^{(2m)}v_{2n+1}^{(2m)}\right)=3$;

(3)

for $j=1,\ldots,n+2$, let

$\alpha\left(v_{j}^{(1)}v_{j}^{(2m)}\right)=2j-1$;

(4)

for $j=n+3,\ldots,2n+1$, let

$\alpha\left(v_{j}^{(1)}v_{j}^{(2m)}\right)=2(2n+3-j)$;

(5)

for $i=1,\ldots,\left\lfloor\frac{m}{2}\right\rfloor$, $j=1,\ldots,n+1$, let

$\alpha\left(v_{j}^{(2i)}v_{j+1}^{(2i)}\right)=\alpha\left(v_{j}^{(2i+1)}v_{j+1}^{(2i+1)}\right)=\alpha\left(v_{j}^{(2m-2i)}v_{j+1}^{(2m-2i)}\right)=\alpha\left(v_{j}^{(2m-2i+1)}v_{j+1}^{(2m-2i+1)}\right)=4i+2j$;

(6)

for $i=1,\ldots,\left\lfloor\frac{m}{2}\right\rfloor$, $j=n+2,\ldots,2n$, let

$\alpha\left(v_{j}^{(2i)}v_{j+1}^{(2i)}\right)=\alpha\left(v_{j}^{(2i+1)}v_{j+1}^{(2i+1)}\right)=\alpha\left(v_{j}^{(2m-2i)}v_{j+1}^{(2m-2i)}\right)=\alpha\left(v_{j}^{(2m-2i+1)}v_{j+1}^{(2m-2i+1)}\right)=4i+2(2n+1-j)+3$
and

$\alpha\left(v_{1}^{(2i)}v_{2n+1}^{(2i)}\right)=\alpha\left(v_{1}^{(2i+1)}v_{2n+1}^{(2i+1)}\right)=\alpha\left(v_{1}^{(2m-2i)}v_{2n+1}^{(2m-2i)}\right)=\alpha\left(v_{1}^{(2m-2i+1)}v_{2n+1}^{(2m-2i+1)}\right)=4i+3$;

(7)

for $i=1,\ldots,\left\lceil\frac{m}{2}\right\rceil$, $j=2,\ldots,n+1$, let

$\alpha\left(v_{j}^{(2i-1)}v_{j}^{(2i)}\right)=\alpha\left(v_{j}^{(2m-2i+1)}v_{j}^{(2m-2i+2)}\right)=4i+2j-3$;

(8)

for $i=1,\ldots,\left\lceil\frac{m}{2}\right\rceil$, $j=n+2,\ldots,2n+1$, let

$\alpha\left(v_{j}^{(2i-1)}v_{j}^{(2i)}\right)=\alpha\left(v_{j}^{(2m-2i+1)}v_{j}^{(2m-2i+2)}\right)=4(n+1+i)-2j$;

(9)

for $i=1,\ldots,\left\lceil\frac{m}{2}\right\rceil$, let

$\alpha\left(v_{1}^{(2i-1)}v_{1}^{(2i)}\right)=\alpha\left(v_{1}^{(2m-2i+1)}v_{1}^{(2m-2i+2)}\right)=4i$;

(10)

for $i=1,\ldots,\left\lfloor\frac{m}{2}\right\rfloor$, $j=1,\ldots,n+2$, let

$\alpha\left(v_{j}^{(2i)}v_{j}^{(2i+1)}\right)=\alpha\left(v_{j}^{(2m-2i)}v_{j}^{(2m-2i+1)}\right)=4i+2j-1$;

(11)

for $i=1,\ldots,\left\lfloor\frac{m}{2}\right\rfloor$, $j=n+3,\ldots,2n+1$,
let

$\alpha\left(v_{j}^{(2i)}v_{j}^{(2i+1)}\right)=\alpha\left(v_{j}^{(2m-2i)}v_{j}^{(2m-2i+1)}\right)=4i+2(2n+3-j)$.

It is not difficult to check that $\alpha$ is an interval $(2m+2n+3)$-coloring
of $T(2m,2n+1)$ when $m$ is even, and $\alpha$ is an interval
$(2m+2n+2)$-coloring of $T(2m,2n+1)$ when $m$ is odd. $\square$

From Theorems 1, 15 and 24, we have:

###### Corollary 25

If $G=T(2m,2n)$ $(m,n\geq 2)$ and $4\leq t\leq\max\\{3m+n+2,3n+m+2\\}$, then
$G$ has an interval $t$-coloring. Also, If $H=T(2m,2n+1)$ $(m\geq
2,n\in\mathbb{N})$, $m$ is odd and $4\leq t\leq 2m+2n+2$, then $H$ has an
interval $t$-coloring, and if $H=T(2m,2n+1)$ $(m\geq 2,n\in\mathbb{N})$, $m$
is even and $4\leq t\leq 2m+2n+3$, then $H$ has an interval $t$-coloring.

Let us note that the lower bound in Theorem 24 is not so far from the upper
bound for $W\left(T(m,n)\right)$. Indeed, since $T(2m,2n)$ is bipartite,
$\Delta\left(T(2m,2n)\right)=4$ and $\mathrm{diam}\left(C(2m,2n)\right)=m+n$,
by Theorem 3, we have $W\left(T(2m,2n)\right)\leq 3(m+n)+1$. Similarly, since
$\Delta\left(T(2m,2n+1)\right)=4$ and
$\mathrm{diam}\left(T(2m,2n+1)\right)=m+n$, by Theorem 2, we have
$W\left(T(2m,2n+1)\right)\leq 3(m+n+1)+1$.

##  5 $N$-dimensional cubes

It is well-known that the $n$-dimensional cube $Q_{n}$ is the Cartesian
product of $n$ copies of $K_{2}$. In [21], Petrosyan investigated interval
colorings of $n$-dimensional cubes and proved that $w\left(Q_{n}\right)=n$ and
$W\left(Q_{n}\right)\geq\frac{n(n+1)}{2}$ for any $n\in\mathbb{N}$. In the
same paper he also conjectured that $W\left(Q_{n}\right)=\frac{n(n+1)}{2}$ for
any $n\in\mathbb{N}$. Here, we prove this conjecture.

Let $e,e^{\prime}\in E(Q_{n})$ and $e=u_{1}u_{2}$, $e^{\prime}=v_{1}v_{2}$.
The distance between two edges $e$ and $e^{\prime}$ in $Q_{n}$, we define as
follows:

$d(e,e^{\prime})=\min_{1\leq i\leq 2,1\leq j\leq 2}d\left(u_{i},v_{j}\right)$.

Let $\alpha$ be an interval $t$-coloring of $Q_{n}$.

For any $e,e^{\prime}\in E(Q_{n})$, define
$\mathrm{sp}_{\alpha}\left(e,e^{\prime}\right)$ as follows:

$\mathrm{sp}_{\alpha}\left(e,e^{\prime}\right)=\left|\alpha(e)-\alpha(e^{\prime})\right|$.

For any $k,0\leq k\leq n-1$, define $\mathrm{sp}_{\alpha,k}$ as follows:

$\mathrm{sp}_{\alpha,k}=\max\left\\{\mathrm{sp}_{\alpha}\left(e,e^{\prime}\right)\colon\,e,e^{\prime}\in
E(Q_{n})~{}and~{}d(e,e^{\prime})=k\right\\}$.

First we need the following simple lemma.

###### Lemma 26

For any pair of vertices $u,v\in V(Q_{n})$ with $d(u,v)=k$, there exist
$v_{1},v_{2},\ldots,v_{k}$ ($v_{i}\neq v_{j}$ when $i\neq j$) vertices such
that $d(u,v_{i})=k-1$ and $vv_{i}\in E(Q_{n})$ for $i=1,\ldots,k$.

Now let $\alpha$ be an interval $W(Q_{n})$-coloring of $Q_{n}$. Clearly,
$\mathrm{sp}_{\alpha,0}=n-1$.

###### Theorem 27

If $1\leq k\leq n-1$, then
$\mathrm{sp}_{\alpha,k}\leq\mathrm{sp}_{\alpha,k-1}+n-k$.

  * Proof.

Let $e,e^{\prime}\in E(Q_{n})$ be any two edges of $Q_{n}$ with
$d(e,e^{\prime})=k$. Without loss of generality, we may assume that
$\alpha(e)\geq\alpha(e^{\prime})$. Since $d(e,e^{\prime})=k$, there exist $u$
and $v$ vertices such that $u\in e$ and $v\in e^{\prime}$ and $d(u,v)=k$. By
Lemma 26, we have that there are $v_{1},v_{2},\ldots,v_{k}$ ($v_{i}\neq v_{j}$
when $i\neq j$) vertices such that $d(u,v_{i})=k-1$ and $vv_{i}\in E(Q_{n})$
for $i=1,\ldots,k$. Since $Q_{n}$ is $n$-regular, we have

$\min_{1\leq i\leq k}\alpha(v_{i}v)\leq\alpha(e^{\prime})+n-k$. (*)

Let $\alpha(e^{\prime\prime})=\min_{1\leq i\leq k}\alpha(v_{i}v)$. By (*), we
obtain

$\alpha(e^{\prime})\geq\alpha(e^{\prime\prime})-(n-k)$ and
$d(e,e^{\prime\prime})=k-1$.

Thus,

$\mathrm{sp}_{\alpha}\left(e,e^{\prime}\right)=\left|\alpha(e)-\alpha(e^{\prime})\right|\leq\left|\alpha(e)-\alpha(e^{\prime\prime})+n-k\right|\leq\left|\alpha(e)-\alpha(e^{\prime\prime})\right|+n-k\leq\mathrm{sp}_{\alpha,k-1}+n-k$.

Since $e$ and $e^{\prime}$ were arbitrary edges with $d(e,e^{\prime})=k$, we
obtain $\mathrm{sp}_{\alpha,k}\leq\mathrm{sp}_{\alpha,k-1}+n-k$. $\square$

###### Corollary 28

$\mathrm{sp}_{\alpha,n-1}\leq\frac{n\left(n+1\right)}{2}-1$.

  * Proof.

By Theorem 27, we have

$\mathrm{sp}_{\alpha,n-1}\leq\mathrm{sp}_{\alpha,0}+n-1+n-2+\ldots+1=\frac{n\left(n+1\right)}{2}-1$.

$\square$

###### Corollary 29

$W\left(Q_{n}\right)\leq\frac{n\left(n+1\right)}{2}$ for any $n\in\mathbb{N}$.

  * Proof.

Clearly, for any $e,e^{\prime}\in E(Q_{n})$, we have $d(e,e^{\prime})\leq
n-1$. Thus, by Corollary 28, we get
$W\left(Q_{n}\right)\leq\frac{n\left(n+1\right)}{2}$. $\square$

By Theorem 6 and Corollary 29, we obtain
$W\left(Q_{n}\right)=\frac{n\left(n+1\right)}{2}$ for any $n\in\mathbb{N}$.
Moreover, by Theorem 1, we have that $Q_{n}$ has an interval $t$-coloring if
and only if $n\leq t\leq\frac{n\left(n+1\right)}{2}$.

## References

  * [1] A.S. Asratian, R.R. Kamalian, Interval colorings of edges of a multigraph, Appl. Math. 5 (1987) 25-34 (in Russian).
  * [2] A.S. Asratian, R.R. Kamalian, Investigation on interval edge-colorings of graphs, J. Combin. Theory Ser. B 62 (1994) 34-43.
  * [3] A.S. Asratian, T.M.J. Denley, R. Haggkvist, Bipartite Graphs and their Applications, Cambridge University Press, Cambridge, 1998.
  * [4] M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002) 77-94.
  * [5] M. Behzad, E.S. Mahmoodian, On topological invariants of the product of graphs, Canad. Math. Bull. 12 (1969) 157-166.
  * [6] Y. Feng, Q. Huang, Consecutive edge-coloring of the generalized $\theta$-graph, Discrete Appl. Math. 155 (2007) 2321-2327.
  * [7] K. Giaro, M. Kubale, Consecutive edge-colorings of complete and incomplete Cartesian products of graphs, Congr, Numer. 128 (1997) 143-149.
  * [8] K. Giaro, M. Kubale, M. Malafiejski, Consecutive colorings of the edges of general graphs, Discrete Math. 236 (2001) 131-143.
  * [9] K. Giaro, M. Kubale, Compact scheduling of zero-one time operations in multi-stage systems, Discrete Appl. Math. 145 (2004) 95-103.
  * [10] D. Hanson, C.O.M. Loten, B. Toft, On interval colorings of bi-regular bipartite graphs, Ars Combin. 50 (1998) 23-32.
  * [11] W. Imrich, S. Klavzar, Product graphs: Structure and Recognition, John Wiley & Sons, New York, 2000.
  * [12] T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995.
  * [13] R.R. Kamalian, Interval colorings of complete bipartite graphs and trees, preprint, Comp. Cen. of Acad. Sci. of Armenian SSR, Erevan, 1989 (in Russian).
  * [14] R.R. Kamalian, Interval edge colorings of graphs, Doctoral Thesis, Novosibirsk, 1990.
  * [15] R.R. Kamalian, A.N. Mirumian, Interval edge colorings of bipartite graphs of some class, Dokl. NAN RA, 97 (1997) 3-5 (in Russian).
  * [16] R.R. Kamalian, P.A. Petrosyan, A note on upper bounds for the maximum span in interval edge-colorings of graphs, Discrete Math. 312 (2012) 1393-1399.
  * [17] R.R. Kamalian, P.A. Petrosyan, A note on interval edge-colorings of graphs, Graphs and Combin. (2012) under review.
  * [18] A. Khchoyan, Interval edge-colorings of subcubic graphs and multigraphs, Yerevan State University, BS thesis, 2010, 30p.
  * [19] M. Kubale, Graph Colorings, American Mathematical Society, 2004.
  * [20] P.A. Petrosyan, G.H. Karapetyan, Lower bounds for the greatest possible number of colors in interval edge colorings of bipartite cylinders and bipartite tori, Proceedings of the CSIT Conference (2007) 86-88.
  * [21] P.A. Petrosyan, Interval edge-colorings of complete graphs and $n$-dimensional cubes, Discrete Math. 310 (2010) 1580-1587.
  * [22] P.A. Petrosyan, Interval edge colorings of some products of graphs, Discuss. Math. Graph Theory 31(2) (2011) 357-373.
  * [23] P.A. Petrosyan, H.H. Khachatrian, L.E. Yepremyan, H.G. Tananyan, Interval edge-colorings of graph products, Proceedings of the CSIT Conference (2011) 89-92.
  * [24] S.V. Sevast’janov, Interval colorability of the edges of a bipartite graph, Metody Diskret. Analiza 50 (1990) 61-72 (in Russian).
  * [25] D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 2001.