# Revealing the non-adiabatic and non-Abelian multiple-band effects via
anisotropic valley Hall conduction in bilayer graphene

Ci Li<EMAIL_ADDRESS>Department of Physics, The University of Hong Kong,
Hong Kong, China  HKU-UCAS Joint Institute of Theoretical and Computational
Physics at Hong Kong, China  Matisse Wei-Yuan Tu<EMAIL_ADDRESS>Department of Physics, National Sun Yat-sen University, Taiwan  Wang Yao
Department of Physics, The University of Hong Kong, Hong Kong, China  HKU-UCAS
Joint Institute of Theoretical and Computational Physics at Hong Kong, China

###### Abstract

Many quantum materials of interest, ex., bilayer graphene, possess a number of
closely spaced but not fully degenerate bands near the Fermi level, where the
coupling to the far detuned remote bands can induce Berry curvatures of the
non-Abelian character in this active multiple-band manifold for transport
effects. Under finite electric fields, non-adiabatic interband transition
processes are expected to play significant roles in the associated Hall
conduction. Here through an exemplified study on the valley Hall conduction in
AB-stacked bilayer graphene, we show that the contribution arising from non-
adiabatic transitions around the bands near the Fermi energy to the Hall
current is not only quantitatively about an order-of-magnitude larger than the
contribution due to adiabatic inter-manifold transition with the non-Abelian
Berry curvatures. Due to the trigonal warping, the former also displays an
anisotropic response to the orientation of the applied electric field that is
qualitatively distinct from that of the latter. We further show that these
anisotropic responses also reveal the essential differences between the
diagonal and off-diagonal elements of the non-Abelian Berry curvature matrix
in terms of their the contributions to the Hall currents. We provide a
physically intuitive understanding on the origin of distinct anisotropic
features from different Hall current contributions, in terms of band
occupations and interband coherence. This then points to the generalization
beyond the specific example of bilayer graphenes.

##  I Introduction

Band structure effects on transport of electrons driven by an external
electric field constitute one of the most fundamental issues in solid-state
physics Mer . In principle, one can group the electronic bands into two kinds
of manifolds, namely, the active and the remote, according to the relation
between the relevant gaps and the applied field. The active manifold contains
those bands around the Fermi energy which play the dominant roles in the
field-driven transport. Other bands are categorised into the remote manifold.
Due to the relatively large gaps between the active and the remote manifolds,
the field-induced inter-manifold transitions are well captured by the
adiabatic approximation, in which the electric field is treated as a
perturbation. When the active manifold contains a single band or a number of
fully degenerate bands, this adiabatic description has been successful in
manifesting one of the most non-trivial band structure effects on electron
transport, namely, the Hall effect Kar ; Lutt ; Adam ; Thou ; Mac ; Naga ; Niu
, which includes a number of varieties such as spin Zhang ; Murakami04235206 ;
Mac1 ; Kane  and valley Hall effects Niu1 ; Yao . On the other hand, when the
active manifold contains a number of closely spaced but not fully degenerate
bands, the effects of a finite electric field on the interband transitions
within the active manifold are beyond the validity of perturbation treatment
and therefore also requires non-adiabatic consideration. Correspondingly, this
leads to a non-adiabatic Hall effect, which has been found to be pronounced in
Dirac cones with a Berry curvature hotspot, as recently discussed Tu1  and
extended to situations with spatially varied band structures Tu .

Although previous studies have respectively expounded on the Hall effects in
the adiabatic regime and expanded into the non-adiabatic one, interesting
realistic materials such as transition metal dichalcogenides (ex. twisted
$\text{MoSe}_{2}$ homobilayers HY ; Mac2 ; DW ; HY1 ) and bilayer graphenesMc2
indeed possess band structures that demand a coherent unification of the above
two perspectives. Explicitly, from the view of the carrier motion, the Hall
effect is rooted to the anomalous part of the velocity. On one end, when the
active manifold contains only a single band or fully degenerate bands over the
whole Brillouin zone, the adiabatic inter-manifold transition results in the
well-known expression of the anomalous velocity in terms of the Berry
curvatures of the active bands Thou ; Niu ; Tu ; NiuB ; Boehm03book . On the
other end, when the remote bands are completely ignored, non-adiabatic
dynamics among the non-degenerate bands within the active manifold gives rise
to a renormalized carrier velocity due to the finite electric field, that also
has an anomalous part contributing to the corresponding non-adiabatic Hall
effect Tu1 . Naturally, the consequence from the interplay of these two ends
is an important question worthy further investigation, since many quantum
materials of interest do have non-degenerate active bands together with non-
negligible coupling to remote bands.

Apart from the non-adiabatic effects mentioned above, the multiple-band nature
of the active manifold, as well-known, also gives rise to the non-Abelian
characters of Berry curvatures upon projecting out the remote bands Niu  (see
also Tu  for pedagogical derivation). On one hand, from the current response
to an infinitesimal applied field, the pure geometrical aspects of the non-
Abelian characters on the Hall currents have been well understood
Murakami04235206 ; Shi . On the other hand, the non-Abelian Berry curvatures
as anomalous driving forces for the dynamics of single wave packets have also
been analysed through the peculiarly induced motion under various contexts
Culcer05085110 ; Chang08193202 ; Gorbar18045203 ; Stedman19103007 .
Nevertheless, the interplay between these two faces of multiple-band effects,
namely, the non-Abelian characters and the non-adiabatic dynamics still
remains an open question.

In this work, we address the above raised issues through investigating the
valley Hall currents in biased graphene bilayer with a modest gap
($0.01\mathrm{eV}$) (Fig. 1(a)) Novo ; Mc ; Ohta ; Mc1 ; Cast ; Oost ; YB ;
Yang ; Mc2 ; Ju , The effective four-band model for this material features two
bands close in energy forming the active manifold and two other remote bands
separated from the active bands by around 0.4eV (see Fig. 1(b)), suitable for
the present purpose.

Explicitly, we investigate the transverse valley currents of $AB$-stacked
bilayer graphene under finite external electric fields. We treat both the
contributions from the adiabatic inter-manifold-transitions and non-adiabatic
intra-active-manifold transitions to the Hall conduction on an equal footing.
The main point of the present research is to establish that the non-adiabatic
aspect of the Hall current is a distinct facet that is qualitatively different
from the more familiar Hall effect usually studied in the adiabatic regime.
This is revealed through the dependence of the Hall current on the angle
between the applied electric field and the crystalline axis, exploiting the
anisotropy from trigonal warping of the electronic band structure of AB-
stacked bilayer graphene. The ability to apply an electric field along various
directions across a sample has been experimentally realized Kang19324  with an
attempt to facilitate the study of the well-known nonlinear Hall effect
supported by Abelian Berry curvature dipoles note-i-0 . We show that the
feasibility on the angular-dependence of the Hall current not only reveals the
crucial distinctions between the adiabatic inter-manifold and the non-
adiabatic intra-active-manifold contributions to the Hall current. But it also
uncovers interesting difference between contributions involving diagonals and
off-diagonals from the non-Abelian Berry curvatures matrix.

Figure 1: (Color online) (a): The atomic structure of an $AB$-stacked bilayer
graphene in side view. (b): The four-band dispersion (with $\gamma_{3}=0$ in
(a), see also Eq. (8)) clearly distinguishing the active and the remote bands.
(c): Interband coherence directly formed through non-adiabatic intra-active-
manifold dynamics. (d): Interband coherence indirectly formed through
adiabatic inter-manifold transitions. They imply distinct roles in their
respective contributions to the Hall conduction.

##  II Unified description of adiabatic and non-adiabatic regimes

To begin, we first summarise the main framework that unify the wave-packet
description of electronic transport for both the adiabatic and the non-
adiabatic regimes Tu . We consider a general band structure, described by the
Hamiltonian, $\mathcal{H}\left(\boldsymbol{k}\right)$ that totally has $N_{A}$
bands in the active manifold $A$ and $N_{R}$ bands in the remote manifold $R$.
The band wavefunctions and energies of
$\mathcal{H}\left(\boldsymbol{k}\right)$ are denoted respectively by
$\left|u_{n}\left(\boldsymbol{k}\right)\right\rangle$ and
$\varepsilon_{n}\left(\boldsymbol{k}\right)$ with the band index $n$ and the
Bloch wave vector $\boldsymbol{k}$. The separation between the manifolds $A$
and $R$ means $\forall n_{a},m_{a}\in A$ and $\forall n_{r}\in R$ that

$\left|\varepsilon_{n_{a}}-\varepsilon_{n_{r}}\right|\gg\underset{m\in{A}}{\text{MAX}}\left|\varepsilon_{n_{a}}-\varepsilon_{m}\right|,~{}\frac{\left|\varepsilon_{n_{a}}-\varepsilon_{n_{r}}\right|}{\left|\varepsilon_{m_{a}}-\varepsilon_{n_{r}}\right|}\approx
1,$

The dynamics of a single wave packet is described by the time dependent
Schrödinger equation
$i\hbar\left|\dot{u}\left(t\right)\right\rangle=\mathcal{H}\left(\boldsymbol{k}\right)\left|u\left(t\right)\right\rangle$
in which the carrier’s Bloch wave vector acquires its time dependence
$\hbar\boldsymbol{\dot{k}}=-e\boldsymbol{E}$ through the driving of an
external electric field $\boldsymbol{E}$. The solution has the form
$\left|u\left(t\right)\right\rangle=\sum_{n\in{A}+R}\eta_{n}\left(t\right)e^{i\gamma_{n}\left(\boldsymbol{k}\right)}\left|u_{n}\left(\boldsymbol{k}\right)\right\rangle$
with the band amplitudes $\eta_{n}$ subject to normalisation. Here
$\gamma_{n}\left(\boldsymbol{k}\right)=\int_{\boldsymbol{k}_{0}}^{\boldsymbol{k}}\text{d}\boldsymbol{k}^{\prime}\cdot\left[\mathcal{R}_{\boldsymbol{k}^{\prime}}\right]_{n,n}$
is the Berry phase of band $n$ for a trajectory of $\boldsymbol{k}$ starting
from $\boldsymbol{k}_{0}$ and
$\left[\mathcal{R}_{\boldsymbol{k}}\right]_{n,m}=i\left\langle
u_{n}\right|\frac{\partial}{\partial\boldsymbol{k}}\left|u_{m}\right\rangle$
denotes the Berry connection between bands $n$ and $m$.

By projecting out the remote bands while retaining their effects, the centre-
of-mass motion of a single wave packet is described by the following
equations,

$\displaystyle\dot{\boldsymbol{r}}$
$\displaystyle=\left\langle\left[\mathcal{D}_{\hbar\boldsymbol{k}},\mathcal{H}_{A}\left(\boldsymbol{k}\right)\right]-\dot{\boldsymbol{k}}\times\boldsymbol{\mathcal{F}}_{\boldsymbol{k}}\right\rangle_{A},$
(1a) $\displaystyle\hbar\dot{\boldsymbol{k}}$ $\displaystyle=-e\boldsymbol{E}$
(1b) where $\mathcal{H}_{A}\left(\boldsymbol{k}\right)$ denotes the projection
of $\mathcal{H}\left(\boldsymbol{k}\right)$ into the active manifold and
$\left[\mathcal{D}_{\boldsymbol{k}}\right]_{n,m}=\delta_{n,m}\frac{\partial}{\partial\boldsymbol{k}}-i\left[\mathcal{R}_{\boldsymbol{k}}\right]_{n,m},$
(1c) is the covariant derivative. The boldface
$\boldsymbol{\mathcal{F}}_{\boldsymbol{k}}$ stands for a rank-1 tensor as a
vector whose spatial components $\mathcal{F}_{\boldsymbol{k}}^{\lambda}$’s are
related to the rank-2 Berry curvature tensor
$(1/2)\epsilon^{\alpha\beta\lambda}\left[\mathcal{F}_{\boldsymbol{k}}^{{\alpha}{\beta}}\right]=\mathcal{F}_{\boldsymbol{k}}^{\lambda}$
where $\epsilon^{\alpha\beta\lambda}$ is the Levi-Civita symbol and
$\mathcal{F}_{\boldsymbol{k}}^{\alpha\beta}=\left\\{\frac{\partial\left[\mathcal{R}_{k_{\beta}}\right]}{\partial{k}_{\alpha}}-\frac{\partial\left[\mathcal{R}_{k_{\alpha}}\right]}{\partial{k}_{\beta}}-i\left[\mathcal{R}_{k_{\alpha}},\mathcal{R}_{k_{\beta}}\right]\right\\},$
(1d) which retains the non-Abelian matrix structure of the Berry connections
$\mathcal{R}_{\boldsymbol{k}}$ in band indices. Here the square bracket stands
for the average
$\left\langle{O}\right\rangle_{A}=\sum_{n,m\in{A}}\eta_{n}^{\ast}O_{n,m}\eta_{m}$
over the band amplitudes $\eta_{n}$’s, which are subject to
$i\hbar\dot{\boldsymbol{\eta}}=\bar{\mathcal{H}}\boldsymbol{\eta}$ (2a) where
the matrix elements of the moving-frame Hamiltonian $\bar{\mathcal{H}}$ read
$\bar{\mathcal{H}}_{n,m}=\delta_{n,m}\varepsilon_{n}+\left(1-\delta_{n,m}\right)e\boldsymbol{E}\cdot\left[\bar{\mathcal{R}}_{\boldsymbol{k}}\right]_{n,m},$
(2b) in which
$\left[\bar{\mathcal{R}}_{\boldsymbol{k}}\right]_{n,m}=e^{-i\gamma_{n}}\left[\mathcal{R}_{\boldsymbol{k}}\right]_{n,m}e^{i\gamma_{m}}$.
The non-Abelian Berry curvature $\mathcal{F}_{\boldsymbol{k}}^{\alpha\beta}$
given by Eq. (1d) arises from adiabatic inter-manifold transitions and is
independent of $\boldsymbol{E}$. Nevertheless, its influences on the carrier
velocity $\dot{\boldsymbol{r}}$, manifested through the second term in Eq.
(1a), namely,
$\left\langle\boldsymbol{\mathcal{F}}_{\boldsymbol{k}}\right\rangle_{A}$,
contains the non-adiabatic intra-active-manifold dynamics embedded in
$\boldsymbol{\eta}$ that displays non-perturbation effects from a finite
$\boldsymbol{E}$ (see Eq. (2)).

The electrical currents arise from an ensemble of wave packets. By taking into
accounts the scattering effects and the decoherence within the band space Tu ,
the electric current is found to be

$\boldsymbol{J}=-e\sum_{i}\int_{\boldsymbol{k}}g_{i}\left(\boldsymbol{k}\right)\bar{\boldsymbol{v}}_{i}\left(\boldsymbol{k}\right),$
(3a) where we have abbreviated $\int\text{d}\boldsymbol{k}$ by
$\int_{\boldsymbol{k}}$. Here $\bar{\boldsymbol{v}}_{i}$ is the ensemble-
averaged velocity, containing two contributions,
$\bar{\boldsymbol{v}}_{i}=\bar{\boldsymbol{v}}_{i}^{A}+\bar{\boldsymbol{v}}_{i}^{R}.$
(3b) The intra-active-manifold non-adiabatic dynamics contributes with
$\bar{\boldsymbol{v}}_{i}^{A}=\bar{\boldsymbol{v}}_{i}^{\text{occ},A}+\bar{\boldsymbol{v}}_{i}^{\text{coh},A}$
(4a) where
$\bar{\boldsymbol{v}}_{i}^{\text{occ},A}=\sum_{n\in{A}}\left|\bar{\eta}_{n}^{i}\right|^{2}\frac{\partial\varepsilon_{n}}{\partial\boldsymbol{k}},$
(4b) is the normal velocity due to band dispersion and
$\bar{\boldsymbol{v}}_{i}^{\text{coh},A}=\sum_{n\neq{m}\in{A}}\left(\bar{\eta}_{n}^{i}\right)^{\ast}\left[\frac{\partial\mathcal{H}_{A}}{\partial\hbar\boldsymbol{k}}\right]_{n,m}\bar{\eta}_{m}^{i},$
(4c) is one part of the anomalous velocity. The other part of the anomalous
velocity is contributed by the inter-manifold adiabatic dynamics with
$\bar{\boldsymbol{v}}_{i}^{R}=\bar{\boldsymbol{v}}_{i}^{\text{occ},R}+\bar{\boldsymbol{v}}_{i}^{\text{coh},R},$
(5a) where
$\bar{\boldsymbol{v}}_{i}^{\text{occ},R}=\frac{e}{\hbar}\boldsymbol{E}\times\sum_{n\in{A}}\left|\bar{\eta}_{n}^{i}\right|^{2}\left[\boldsymbol{\mathcal{F}}_{\boldsymbol{k}}\right]_{n,n},$
(5b) and
$\bar{\boldsymbol{v}}_{i}^{\text{coh},R}=\frac{e}{\hbar}\boldsymbol{E}\times\sum_{n\neq
m\in{A}}\left(\bar{\eta}_{n}^{i}\right)^{\ast}\left[\boldsymbol{\mathcal{F}}_{\boldsymbol{k}}\right]_{n,m}\bar{\eta}_{m}^{i}.$
(5c) come from projecting the inter-manifold dynamics onto the band
occupations $\left|\bar{\eta}_{n}^{i}\right|^{2}$ and interband coherence
$\left(\bar{\eta}_{n}^{i}\right)^{\ast}\bar{\eta}_{m}^{i}$ in the active
manifold respectively. Here $\bar{\boldsymbol{\eta}}^{i}$, a vector with
components $\bar{\eta}_{n}^{i}$ enumerated by $n$, is defined as an
eigenvector of the moving-frame Hamiltonian’s projection on active bands,
$\bar{\mathcal{H}}_{A}\left(\boldsymbol{k},\boldsymbol{E}\right)$, indexed
with $i$, namely,
$\bar{\mathcal{H}}_{A}\bar{\boldsymbol{\eta}}^{i}=\mathcal{E}_{i}\bar{\boldsymbol{\eta}}^{i}$
with $\mathcal{E}_{i}$ the corresponding eigenvalue. We call
$\bar{\boldsymbol{\eta}}^{i}$’s the hybridised bands and they depend on the
electric field in a non-perturbation way Tu1 ; Tu . The physical meaning is
the following. The joint action of decoherence and the electric field favours
a certain form of interband coherence as those contained in
$\bar{\boldsymbol{\eta}}^{i}$’s. As a result, the carriers are led to a
statistical mixture of the hybridised bands $\bar{\boldsymbol{\eta}}^{i}$’s.
The distribution function with respect to occupations on the hybridised bands
is given by $g_{i}=g_{i}^{0}+\delta g_{i}$ where
$g_{i}^{0}=1/\left[\exp\left(\frac{\mathcal{E}_{i}-\mu}{k_{B}T}\right)+1\right]$
with $\mu$ the chemical potential and $T$ the temperature and $\delta
g_{i}=\left(e/\hbar\right)\tau\boldsymbol{E}\cdot\partial
g_{i}^{0}/\partial\boldsymbol{k}$ with $\tau$ the relaxation time note-1 .

The current Eq. (3) can be further decomposed as

$\boldsymbol{J}=\boldsymbol{J}^{\text{L}}+\boldsymbol{J}^{\text{H}},$

where $\boldsymbol{J}^{\text{L}}=-e\int_{\boldsymbol{k}}\sum_{i}\delta
g_{i}\bar{\boldsymbol{v}}_{i}$ and

$\boldsymbol{J}^{\text{H}}=\boldsymbol{J}_{A}^{\text{H}}+\boldsymbol{J}_{R}^{\text{H}},$
(6a) in which
$\boldsymbol{J}_{A}^{\text{H}}=-e\int_{\boldsymbol{k}}\sum_{i}g_{i}^{0}\bar{\boldsymbol{v}}_{i}^{\text{coh},A},~{}\boldsymbol{J}_{R}^{\text{H}}=-e\int_{\boldsymbol{k}}\sum_{i}g_{i}^{0}\bar{\boldsymbol{v}}_{i}^{R}$
(6b) on knowing that
$\int_{\boldsymbol{k}}g_{i}^{0}\bar{\boldsymbol{v}}_{i}^{\text{occ},A}=0$ Mer
. These two contributions $\boldsymbol{J}^{\text{L}}$ and
$\boldsymbol{J}^{\text{H}}$ respectively reproduce the well-established
expressions of the longitudinal current and the Hall current in the limit of
infinitesimal $\boldsymbol{E}$ Niu ; Tu . In this work, we are only interested
in $\boldsymbol{J}^{\text{H}}$.

Within this framework, the issues raised in the introduction can now be
addressed. The first question is on the interplay between the respective
contributions to the Hall current arising from adiabatic coupling to remote
bands and from non-adiabatic dynamics within the active manifold. This can be
approached from the well-known notion that the Hall current is mediated by the
interband coherence Naga . Both contributions $\boldsymbol{J}_{A}^{\text{H}}$
and $\boldsymbol{J}_{R}^{\text{H}}$ contain interband coherence among the
active bands, namely,
$\left(\bar{\eta}_{n}^{i}\right)^{\ast}\bar{\eta}_{m}^{i}$ for $n\neq{m}$ with
$n,m\in{A}$. Such coherence in $\boldsymbol{J}_{A}^{\text{H}}$ explicated by
Eq. (4c) is directly formed through the field-induced interband transitions
within the active manifold. In contrast, for $\boldsymbol{J}_{R}^{\text{H}}$,
such coherence given by Eq. (5c) is only indirectly formed through transitions
forth and back between the active and the remote bands (see illustrations in
Fig. 1(c) and (d) respectively). This leads us to anticipate that the natures
of the Hall current manifested via $\boldsymbol{J}_{A}^{\text{H}}$ and
$\boldsymbol{J}_{R}^{\text{H}}$ can be very different.

The second question concerns the two faces of the multiple-band effects,
namely, the non-adiabatic dynamics and the non-Abelian characters of the Berry
curvatures. This can be viewed from the decomposition

$\boldsymbol{J}_{R}^{\text{H}}=\boldsymbol{J}_{\text{occ},R}^{\text{H}}+\boldsymbol{J}_{\text{coh},R}^{\text{H}},$
(7a) where
$\boldsymbol{J}_{\text{occ}/\text{coh},R}^{\text{H}}=-e\int_{\boldsymbol{k}}\sum_{i}g_{i}^{0}\bar{\boldsymbol{v}}_{i}^{\text{occ}/\text{coh},R}.$
(7b) When the active bands are fully degenerate over the Brillouin zone,
$\boldsymbol{J}_{\text{coh},R}^{\text{H}}$ has no contribution to the Hall
current, as we have discussed in Ref.Tu . There we have also shown that the
Hall current reduces to the well-established expression
$\boldsymbol{J}^{\text{H}}=\left(e^{2}/\hbar\right)\boldsymbol{E}\times\int_{\boldsymbol{k}}\text{Tr}\left(\boldsymbol{\mathcal{F}}_{\boldsymbol{k}}\right)$
Shi  when the degenerate band energy is set below the Fermi energy. The gauge
symmetry associated with band degeneracy can be utilized to study the non-
Abelian characters Wilczek842111 . For general non-degenerate bands, where
gauge symmetry is not expected, the non-Abelian characters of
$\mathcal{F}_{\boldsymbol{k}}^{z}$ as matrices are fully embedded in the
decomposition Eq. (7). In conjunction with Eq. (5), we find the two current
contributions $J_{\text{occ},R}^{\text{H}}$ and $J_{\text{coh},R}^{\text{H}}$
involve only the diagonals and the off-diagonals of
$\mathcal{F}_{\boldsymbol{k}}^{z}$ respectively, bearing also distinct
physical meanings as currents arising from band occupations and interband
coherence. Comparison between $J_{\text{occ},R}^{\text{H}}$ and
$J_{\text{coh},R}^{\text{H}}$ thus provides a mean to reveal the multiple-band
effects that underlie the Hall currents including both the non-Abelian
characters of $\mathcal{F}_{\boldsymbol{k}}^{z}$ and non-adiabatic effects
embedded in $\bar{\eta}_{n}^{i}$’s. In the following, we illustrate these
points in $AB$-stacked bilayer graphenes.

##  III The band manifolds of $AB$-stacked bilayer graphene

The energy dispersion relation, including both active and remote manifolds,
for $AB$-stacked bilayer graphene can be analytically obtained. In the basis
of the sublattices of the two layers 1 and 2, labeled as
$A_{1},B_{1},A_{2},B_{2}$ (see Fig. 1(a)), the effective four-band Hamiltonian
near the Dirac point $K\left(\text{or }K^{\prime}\right)$ can be expressed as
Mc2

$\mathcal{H}\left(\boldsymbol{k}\right)=\left(\begin{array}[]{cccc}\epsilon_{A_{1}}&f\pi^{\dagger}&-f_{4}\pi^{\dagger}&f_{3}\pi\\\
f\pi&\epsilon_{B_{1}}&\gamma_{1}&-f_{4}\pi^{\dagger}\\\
-f_{4}\pi&\gamma_{1}&\epsilon_{A_{2}}&f\pi^{\dagger}\\\
f_{3}\pi^{\dagger}&-f_{4}\pi&f\pi&\epsilon_{B_{2}}\end{array}\right)$ (8)

with $\pi=\xi k_{x}+ik_{y}$, $f=\sqrt{3}a\gamma_{0}/2$, and
$f_{3,4}=\sqrt{3}a\gamma_{3,4}/2$ in which $\xi=\pm 1$ is the valley index and
$a$ is the lattice constant. The on-site potentials can be represented
explicitly as $\epsilon_{A_{1}}=-\frac{1}{2}U$,
$\epsilon_{B_{1}}=\frac{1}{2}\left(-U+2\Delta^{\prime}\right)$,
$\epsilon_{A_{2}}=\frac{1}{2}\left(U+2\Delta^{\prime}\right)$, and
$\epsilon_{B_{2}}=\frac{1}{2}\left(U-\delta_{AB}\right)$, with $U$ the
interlayer asymmetry between the two layers, $\Delta^{\prime}$ for an energy
difference between dimer and non-dimer sites. The intralayer hopping between
the $A$ and $B$ sites is given by $\gamma_{0}$ and the meanings of various
interlayer couplings $\gamma_{i}$ with $i=1,3,4$ are indicated in Fig. 1(a).
Following Ref. Kuz , we fix $a=2.46\mathrm{\mathring{A}}$,
$\gamma_{0}=3.16\mathrm{eV}$, $\gamma_{1}=0.381\mathrm{eV}$ and
$\gamma_{4}=\Delta^{\prime}=0$ throughout this work.

The band energies obtained from diagonalising Eq. (8) is illustrated in Fig.
1(b) clearly show two bands around the Fermi energy. They are the lowest
conduction band and the highest valence band, indexed by $c$ and $v$
respectively, that form the active manifold. The remote bands consist of the
higher conduction band $c_{R}$ and the lower valence band $v_{R}$ (see Fig.
1(b)). The valley Hall current is
$\boldsymbol{J}^{\text{H}}=\boldsymbol{J}_{A}^{\text{H}}+\boldsymbol{J}_{R}^{\text{H}}$
detailed in Eq. (6). By Eqs. (6b) and (5), we see
$\boldsymbol{J}_{R}^{\text{H}}$ is perpendicular to $\boldsymbol{E}$. As shown
in an earlier study that for active manifolds with two bands,
$\boldsymbol{J}_{A}^{\text{H}}$ is also perpendicular to $\boldsymbol{E}$ Tu1
. We apply the polar coordinate, i.e., $\boldsymbol{E}=E\hat{\rho}$ with the
basis vector $\hat{\rho}=\hat{x}\cos\theta+\hat{y}\sin\theta$ and
$\hat{\theta}=-\hat{x}\sin\theta+\hat{y}\cos\theta$. Here
$E\equiv\left|\boldsymbol{E}\right|$ and $\theta$ is the angle between
$\boldsymbol{E}$ and $\hat{x}$. It is then sufficient to investigate the
scalars $J_{A/R}^{\text{H}}=\hat{\theta}\cdot\boldsymbol{J}_{A/R}^{\text{H}}$
and
$J_{\text{occ}/\text{coh},R}^{\text{H}}=\hat{\theta}\cdot\boldsymbol{J}_{\text{occ}/\text{coh},R}^{\text{H}}$.
For definiteness, we place the chemical potential $\mu$ in the middle of the
gap. Then only the lower-energy hybridised band, indexed by $i_{v}$, needs to
be counted at very low temperatures in $\sum_{i}$ in Eq. (6b). This simplifies
$J_{\text{occ}/\text{coh},R}^{\text{H}}=-e\int_{\boldsymbol{k}}\bar{v}_{i_{v}}^{\text{occ}/\text{coh},R}$
with
$\bar{v}_{i_{v}}^{\text{occ}/\text{coh},R}=\hat{\theta}\cdot\bar{\boldsymbol{v}}_{i_{v}}^{\text{occ}/\text{coh},R}$
(see Eqs. (5) and (6)) and
$J_{A}^{\text{H}}=-e\int_{\boldsymbol{k}}\bar{v}_{i_{v}}^{\text{coh},A}$ with
$\bar{v}_{i_{v}}^{\text{coh},A}=\hat{\theta}\cdot\bar{\boldsymbol{v}}_{i_{v}}^{\text{coh},A}$
(see Eqs. (4) and (6)).

##  IV Intra- versus inter-manifold contributions to the Hall currents

Since $\boldsymbol{E}=E\hat{\rho}(\theta)$ is a vector, $J_{A/R}^{\text{H}}$
in principle depends on both $E$ and $\theta$. When the dispersion of the
system is isotropic, then the dependence of $J^{\text{H}}$ on $\theta$
disappears. The two contributions $J_{A}^{\text{H}}$ and $J_{R}^{\text{H}}$
should depend on $E$ very distinctively. When the dispersion is anisotropic,
then $J_{A}^{\text{H}}$ and $J_{R}^{\text{H}}$ should also depend on $\theta$,
which characterises the orientation of the applied field, in very different
manners. We now discuss explicitly how these are revealed.

The isotropy of dispersion here for the $AB$-stacked bilayer graphenes is
determined by $\gamma_{3}$, an interlayer skew hopping parameter (see Fig.
1(a)). With $\gamma_{3}=0$, the distinction between $J_{A}^{\text{H}}$ and
$J_{R}^{\text{H}}$ is simply displayed in the order-of-magnitude difference
between the current values, plotted as functions of $E$ in Fig. 2(a) in unit
of $E_{0}$ rr . By defining

$r_{n,m}\left(\boldsymbol{k},\boldsymbol{E}\right)=\left|\frac{\left[\bar{\mathcal{R}}_{\boldsymbol{k}}\right]_{n,m}\cdot
e\boldsymbol{E}}{\varepsilon_{n}-\varepsilon_{m}}\right|$ (9)

as a dimensionless quantity that measures the ratio between the field-induced
interband coupling to the gap size Tu1  at a given $\boldsymbol{k}$, $E_{0}$
is the field strength that satisfies MAX
$r_{c,v}\left(\boldsymbol{k},E_{0}\right)=1$. One can calculate $J^{\text{H}}$
by the full-band formulation discussed in Ref. Tu , without separating the
contributions into $J_{A}^{\text{H}}$ and $J_{R}^{\text{H}}$. We have verified
that the computations here based on Eq. (6) agree with the results of full-
band calculation. The consistency with full-band calculation signifies that it
indeed makes sense to simultaneously speak of the adiabatic contribution (from
coupling to remote band), and the non-adiabatic contribution (from intra-
manifold coupling) to the Hall effect over a sizable range of the electric
field. In addition, under the condition $\gamma_{3}=0$, we found that
$J_{R}^{\text{H}}$ is entirely dominated by $J_{\text{occ},R}^{\text{H}}$ with
vanishing contribution from $J_{\text{coh},R}^{\text{H}}$ (see Fig. 2b)). We
will show that when $\gamma_{3}\neq 0$, more interesting differences between
$J_{\text{occ},R}^{\text{H}}$ and $J_{\text{coh},R}^{\text{H}}$ can arise.

Figure 2: (Color online) Under isotropic dispersion with $\gamma_{3}=0$,
different contributions to the Hall currents only depend on the magnitude $E$
of applied field $\boldsymbol{E}$. (a): The non-adiabatic intra-active-
manifold contribution $J_{A}^{\text{H}}$ and adiabatic inter-manifold
contribution $J_{R}^{\text{H}}$ show significant quantitative difference. (b):
The two components $J_{\text{occ},R}^{\text{H}}$ and
$J_{\text{coh},R}^{\text{H}}$ in Eq. (7a). Under such isotropic dispersion,
only the diagonals of the non-Abelian matrix are involved in the nonzero
contribution $J_{\text{occ},R}^{\text{H}}$ to $J_{R}^{\text{H}}$. Here the
currents are in unit of $J_{0}=e^{2}E_{0}/h$, where $E_{0}=1.15\mathrm{V/\mu
m}$ is chosen such that MAX $r_{c,v}\left(\boldsymbol{k},E_{0}\right)=1$ (see
Eq. (9)). The energy gap is $U=0.01\mathrm{eV}$.

When $\gamma_{3}\neq 0$ the anisotropy of the dispersion appears (see Fig.
3(a)), allowing non-trivial $\theta$-dependence of
$J_{R}^{\text{H}}=J_{\text{occ},R}^{\text{H}}+J_{\text{coh},R}^{\text{H}}$ and
$J_{A}^{\text{H}}$. From Eqs. (7) and (5), we see on one hand,
$J_{\text{occ},R}^{\text{H}}$ depends on $\theta$ through the band occupations
$\left|\bar{\eta}_{c}^{i_{v}}\right|^{2}$ and
$\left|\bar{\eta}_{v}^{i_{v}}\right|^{2}$ that have the same period in
$\theta$ in $\bar{v}_{i_{v}}^{\text{occ},R}$. On the other hand,
$J_{\text{coh},R}^{\text{H}}$ gains $\theta$-dependence through the interband
coherence $\left(\bar{\eta}_{c}^{i_{v}}\right)^{\ast}\bar{\eta}_{v}^{i_{v}}$
in $\bar{v}_{i_{v}}^{\text{coh},R}$. Explicitly, we have

$\left|\bar{\eta}_{c/v}^{i_{v}}\right|^{2}=\frac{1\mp\varepsilon_{g}/\bar{\varepsilon}_{g}}{2},~{}\left(\bar{\eta}_{c}^{i_{v}}\right)^{\ast}\bar{\eta}_{v}^{i_{v}}=-\frac{\left[\bar{\mathcal{R}}_{\boldsymbol{k}}\right]_{v,c}\cdot\boldsymbol{E}}{\bar{\varepsilon}_{g}}$
(10)

where $\varepsilon_{g}=\varepsilon_{c}-\varepsilon_{v}$ and

$\bar{\varepsilon}_{g}=\sqrt{\varepsilon_{g}^{2}+4\left|\left[\bar{\mathcal{R}}_{\boldsymbol{k}}\right]_{v,c}\cdot\boldsymbol{E}\right|^{2}}$
(11)

is the renormalized gap. Using
$\boldsymbol{E}=E(\hat{x}\cos\theta+\hat{y}\sin\theta)$, we straightforwardly
see that $\left(\bar{\eta}_{c}^{i_{v}}\right)^{\ast}\bar{\eta}_{v}^{i_{v}}$
has a $\theta$-period that is twice of that of
$\left|\bar{\eta}_{c}^{i_{v}}\right|^{2}$ and
$\left|\bar{\eta}_{v}^{i_{v}}\right|^{2}$. So the $\theta$-period of
$J_{R}^{\text{H}}$ is led by that of $J_{\text{coh},R}^{\text{H}}$, which is
associated with the interband coherence that appears in
$\bar{v}_{i_{v}}^{\text{coh},R}$ of Eq. (5).

We now turn to the $\theta$-dependence in $J_{A}^{\text{H}}$. From Eqs. (6)
and (4), we find that $J_{A}^{\text{H}}$ depends on $\theta$ through the term
$\left(\bar{\eta}_{c}^{i_{v}}\right)^{\ast}\bar{\eta}_{v}^{i_{v}}\hat{\theta}\cdot\partial\mathcal{H}_{A}/\partial\hbar\boldsymbol{k}$
that appears in $\bar{v}_{i_{v}}^{\text{coh},A}$. Here
$\hat{\theta}\cdot\partial\mathcal{H}_{A}/\partial\hbar\boldsymbol{k}=\left(-\sin\theta\partial\mathcal{H}_{A}/\partial\hbar{k}_{x}+\cos\theta\partial\mathcal{H}_{A}/\partial\hbar{k}_{y}\right)$
which makes the $\theta$-period of
$\left(\bar{\eta}_{c}^{i_{v}}\right)^{\ast}\bar{\eta}_{v}^{i_{v}}\hat{\theta}\cdot\partial\mathcal{H}_{A}/\partial\hbar\boldsymbol{k}$
only half as that of
$\left(\bar{\eta}_{c}^{i_{v}}\right)^{\ast}\bar{\eta}_{v}^{i_{v}}$. These two
different $\theta$-dependencies, namely,
$\left(\bar{\eta}_{c}^{i_{v}}\right)^{\ast}\bar{\eta}_{v}^{i_{v}}$ and
$\left(\bar{\eta}_{c}^{i_{v}}\right)^{\ast}\bar{\eta}_{v}^{i_{v}}\hat{\theta}\cdot\partial\mathcal{H}_{A}/\partial\hbar\boldsymbol{k}$,
are revealed correspondingly in the velocities
$\bar{v}_{i_{v}}^{\text{coh},R}$ and $\bar{v}_{i_{v}}^{\text{coh},A}$, plotted
as functions of $\theta$ in Fig. 3(b) and (c) respectively. It clearly shows
the distinctively different periods.

From the above analysis with also the aids of Eqs. (5) and (4), the
$\theta$-period of the average carrier velocity
$\bar{v}_{i_{v}}^{\text{coh},R}$ is twice as that of
$\bar{v}_{i_{v}}^{\text{coh},A}$ at arbitrary $\boldsymbol{k}$ regardless of
the dispersion is anisotropic or isotropic. The currents are obtained by
integrating the average carrier velocity over $\boldsymbol{k}$. The above
discussed $\theta$-period difference between $\bar{v}_{i_{v}}^{\text{coh},R}$
and $\bar{v}_{i_{v}}^{\text{coh},A}$ appears also in the difference between
$J_{R}^{\text{H}}$ and $J_{A}^{\text{H}}$ only when the dispersion of the
system is anisotropic. With $\gamma_{3}\neq 0$, which leads to a well-known
trigonal-warped dispersion Mc2 ; Kech , we show in Fig. 4(a) at a given valley
$\xi=1$ both current contributions $J_{R}^{\text{H}}$ and $J_{A}^{\text{H}}$.
It clearly shows that while $J_{R}^{\text{H}}$ follows the $C_{3}$ symmetry of
the energy dispersion, $J_{A}^{\text{H}}$ exhibits $C_{6}$ symmetry. The
$\theta$-period of the current is different from the $\boldsymbol{k}$-resolved
average carrier velocity due to integration over $\boldsymbol{k}$, which
manifests the symmetry of the dispersion. Nevertheless, the character that
$\bar{v}_{i_{v}}^{\text{coh},R}$ has its $\theta$-period twice as that of
$\bar{v}_{i_{v}}^{\text{coh},A}$ is fully revealed in the physical observable
that $J_{R}^{\text{H}}$’s $\theta$-period is twice of $J_{A}^{\text{H}}$’s.
The intuitively anticipated qualitative difference between $J_{A}^{\text{H}}$
and $J_{R}^{\text{H}}$ from Fig. 1(c) and (d) is thus concretely illustrated
through different periods in $\theta$.

Figure 3: (Color online) (a): The anisotropic dispersion of the bands near the
fermi energy, demonstrated with $\gamma_{3}=0.38\mathrm{eV}$ Kuz . Inset: The
trigonal warping of active conduction band, implying that the magnitude of the
Hall current (yellow arrows of different lengths) depends on the angle
$\theta$ between $\boldsymbol{E}$ (solid white arrows) and the crystal axis,
here taken as $\hat{x}$ (dashed white arrow). (b) and (c): Different
$\theta$-dependencies of the anomalous velocities
$\bar{v}_{i_{v}}^{\text{coh},R}$ and $\bar{v}_{i_{v}}^{\text{coh},A}$
respectively, giving rise to distinct periods in $\theta$ and determining the
anisotropic responses of $J_{R}^{\text{H}}$ and $J_{A}^{\text{H}}$ to $\theta$
(see the main text for details). The specific choice of $\boldsymbol{k}$ is
irrelevant. Here we use $k_{x}=0.01$Å and $k_{y}=0$. Other parameters follow
that used in Fig. 2 with $E=E_{0}$ here and $v_{F}=\sqrt{3}a\gamma_{0}/\hbar$
as the Fermi velocity.

##  V Two faces of multiple-band effects: non-adiabatic and non-Abelian

###  V.1 revelation on the Hall currents

We now focus on the remote band contribution $J_{R}^{\text{H}}$ to reveal the
relation between the underlying non-adiabatic dynamics and the non-Abelian
characters raised from the multi-band effects in the active manifold. As we
have mentioned before, when the active bands are fully degenerate and
occupied, the linear conductivity is given by
$\sigma^{\text{H}}=\left.\partial
J^{\text{H}}/\partial{E}\right|_{E=0}=\left(e^{2}/\hbar\right)\int_{\boldsymbol{k}}\text{Tr}\left(\mathcal{F}_{\boldsymbol{k}}^{z}\right)$,
which depends neither on $E$ nor on $\theta$, as a consequence of its
definition. Furthermore, this linear conductivity only involves the band
diagonals of the Berry curvature matrix $\mathcal{F}_{\boldsymbol{k}}^{z}$.

As discussed before, anisotropy of the dispersion can be revealed in the Hall
currents under the finite electric fields. In order to extract the
$\theta$-dependence more exclusively, we define
$\Delta{J}_{\text{coh}/\text{occ},R}^{\text{H}}=J_{\text{coh}/\text{occ},R}^{\text{H}}-\bar{J}_{\text{coh}/\text{occ},R}^{\text{H}}$,
where we subtract the angular average
$\bar{J}_{\text{coh}/\text{occ},R}^{\text{H}}=\left(1/\theta_{T}^{\text{coh}/\text{occ},R}\right)\int_{0}^{\theta_{T}^{\text{coh}/\text{occ},R}}\text{d}\theta{J}_{\text{coh}/\text{occ},R}^{\text{H}}$
in which $\theta_{T}^{\text{coh}/\text{occ},R}$ denotes the $\theta$-period of
$J_{\text{coh}/\text{occ},R}^{\text{H}}$. We plot
$\Delta{J}_{\text{coh},R}^{\text{H}}$ (solid line) and
$\Delta{J}_{\text{occ},R}^{\text{H}}$ (dashed line) as a function of $\theta$
in Fig. 4(b), which shows that
$\theta_{T}^{\text{coh},R}=2\theta_{T}^{\text{occ},R}$, as expected due to the
reasons already discussed for Fig. 3. More interestingly, in Fig. 4(b) we see
that $\Delta{J}_{\text{coh},R}^{\text{H}}$ displays a variation with respect
to $\theta$ that is clearly greater than that of
$\Delta{J}_{\text{occ},R}^{\text{H}}$. This is because the interband coherence
$\left(\bar{\eta}_{c}^{i_{v}}\right)^{\ast}\bar{\eta}_{v}^{i_{v}}$ in general
is more sensitive to $\theta$ than the occupation
$\left|\bar{\eta}_{c/v}^{i_{v}}\right|^{2}$ since the former is one order
larger in $E\cos\theta$ and $E\sin\theta$ than the latter (see Eq. (10)). Note
that in terms of
$J_{\text{coh}/\text{occ},R}^{\text{H}}=\Delta{J}_{\text{coh}/\text{occ},R}^{\text{H}}+\bar{J}_{\text{coh}/\text{occ},R}^{\text{H}}$,
we still have $J_{\text{occ},R}^{H}\gg J_{\text{coh},R}^{H}$ for
$\gamma_{3}\neq 0$. This is consistent with the observation in Fig. 2(b) where
$\gamma_{3}=0$. Importantly, it is the anisotropy (sensitivity to $\theta$’s
variation due to $\gamma_{3}\neq 0$) that pronounces the role of the off-
diagonal term, due to which the Berry curvature is said to be non-Abelian. The
underlying non-adiabatic dynamics, characterised by $\theta$-dependence at
finite $\boldsymbol{E}$, thus manifests the non-Abelian characters of
$\mathcal{F}_{\boldsymbol{k}}^{z}$, differentiating between the diagonal
$J_{\text{occ},R}^{\text{H}}$ and off-diagonal $J_{\text{coh},R}^{\text{H}}$
contributions.

Figure 4: (Color online) (a): The qualitative difference between
$J_{R}^{\text{H}}$ and $J_{A}^{\text{H}}$ revealed through distinct symmetries
($C_{3}$ for $J_{R}^{\text{H}}$ and $C_{6}$ for $J_{A}^{\text{H}}$). (b):
Angular variations of inter-band coherence
($\Delta{J}_{\text{coh},R}^{\text{H}}$ as the solid line) and band-occupation
($\Delta{J}_{\text{occ},R}^{\text{H}}$ as the dashed line) contributions,
respectively to the remote-band-mediated Hall current $J_{R}^{\text{H}}$,
contrasting the diagonal and the off-diagonal involvements of the non-Abelian
Berry curvature matrices. The parameters are same as what we take in Fig. 3
for both (b) and (c). The angular averages are
$\bar{J}_{\text{occ},R}^{\text{H}}=0.168J_{0}$ and
$\bar{J}_{\text{coh},R}^{\text{H}}=0$.

###  V.2 microscopic picture from $\boldsymbol{k}$-resolved processes

So far the two faces of multiple-band effects have been investigated through
the $\boldsymbol{k}$-integrated currents. To have a deeper insight, we revisit
the $\boldsymbol{k}$-resolved dimensionless quantity, Eq. (9). On one hand,
with the band indices $n=c,m=v\in{A}$, Eq. (9) measures the strength of non-
adiabatic intra-manifold transition with respect to the gap between active
bands $c$ and $v$. On the other hand, the underlying constituents of the non-
Abelian Berry curvature Eq. (1d), which can be rewritten as
$\left[\mathcal{F}_{\boldsymbol{k}}^{\alpha\beta}\right]_{\left(m^{\prime},m\right)\in{A}}=\sum_{n\in{R}}\left\\{i\left[\mathcal{R}_{k_{\alpha}}\right]_{m^{\prime},n}\left[\mathcal{R}_{k_{\beta}}\right]_{n,m}-(k_{\alpha}\leftrightarrow
k_{\beta})\right\\}$, are the inter-manifold Berry connections
$\left[\mathcal{R}_{k_{\beta}}\right]_{n,m}$ contained in Eq. (9) with
$n\in{R}$ and $m\in{A}$. We thus are able to explore the multiple-band effects
from the $\boldsymbol{k}$-resolved information of Eq. (9).

In Fig. 5, we inspect $\boldsymbol{k}$-dependencies of
$r_{c,v}\left(\boldsymbol{k},\boldsymbol{E}\right)$ (for non-adiabatic intra-
active-manifold dynamics) and
$r_{c_{R},v}\left(\boldsymbol{k},\boldsymbol{E}\right)$ (for constituents of
non-Abelian Berry curvatures) respectively for both cases $\gamma_{3}=0$ and
$\gamma_{3}\neq 0$. The $\boldsymbol{k}$-dependence of $r_{c,v}$ follows the
symmetry of $\boldsymbol{k}$-dependence of band energies
$\varepsilon_{c/v}(\boldsymbol{k})$ (see Fig. 5(a) and (c) with respective
energy dispersion in mind).note-2  In contrast, $r_{c_{R},v}$ for
$\gamma_{3}=0$ and that for $\gamma_{3}\neq 0$ have similar patterns in
$\boldsymbol{k}$-dependence (see Fig. 5(b) and (d)) that are distinct from the
$\boldsymbol{k}$-dependence pattern of $r_{c,v}$’s in Fig. 5(a) and (c).
Regardless of $\gamma_{3}=0$ or $\gamma_{3}\neq 0$, $r_{c_{R},v}$’s do not
follow the symmetry of energy dispersion in $\boldsymbol{k}$-dependence. This
provides the insight that the non-adiabatic interband transitions and the
transitions giving rise to non-Abelian Berry curvatures, where both are
responsible for Hall currents, are fundamentally different in their natures.

As discussed before with an analysis of $J^{\text{H}}$’s dependence on
$\boldsymbol{E}$’s orientation, such qualitative difference can be seen from
$\boldsymbol{k}$-integrated currents only when the energy dispersion is
anisotropic. Crucially, even without energy anisotropy, the qualitative
differences in the microscopic $\boldsymbol{k}$-resolved processes already
underlie the origin that the non-adiabatic contribution to the Hall current is
physically distinct from the adiabatic one, as a result of multiple-band
effects.

Figure 5: (Color online) Visualization of the dimensionless non-adiabatic
measure $r_{n,m}(\boldsymbol{k},\boldsymbol{E}=E_{0}\hat{x})$ in the
$\boldsymbol{k}$-space for both isotropic ($\gamma_{3}=0$ as (a) and (b)) and
anisotropic ($\gamma_{3}=0.38\mathrm{eV}$ as (c) and (d)) dispersions. Other
parameters are the same as in Fig. 2 (for $\gamma_{3}=0$) and Fig. 3 (for
$\gamma_{3}\neq 0$). Similarity between (b) and (d) is contrasted with
dissimilarity between (a) and (c) to reveal the distinctness of non-adiabatic
interband transitions as a multiple-band effect.

##  VI Conclusions and discussions

In summary, through the studies of the valley Hall currents in typical
$AB$-stacked bilayer graphenes as an example, we have demonstrated the
followings. (i): The adiabatic inter-manifold contribution and the non-
adiabatic intra-active-manifold contribution to the Hall current not only
differ quantitatively about an order of magnitude due to the perturbation role
of the electric field in the adiabatic inter-manifold transition processes.
They also differ qualitatively in terms of the periodicity with respect to the
angle of the applied electric field. (ii): The non-Abelian characters due to
the multiple-band nature of the active manifold are manifested by the
difference between the diagonal and the off-diagonal contributions to the Hall
current in terms not only of the periodicity with respect to the angle of the
applied electric field but also of the angular variation amplitude.

The values of the angular periods and the shapes of the angular profiles for
different contributions to the Hall currents depend on the details of the
materials’ electronic structures under consideration. Nevertheless, the
conclusions (i) and (ii), confirmed by the calculations specifically
designated to $AB$-stacked bilayer graphenes, are expected to be held also for
other materials with anisotropic energy dispersion such that the Hall current
at finite electric fields is sensitive to the orientation of the field. This
is because the general analysis leading to the above conclusions is simply
rooted to how band occupation and interband coherence differ fundamentally in
their responses to the applied electric field (as exemplified for two-band
active manifold in Eq. (10)). This fundamental difference also serves as the
basis to manifest the multiple-band induced non-Abelian effects in Hall
currents. Interestingly, this provides an intuitive approach toward the
understanding of the non-Abelian characters, totally based on physically
observable carrier transport currents, as complementary to the conventionally
more mathematically oriented understanding based on quantum geometry of the
band structures alone.

## Acknowledgments

C. Li would like to thank D. W. Zhai and B. Fu for useful discussions. The
work is mainly supported by the Research Grants Council of Hong Kong
(HKU17306819 and AoE/P-701/20), and the University of Hong Kong (Seed Funding
for Strategic Interdisciplinary Research). M. W.-Y. Tu acknowledge the the
hospitality of Prof. Tay-Rong Chang with support from ministry of technology
and science in Taiwan of grand no. MOST110-2636-M-006-016. M. W.-Y. Tu also
acknowledge the hospitality of National Center for Theoretical Science and
thank Prof. Tse-Min Chen for useful discussions.

## References

  * (1) N. W. Ashcroft and N. D. Mermin, Solid State Physics (Sounders College, Philadelphia, 1976).
  * (2) R. Karplus and J. M. Luttinger, Hall effect in ferromagnetics, Phys. Rev. 95, 1154 (1954).
  * (3) J. M. Luttinger, Theory of the Hall effect in ferromagnetic substances, Phys. Rev. 112, 739 (1958).
  * (4) E. Adams and E. Blount, Energy bands in the presence of an external force field-II: Anomalous velocities, J. Phys. Chem. Solids 10, 286 (1959).
  * (5) D. J. Thouless, M. Kohmoto, M. P. Nightingale, and M. D. Nijs, Quantized Hall Conductance in a Two-Dimensional Periodic Potential, Phys. Rev. Lett. 49, 405 (1982).
  * (6) T. Jungwirth, Q. Niu, and A. H. MacDonald, Anomalous Hall Effect in Ferromagnetic Semiconductors, Phys. Rev. Lett. 88, 207208 (2002).
  * (7) N. Nagaosa, J. Sinova, S. Onoda, A. H. MacDonald, and N. P. Ong, Anomalous Hall effect, Rev. Mod. Phys. 82, 1539 (2010).
  * (8) D. Xiao, M.-C. Chang, and Q. Niu, Berry phase effects on electronic properties, Rev. Mod. Phys. 82, 1959 (2010).
  * (9) S. Murakami, N. Nagaosa, and S.-C. Zhang, Dissipationless quantum spin current at room temperature, Science 301, 1348 (2003).
  * (10) S. Murakami, N. Nagaosa, and S. C. Zhang, Phys. Rev. B 69, 235206 (2004).
  * (11) J. Sinova, D. Culcer, Q. Niu, N. A. Sinitsyn, T. Jungwirth, and A. H. MacDonald, Universal Intrinsic Spin Hall Effect, Phys. Rev. Lett. 92, 126603 (2004).
  * (12) C. L. Kane and E. J. Mele, $Z_{2}$ Topological Order and the Quantum Spin Hall Effect, Phys. Rev. Lett. 95, 146802 (2005).
  * (13) D. Xiao, W. Yao, and Q. Niu, Valley-Contrasting Physics in Graphene: Magnetic Moment and Topological Transport, Phys. Rev. Lett. 99, 236809 (2007).
  * (14) D. Xiao, G.-B. Liu, W. Feng, X. Xu, and W. Yao, Coupled Spin and Valley Physics in Monolayers of MoS2 and Other Group-VI Dichalcogenides, Phys. Rev. Lett. 108, 196802 (2012).
  * (15) M. W. Y. Tu, C. Li, H. Y. Yu, and W. Yao, Non-adiabatic Hall effect at Berry curvature hot spot, 2D Materials 7, 4 (2020).
  * (16) M. W. Y. Tu, C. Li, and W. Yao, Theory of wave-packet transport under narrow gaps and spatial textures: Nonadiabaticity and semiclassicality, Phys. Rev. B 102, 045423 (2020).
  * (17) Y. Wang, Z. Wang, W. Yao, G. B. Liu, and H. Y. Yu, Interlayer coupling in commensurate and incommensurate bilayer structures of transition-metal dichalcogenides, Phys. Rev. B 95, 115429 (2017).
  * (18) F. C. Wu T. Lovorn, E. Tutuc, I. Martin, and A. H. MacDonald, Topological Insulators in Twisted Transition Metal Dichalcogenide Homobilayers, Phys. Rev. Lett. 122, 086402 (2019).
  * (19) D. W. Zhai and W. Yao, Theory of tunable flux lattices in the homobilayer moiré of twisted and uniformly strained transition metal dichalcogenides, Phys. Rev. Mat 4, 094002 (2020).
  * (20) H. Y. Yu, M. X. Chen, and W. Yao, Giant magnetic field from moiré induced Berry phase in homobilayer semiconductors, Natl. Sci. Rev 7, 12-20 (2020).
  * (21) E. McCann and M. Koshino, The electronic properties of bilayer graphene, Rep. Prog. Phys. 76, 5 (2013).
  * (22) Q. Niu, M. C. Cheng, B. Wu, D. Xiao, and R. Cheng, Physical Effects of Geometric Phases (World Scientific, 2017).
  * (23) A. Böhm, H. Koizumi, Q. Niu, J. Zwanziger, and A. Mostafazadeh, The Geometric Phase in Quantum Systems (Springer, 2003).
  * (24) R. Shindou and K. I. Imura, Noncommutative geometry and non-Abelian Berry phase in the wave-packet dynamics of Bloch electrons, Nucl. Phys. B 720, 399 (2005).
  * (25) D. Culcer, Y. Yao, and Q. Niu, Coherent wave-packet evolution in coupled bands, Phys. Rev. B, 72, 085110 (2005).
  * (26) M.-C. Chang and Q. Niu, Berry curvature, orbital moment, and effective quantum theory of electrons in electromagnetic fields, J. Phys.: Condens. Matter 20, 193202 (2008).
  * (27) E. V. Gorbar, V. A. Miransky, I. A. Shovkovy, and P. O. Sukhachov, Non-Abelian properties of electron wave packets in the Dirac semimetals $\text{A}_{3}$Bi (A=Na,K,Rb), Phys. Rev. B 98, 045203 (2018).
  * (28) T. Stedman, C. Timm and L. M. Woods, Multiband effects in equations of motion of observables beyond the semiclassical approach, New J. Phys. 21, 103007 (2019).
  * (29) K. S. Novoselov, et. al, Unconventional quantum Hall effect and Berry’s phase of $2\pi$ in bilayer graphene, Nat. Phys. 2, 177 (2006).
  * (30) E. McCann and V. I. Fal’ko, Landau-Level Degeneracy and Quantum Hall Effect in a Graphite Bilayer, Phys. Rev. Lett. 96, 086805 (2006).
  * (31) T. Ohta, A. Bostwick, T. Seyller, K. Horn, and E. Rotenberg, Controlling the Electronic Structure of Bilayer Graphene, Science 313, 951 (2006).
  * (32) E. McCann, Asymmetry gap in the electronic band structure of bilayer graphene, Phys. Rev. B 74, 161403(R) (2006).
  * (33) E. V. Castro, et al, Biased Bilayer Graphene: Semiconductor with a Gap Tunable by the Electric Field Effect, Phys. Rev. Lett. 99, 216802 (2007).
  * (34) J. B. Oostinga, H. B. Heersche, X. L. Liu, A. F. Morpurgo, and L. M. K. Vandersypen, Gate-induced insulating state in bilayer graphene devices, Nat. Mater. 7, 151 (2008).
  * (35) Y. B. Zhang, et al, Direct observation of a widely tunable bandgap in bilayer graphene, Nature 459, 820 (2009).
  * (36) L. Yang, J. Deslippe, C. H. Park, M. L. Cohen, and S. G. Louie, Excitonic Effects on the Optical Response of Graphene and Bilayer Graphene, Phys. Rev. Lett. 103, 186802 (2009).
  * (37) L. Ju, et al, Topological valley transport at bilayer graphene domain walls, Nature 520, 650 (2015).
  * (38) K. Kang, T. Li, E. Sohn, J. Shan, and K. F. Mak, Nonlinear anomalous Hall effect in few-layer $\text{WTe}_{2}$, Nat. Mater. 18, 324 (2019).
  * (39) The nonlinear Hall effect supported by Berry curvature dipoles aims at the higher-order action of an ac electric field on the off-equilibrium distribution where extrinsic scattering plays important roles. It keeps a single band in the active manifold so the remote band effects are well accounted adiabatically, giving rise to the Abelian Berry curvature Sodemann15216806 ; Du193047 . Here instead we are interested in the non-perturbation action of a dc electric field on intrinsic inter-band transitions within the multiple-band active manifold, where remote band effects are manifested by non-Abelian Berry curvatures.
  * (40) I. Sodemann and L. Fu, Quantum Nonlinear Hall Effect Induced by Berry Curvature Dipole in Time-Reversal Invariant Materials, Phys. Rev. Lett. 115, 216806 (2015).
  * (41) Z. Z. Du, C. M. Wang, S. Li, H.-Z. Lu, and X. C. Xie, Disorder-induced nonlinear Hall effect with time-reversal symmetry, Nat. Commun. 10, 3047 (2019).
  * (42) The ensemble-averaged velocity $\bar{\boldsymbol{v}}_{i}$ given in Eq. (3b) though looks similar to the velocity expression of a single wave packet $\dot{\boldsymbol{r}}$ given by the first line of Eq. (1a) in terms of the decomposition into intra-manifold and inter-manifold processes, they are fundamentally different. The velocity in Eq. (1a) is obtained by the full coherent evolution of a single wave packet. Its value at a given instance on which the wave packet has been driven to carry the momentum $\boldsymbol{k}$ is fully dependent on the non-Markov history of band amplitudes and the Bloch momentum of the wave packet. Henceforth $\dot{\boldsymbol{r}}$ is not fixed by the present $\boldsymbol{k}$ and $\boldsymbol{E}$ alone. The ensemble-averaged velocity is obtained from taking into account the Markov decoherence process through the evaluation of the density operator in the steady-state limit at each $\boldsymbol{k}$. Therefore, $\bar{\boldsymbol{v}}_{i}$ is fully determined by $\boldsymbol{k}$ and $\boldsymbol{E}$. The integral in Eq. (3a) for the current arising from an ensemble of wave packets is then well-defined. See more details in Ref.Tu .
  * (43) F. Wilczek and A. Zee, Appearance of gauge structure in simple dynamical systems, Phys. Rev. Lett. 52, 2111 (1984).
  * (44) We have shown analytically in Ref. Tu  that by taking the dimensionless quantities $\left|\mathcal{\bar{R}}_{n_{R},m_{A}}\cdot E/\left(\varepsilon_{n_{R}}-\varepsilon_{m_{A}}\right)\right|$, where $n_{R}/m_{A}$ belong to remote/active bands, as perturbation to the first order, $J_{R}^{\text{H}}$ reduces to the form with non-Abelian Berry curvature as shown in Eqs. (5) and (6). Since this is a perturbtion result, $J_{R}^{\text{H}}$ of course is expected to be small. Here this anticipation is verified in the numerical calculation.
  * (45) A. B. Kuzmenko, I. Crassee, D. van der Marel, P. Blake, and K. S. Novoselov, Determination of the gate-tunable band gap and tight-binding parameters in bilayer graphene using infrared spectroscopy, Phys. Rev. B 80, 165406 (2009).
  * (46) K. Kechedzhi, V. I. Fal’ko, E. McCann, and B. L. Altshuler, Influence of Trigonal Warping on Interference Effects in Bilayer Graphene, Phys. Rev. Lett. 98, 176806 (2007).
  * (47) Usually $r_{c,v}$ is peaked at the Dirac point because the gap size there is the smallest. Nevertheless in Fig. 5(a), with $\gamma_{3}=0$ the Berry connection there vanishes, namely, $\left[\mathcal{R}_{\boldsymbol{k}=0}\right]_{c,v}=0$. The band structure is dramatically changed by $\gamma_{3}\neq 0$ with the trigonal warping effect also visible in $r_{c,v}$. The directionality of $\boldsymbol{E}$ (here set in the direction of $\hat{x}$) slightly deviates $r_{c,v}$’s $\boldsymbol{k}$-dependence from the symmetry of energy dispersion, as a result of definition of Eq. (9). Noticeably, the anisotropy of energy dispersion with $\gamma_{3}\neq 0$ is also accompanied by stronger non-adiabatic intra-manifold transition effects with respect to the same value of gap (see the differences in color bars between Fig. 5(a) and Fig. 5(c)).


$Id:espcrc1.tex,v1.22004/02/2411:22:11speppingExp$ Further results on the
deficiency of graphsP.A. Petrosyan, H.H. Khachatrian

# Further results on the deficiency of graphs

P.A. Petrosyan, H.H. Khachatrian[MCSD] 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

###### Abstract

A _proper $t$-edge-coloring_ of a graph $G$ is a mapping
$\alpha:E(G)\rightarrow\\{1,\ldots,t\\}$ such that all colors are used, and
$\alpha(e)\neq\alpha(e^{\prime})$ for every pair of adjacent edges
$e,e^{\prime}\in E(G)$. If $\alpha$ is a proper edge-coloring of a graph $G$
and $v\in V(G)$, then _the spectrum of a vertex $v$_, denoted by
$S\left(v,\alpha\right)$, is the set of all colors appearing on edges incident
to $v$. _The deficiency of $\alpha$ at vertex $v\in V(G)$_, denoted by
$def(v,\alpha)$, is the minimum number of integers which must be added to
$S\left(v,\alpha\right)$ to form an interval, and _the deficiency
$def\left(G,\alpha\right)$ of a proper edge-coloring $\alpha$ of $G$_ is
defined as the sum $\sum_{v\in V(G)}def(v,\alpha)$. _The deficiency of a graph
$G$_, denoted by $def(G)$, is defined as follows:
$def(G)=\min_{\alpha}def\left(G,\alpha\right)$, where minimum is taken over
all possible proper edge-colorings of $G$. For a graph $G$, the smallest and
the largest values of $t$ for which it has a proper $t$-edge-coloring $\alpha$
with deficiency $def(G,\alpha)=def(G)$ are denoted by $w_{def}(G)$ and
$W_{def}(G)$, respectively. In this paper, we obtain some bounds on
$w_{def}(G)$ and $W_{def}(G)$. In particular, we show that for any
$l\in\mathbb{N}$, there exists a graph $G$ such that $def(G)>0$ and
$W_{def}(G)-w_{def}(G)\geq l$. It is known that for the complete graph
$K_{2n+1}$, $def(K_{2n+1})=n$ ($n\in\mathbb{N}$). Recently, Borowiecka-
Olszewska, Drgas-Burchardt and Hałuszczak posed the following conjecture on
the deficiency of near-complete graphs: if $n\in\mathbb{N}$, then
$def(K_{2n+1}-e)=n-1$. In this paper, we confirm this conjecture.

Keywords: proper edge-coloring, interval (consecutive) coloring, deficiency,
complete graph, near-complete graph.

Dedicated to the memory of Haroutiun Khachatrian

##  1 Introduction

All graphs considered in this paper 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 V(G)$ is denoted by
$d_{G}(v)$, the diameter of $G$ by $\mathrm{diam}(G)$, and the chromatic index
of $G$ by $\chi^{\prime}(G)$. For a graph $G$, let $\Delta(G)$ and $\delta(G)$
denote the maximum and minimum degrees of vertices in $G$, respectively. The
terms and concepts that we do not define can be found in [4, 24, 37].

A _proper $t$-edge-coloring_ of a graph $G$ is a mapping
$\alpha:E(G)\rightarrow\\{1,\ldots,t\\}$ such that all colors are used, and
$\alpha(e)\neq\alpha(e^{\prime})$ for every pair of adjacent edges
$e,e^{\prime}\in E(G)$. If $\alpha$ is a proper edge-coloring of a graph $G$
and $v\in V(G)$, then _the spectrum of a vertex $v$_, denoted by
$S\left(v,\alpha\right)$, is the set of all colors appearing on edges incident
to $v$. A proper $t$-edge-coloring $\alpha$ of a graph $G$ is an _interval
$t$-coloring_ if for each vertex $v$ of $G$, the set $S\left(v,\alpha\right)$
is an interval of integers. A graph $G$ is _interval colorable_ if it has an
interval $t$-coloring for some positive integer $t$. The set of all interval
colorable graphs is denoted by $\mathfrak{N}$. For a graph $G\in\mathfrak{N}$,
the smallest and the largest values of $t$ for which it has an interval
$t$-coloring are denoted by $w(G)$ and $W(G)$, respectively. The concept of
interval edge-coloring of graphs was introduced by Asratian and Kamalian [2]
in 1987. In [2], the authors proved that if $G\in\mathfrak{N}$, then
$\chi^{\prime}\left(G\right)=\Delta(G)$. Asratian and Kamalian also proved [2,
3] that if a triangle-free graph $G$ admits an interval $t$-coloring, then
$t\leq\left|V(G)\right|-1$. In [18, 19], Kamalian investigated interval
colorings of complete bipartite graphs and trees. In particular, he proved
that the complete bipartite graph $K_{m,n}$ has an interval $t$-coloring if
and only if $m+n-\gcd(m,n)\leq t\leq m+n-1$, where $\gcd(m,n)$ is the greatest
common divisor of $m$ and $n$. In [25, 28], Petrosyan, Khachatrian and
Tananyan proved that the $n$-dimesional cube $Q_{n}$ has an interval
$t$-coloring if and only if $n\leq t\leq\frac{n\left(n+1\right)}{2}$. The
problem of determining whether or not a given graph is interval colorable is
$NP$-complete, even for regular [2] and bipartite [33] graphs. In some papers
[2, 3, 11, 12, 16, 17, 18, 19, 24, 25, 27, 28, 29, 30, 33], the problems of
the existence, construction and estimating of the numerical parameters of
interval colorings of graphs were investigated.

It is known that there are graphs that have no interval colorings. A smallest
example is $K_{3}$. Since not all graphs admit an interval coloring, it is
naturally to consider a measure of closeness for a graph to be interval
colorable. In [13], Giaro, Kubale and Małafiejski introduced such a measure
which is called deficiency of a graph (another measure was suggested in [32]).
The _deficiency $def(G)$ of a graph $G$_ is the minimum number of pendant
edges whose attachment to $G$ makes it interval colorable. The concept of
deficiency of graphs can be also defined using proper edge-colorings. _The
deficiency of a proper edge-coloring $\alpha$ at vertex $v\in V(G)$_, denoted
by $def(v,\alpha)$, is the minimum number of integers which must be added to
$S\left(v,\alpha\right)$ to form an interval, and _the deficiency
$def\left(G,\alpha\right)$ of a proper edge-coloring $\alpha$ of $G$_ is
defined as the sum $\sum_{v\in V(G)}def(v,\alpha)$. In fact,
$def(G)=\min_{\alpha}def\left(G,\alpha\right)$, where minimum is taken over
all possible proper edge-colorings of $G$. The problem of determining the
deficiency of a graph is $NP$-complete, even for regular and bipartite graphs
[2, 33, 13]. In [13], Giaro, Kubale and Małafiejski obtained some results on
the deficiency of bipartite graphs. In particular, they showed that there are
bipartite graphs whose deficiency approaches the number of vertices. In [14],
the same authors proved that if $G$ is an $r$-regular graph with an odd number
of vertices, then $def(G)\geq\frac{r}{2}$, and determined the deficiency of
odd cycles, complete graphs, wheels and broken wheels. In [34], Schwartz
investigated the deficiency of regular graphs. In particular, he obtained
tight bounds on the deficiency of regular graphs and proved that there are
regular graphs with high deficiency. Bouchard, Hertz and Desaulniers [9]
derived some lower bounds for the deficiency of graphs and provided a tabu
search algorithm for finding a proper edge-coloring with minimum deficiency of
a graph. Recently, Borowiecka-Olszewska, Drgas-Burchardt and Hałuszczak [7]
studied the deficiency of $k$-trees. In particular, they determined the
deficiency of all $k$-trees with maximum degree at most $2k$, where
$k\in\\{2,3,4\\}$. They also proved that the following lower bound for
$def(G)$ holds: if $G$ is a graph with an odd number of vertices, then
$def(G)\geq\frac{2|E(G)|-(|V(G)|-1)\Delta(G)}{2}$. In the same paper,
Borowiecka-Olszewska, Drgas-Burchardt and Hałuszczak posed the following
conjecture on the deficiency of near-complete graphs: if $n\in\mathbb{N}$,
then $def(K_{2n+1}-e)=n-1$.

For a graph $G$, the smallest and the largest values of $t$ for which it has a
proper $t$-edge-coloring $\alpha$ with deficiency $def(G,\alpha)=def(G)$ are
denoted by $w_{def}(G)$ and $W_{def}(G)$, respectively. In this paper, we
obtain some bounds on $w_{def}(G)$ and $W_{def}(G)$. We also determine the
deficiency of certain graphs. In particular, we confirm the above-mentioned
conjecture of Borowiecka-Olszewska, Drgas-Burchardt and Hałuszczak.

##  2 Notation, definitions and auxiliary results

We use standard notation $C_{n}$ and $K_{n}$ for the simple cycle and complete
graph on $n$ vertices, respectively. We also use standard notation $K_{m,n}$
and $K_{l,m,n}$ for the complete bipartite and tripartite graph, respectively,
one part of which has $m$ vertices, other part has $n$ vertices and a third
part has $l$ vertices.

For two positive integers $a$ and $b$ with $a\leq b$, we denote by
$\left[a,b\right]$ the interval of integers
$\left\\{a,a+1,\ldots,b-1,b\right\\}$. If $a>b$, then
$\left[a,b\right]=\emptyset$.

Let $A$ be a finite set of integers. The deficiency $def(A)$ of $A$ is the
number of integers between $\min A$ and $\max A$ not belonging to $A$.
Clearly, $def(A)=\max A-\min A-|A|+1$. A set $A$ with $def(A)=0$ is an
interval.

If $\alpha$ is a proper edge-coloring of a graph $G$ and $v\in V(G)$, then the
spectrum of a vertex $v$, denoted by $S\left(v,\alpha\right)$, is the set of
colors appearing on edges incident to $v$. The smallest and largest colors of
$S\left(v,\alpha\right)$ are denoted by $\underline{S}\left(v,\alpha\right)$
and $\overline{S}\left(v,\alpha\right)$, respectively. If $\alpha$ is a proper
edge-coloring of a graph $G$ and $V^{\prime}\subseteq V(G)$, then we can
define $S\left(V^{\prime},\alpha\right)$ as follows:
$S\left(V^{\prime},\alpha\right)=\bigcup_{v\in
V^{\prime}}S\left(v,\alpha\right)$. The smallest and largest colors of
$S\left(V^{\prime},\alpha\right)$ are denoted by
$\underline{S}\left(V^{\prime},\alpha\right)$ and
$\overline{S}\left(V^{\prime},\alpha\right)$, respectively. The deficiency of
$\alpha$ at vertex $v\in V(G)$, denoted by $def(v,\alpha)$, is defined as
follows: $def(v,\alpha)=def\left(S\left(v,\alpha\right)\right)$. The
deficiency of a proper edge-coloring $\alpha$ of $G$ is defined as the sum
$def\left(G,\alpha\right)=\sum_{v\in V(G)}def(v,\alpha)$. For a graph $G$,
define the deficiency $def(G)$ as follows:
$def(G)=\min_{\alpha}def\left(G,\alpha\right)$, where minimum is taken over
all possible proper edge-colorings of $G$. Clearly, $def(G)=0$ if and only if
$G\in\mathfrak{N}$. Also, it is easy to see that $def(G)$ can be defined as
the minimum number of pendant edges whose attachment to $G$ makes it interval
colorable. For a graph $G$, the smallest and the largest values of $t$ for
which it has a proper $t$-edge-coloring $\alpha$ with deficiency
$def(G,\alpha)=def(G)$ are denoted by $w_{def}(G)$ and $W_{def}(G)$,
respectively. Clearly, if for a graph $G$, $def(G)=0$, then $w_{def}(G)=w(G)$
and $W_{def}(G)=W(G)$.

We will use the following five results.

######  Theorem 2.1.

[2, 3] If $G\in\mathfrak{N}$, then $\chi^{\prime}(G)=\Delta(G)$. Moreover, if
$G$ is a regular graph, then $G\in\mathfrak{N}$ if and only if
$\chi^{\prime}(G)=\Delta(G)$.

######  Theorem 2.2.

[2, 3] If $G$ is a regular graph and $G\in\mathfrak{N}$, then for every $t$,
$w(G)\leq t\leq W(G)$, $G$ has an interval $t$-coloring.

######  Theorem 2.3.

[2, 3] If $G$ is a triangle-free graph and $G\in\mathfrak{N}$, then
$W(G)\leq|V(G)|-1$.

######  Theorem 2.4.

[5] If $G$ is a planar graph and $G\in\mathfrak{N}$, then
$W(G)\leq\frac{11}{6}|V(G)|$.

######  Theorem 2.5.

[15] For any $m,n\in\mathbb{N}$, $K_{1,m,n}\in\mathfrak{N}$ if and only if
$\gcd(m+1,n+1)=1$. Moreover, if $\gcd(m+1,n+1)=1$, then
$w\left(K_{1,m,n}\right)=m+n$.

We also need the following lemma on a special interval coloring of the
complete bipartite graph $K_{p,p}$.

######  Lemma 2.6.

If $K_{p,p}$ is a complete bipartite graph with bipartition $(X,Y)$, where
$X=\\{x_{1},\ldots,x_{p}\\}$ and $Y=\\{y_{1},\ldots,y_{p}\\}$, then $K_{p,p}$
has an interval coloring $\beta$ such that
$\underline{S}(x_{i},\beta)=\underline{S}(y_{i},\beta)=\left\lfloor\frac{i}{2}\right\rfloor+1$
for $1\leq i\leq p$.

###### Proof.

We construct an edge-coloring $\beta$ of $K_{p,p}$ in the following way: for
every $1\leq k\leq\left\lfloor\frac{p}{2}\right\rfloor$, let

$\beta\left(x_{i}y_{j}\right)=\left\\{\begin{tabular}[]{ll}$k$,&if
$i+j=2k$,\\\ $k+p$,&if $i+j=2k+p$.\\\ \end{tabular}\right.$

At this point exactly $\left\lfloor\frac{p}{2}\right\rfloor$ edges incident to
each vertex are colored. Let $H$ denote the subgraph of $K_{p,p}$ which
contains all vertices of $K_{p,p}$ but only its non-colored edges. Clearly,
$H$ is a $\left\lceil\frac{p}{2}\right\rceil$-regular bipartite graph, so, by
König’s edge-coloring theorem, it has a proper
$\left\lceil\frac{p}{2}\right\rceil$-edge-coloring $\beta^{\prime}$. We
complete the edge-coloring $\beta$ of $K_{p,p}$ by shifting the colors from
$\beta^{\prime}$ by $\left\lfloor\frac{p}{2}\right\rfloor$. For every $e\in
E(H)$, let

$\displaystyle\beta(e)=\beta^{\prime}(e)+\left\lfloor\frac{p}{2}\right\rfloor.$

The resulting spectrums of the vertices $x_{i}$ and $y_{i}$ ($1\leq i\leq p$)
are the following:

$\displaystyle
S(x_{i},\beta)=S(y_{i},\beta)=\left[\left\lfloor\frac{i}{2}\right\rfloor+1,\left\lfloor\frac{p}{2}\right\rfloor\right]\cup\left[1+p,\left\lfloor\frac{i}{2}\right\rfloor+p\right]\cup\left[\left\lfloor\frac{p}{2}\right\rfloor+1,p\right],$

where the last interval comes from the subgraph $H$ and is common for all
vertices of $K_{p,p}$. The union of these intervals is

$\displaystyle
S(x_{i},\beta)=S(y_{i},\beta)=\left[\left\lfloor\frac{i}{2}\right\rfloor+1,\left\lfloor\frac{i}{2}\right\rfloor+p\right](1\leq
i\leq p).$

∎

Note that this lemma is a partial case of Lemma 4 from [35].

##  3 Some bounds on $w_{def}(G)$ and $W_{def}(G)$

Recently, in [1], Altinakar, Caporossi and Hertz proved that if $G$ has at
least three vertices, then $W_{def}(G)\leq 2|V(G)|-4+def(G)$. Here, we provide
some other bounds for the parameters $w_{def}(G)$ and $W_{def}(G)$ depending
on the number of vertices, degrees and diameter for connected, triangle-free
and planar graphs.

######  Theorem 3.1.

Let $\mathfrak{C}$ be a class of graphs closed under the operation of
attaching of pendant edges. If $W(G^{\prime})\leq f(|V(G^{\prime})|)$ holds
for any graph $G^{\prime}\in\mathfrak{C}\cap\mathfrak{N}$, then for any graph
$G\in\mathfrak{C}$, we have

$W_{def}(G)\leq f\left(|V(G)|+def(G)\right)$.

###### Proof.

Let $G\in\mathfrak{C}$ and $\alpha$ be a proper $W_{def}(G)$-edge-coloring of
$G$ such that $def(G,\alpha)=def(G)$.

Define an auxiliary graph $G^{\prime}$ as follows: for each vertex $v\in V(G)$
with $def(v,\alpha)>0$, we attach $def(v,\alpha)$ pendant edges at vertex $v$.
Clearly, $G^{\prime}\in\mathfrak{C}$ and $|V(G^{\prime})|=|V(G)|+def(G)$.
Next, we extend a proper $W_{def}(G)$-edge-coloring $\alpha$ of $G$ to a
proper $W_{def}(G)$-edge-coloring $\beta$ of $G^{\prime}$ as follows: for each
vertex $v\in V(G)$ with $def(v,\alpha)>0$, we color the attached edges
incident to $v$ using distinct colors from
$\left[\underline{S}\left(v,\alpha\right),\overline{S}\left(v,\alpha\right)\right]\setminus
S(v,\alpha)$. By the definition of $\beta$ and the construction of
$G^{\prime}$, we obtain that $G^{\prime}$ has an interval
$W_{def}(G)$-coloring. Since $G^{\prime}\in\mathfrak{C}\cap\mathfrak{N}$, we
have

$W_{def}(G)\leq W(G^{\prime})\leq
f(|V(G^{\prime})|)=f\left(|V(G)|+def(G)\right)$.

∎

Since the class of triangle-free graphs is closed under the operation of
attaching of pendant edges, by Theorems 2.3 and 3.1, we obtain the following
results.

######  Corollary 3.2.

If $G$ is a triangle-free graph, then $W_{def}(G)\leq|V(G)|+def(G)-1$.

######  Corollary 3.3.

If $G$ is a bipartite graph, then $W_{def}(G)\leq|V(G)|+def(G)-1$.

It is known that $W_{def}(K_{m,n})=m+n-1$ ($m,n\in\mathbb{N}$) [18, 19], so
this upper bound is sharp for graphs $G$ with $def(G)=0$. Now let us consider
graphs $G$ with $def(G)=1$. Let $K_{n,n}^{\prime}$ be a complete bipartite
graph with exactly one subdivided edge, i.e.

$V\left(K_{n,n}^{\prime}\right)=\\{u_{1},\ldots,u_{n},v_{1},\ldots,v_{n},w\\}$
and

$E\left(K_{n,n}^{\prime}\right)=\left(\\{u_{i}v_{j}\colon\,1\leq i\leq n,1\leq
j\leq n\\}\setminus\\{u_{n}v_{n}\\}\right)\cup\\{u_{n}w,wv_{n}\\}$.

It is well-known that $\chi^{\prime}\left(K_{n,n}^{\prime}\right)=n+1$ [6,
36], so by Theorem 2.1, $K_{n,n}^{\prime}\notin\mathfrak{N}$. Thus,
$def\left(K_{n,n}^{\prime}\right)\geq 1$. On the other hand, let us define an
edge-coloring $\alpha$ of $K_{n,n}^{\prime}$ as follows: for every $e\in
E\left(K_{n,n}^{\prime}\right)$, let

$\alpha\left(e\right)=\left\\{\begin{tabular}[]{ll}$i+j-1$,&if
$e=u_{i}v_{j}$,\\\ $2n-1$,&if $e=u_{n}w$,\\\ $2n$,&if $e=wv_{n}.$\\\
\end{tabular}\right.$

It is not difficult to see that $\alpha$ is a proper $2n$-edge-coloring of
$K_{n,n}^{\prime}$ with deficiency $def(K_{n,n}^{\prime},\alpha)=1$. Hence,
$def(K_{n,n}^{\prime})=1$ and $2n\leq W_{def}(K_{n,n}^{\prime})\leq 2n+1$.

Since the class of planar graphs is closed under the operation of attaching of
pendant edges, by Theorems 2.4 and 3.1, we obtain the following result.

######  Corollary 3.4.

If $G$ is a planar graph, then
$W_{def}(G)\leq\frac{11}{6}\left(|V(G)|+def(G)\right)$.

Next we give some upper bounds for $W_{def}(G)$ depending on degrees and
diameter of the connected graph $G$.

######  Theorem 3.5.

If $G$ is a connected graph, then

$W_{def}(G)\leq 1+def(G)+{\max\limits_{P\in\mathbf{P}}}{\sum\limits_{v\in
V(P)}}\left(d_{G}(v)-1\right)$,

where $\mathbf{P}$ is the set of all shortest paths in the graph $G$.

###### Proof.

In the proof we follow the idea from [3] (Thm. 2). Let $\alpha$ be a proper
$W_{def}(G)$-edge-coloring of $G$ such that $def(G,\alpha)=def(G)$.

Similarly as in the proof of Theorem 3.1, we define an auxiliary graph $H$ as
follows: for each vertex $v\in V(G)$ with $def(v,\alpha)>0$, we attach
$def(v,\alpha)$ pendant edges at vertex $v$. Clearly, $H$ is a connected
graph. Again, we extend a proper $W_{def}(G)$-edge-coloring $\alpha$ of $G$ to
a proper $W_{def}(G)$-edge-coloring $\beta$ of $H$ as follows: for each vertex
$v\in V(G)$ with $def(v,\alpha)>0$, we color the attached edges incident to
$v$ using colors from
$\left[\underline{S}\left(v,\alpha\right),\overline{S}\left(v,\alpha\right)\right]\setminus
S(v,\alpha)$. By the definition of $\beta$ and the construction of $H$, we
obtain that $H$ has an interval $W_{def}(G)$-coloring. In the coloring $\beta$
of $H$, we consider the edges with colors $1$ and $W_{def}(G)$. Let
$e=u_{1}u_{2},e^{\prime}=w_{1}w_{2}$ and
$\beta(e)=1,\beta(e^{\prime})=W_{def}(G)$. Without loss of generality we may
assume that a shortest path $P$ joining $e$ with $e^{\prime}$ joins $u_{1}$
with $w_{1}$, where $P=v_{0}e_{1}v_{1}\ldots v_{i-1}e_{i}v_{i}\ldots
v_{k-1}e_{k}v_{k}$ and $v_{0}=u_{1}$, $v_{k}=w_{1}$.

Since $\beta$ is an interval $W_{def}(G)$-coloring of $H$, we have

$\beta(e_{1})\leq d_{H}(v_{0})$,

$\beta(e_{2})\leq\beta(e_{1})+d_{H}(v_{1})-1$,

$\cdots\cdots\cdots\cdots\cdots\cdots$

$\beta(e_{i})\leq\beta(e_{i-1})+d_{H}(v_{i-1})-1$,

$\cdots\cdots\cdots\cdots\cdots\cdots$

$\beta(e_{k})\leq\beta(e_{k-1})+d_{H}(v_{k-1})-1$,

$\beta(e^{\prime})\leq\beta(e_{k})+d_{H}(v_{k})-1$.

Summing up these inequalities, we obtain

$\beta(e^{\prime})\leq 1+{\sum\limits_{j=0}^{k}\left(d_{H}(v_{j})-1\right)}$.

From here, we obtain

$\displaystyle W_{def}(G)=\beta(e^{\prime})$ $\displaystyle\leq$
$\displaystyle 1+{\sum\limits_{j=0}^{k}\left(d_{H}(v_{j})-1\right)}\leq
1+def(G)+{\sum\limits_{j=0}^{k}\left(d_{G}(v_{j})-1\right)}$
$\displaystyle\leq$ $\displaystyle
1+def(G)+{\max\limits_{P\in\mathbf{P}}}{\sum\limits_{v\in
V(P)}}\left(d_{G}(v)-1\right).$

∎

######  Corollary 3.6.

If $G$ is a connected graph, then

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

It is known that the upper bound in Theorem 3.5 is sharp for trees [18, 19].
The upper bound in Corollary 3.6 cannot be significantly improved, since
$def\left(C_{2n+1}\right)=1$, $\mathrm{diam}\left(C_{2n+1}\right)=n$ and
$W_{def}\left(C_{2n+1}\right)=n+2$ ($n\in\mathbb{N}$).

Here we prove a lower bound on $w_{def}(G)$ for graphs without perfect
matching.

######  Theorem 3.7.

If $G$ has no perfect matching, then $w_{def}(G)\geq 2\delta(G)-def(G)$.

###### Proof.

In the proof of this theorem we follow the idea from [9] (Prop. 2).

Let $\alpha$ be a proper $w_{def}(G)$-edge-coloring of $G$ such that
$def(G,\alpha)=def(G)$.

It is easy to see that for every $v\in V(G)$, we have

$1\leq\underline{S}\left(v,\alpha\right)\leq w_{def}(G)-\delta(G)+1$.

Assume that $w_{def}(G)-\delta(G)+1\leq\delta(G)$ (otherwise, $w_{def}(G)\geq
2\delta(G)\geq 2\delta(G)-def(G)$).

Since $G$ has no perfect matching, for each color
$c\in\left[w_{def}(G)-\delta(G)+1,\delta(G)\right]$, there is at least one
vertex $v_{c}$ such that $c\notin S\left(v_{c},\alpha\right)$ and
$\underline{S}\left(v_{c},\alpha\right)<c<\overline{S}\left(v_{c},\alpha\right)$.
This implies that there are at least $2\delta(G)-w_{def}(G)$ missing colors at
vertices of $G$. Hence, $def(G)\geq 2\delta(G)-w_{def}(G)$. ∎

######  Corollary 3.8.

[9] If $G$ is a graph with an odd number of vertices, then $w_{def}(G)\geq
2\delta(G)-def(G)$.

######  Corollary 3.9.

[9] If $G$ is an $r$-regular graph with an odd number of vertices and
$def(G)=\frac{r}{2}$, then $w_{def}(G)\geq\frac{3r}{2}$.

######  Corollary 3.10.

If $G$ has no perfect matching and $G\in\mathfrak{N}$, then
$w(G)\geq\max\\{\Delta(G),2\delta(G)\\}$.

In [14], Giaro, Kubale and Małafiejski determined the deficiency of
$K_{2n+1}$, and they proved that $def(K_{2n+1})=n$ ($n\in\mathbb{N}$). The
lower bound in Theorem 3.7 is sharp for $K_{2n+1}$, since
$\delta(K_{2n+1})=2n$ and it was proved in [9] that
$w_{def}\left(K_{2n+1}\right)=3n$ ($n\in\mathbb{N}$). In the next section we
will prove that this lower bound is also sharp for near-complete graphs, but
first we consider the difference $W_{def}(G)-w_{def}(G)$. In [19], Kamalian
proved that for any $l\in\mathbb{N}$, there exists a graph $G$ such that
$G\in\mathfrak{N}$ and $W(G)-w(G)\geq l$. Here we extend this result to graphs
with a positive deficiency.

######  Theorem 3.11.

For any $l\in\mathbb{N}$, there exists a graph $G$ such that $def(G)>0$ and
$W_{def}(G)-w_{def}(G)\geq l$.

###### Proof.

Let $p=2l+1$ and $G=K_{2p+1}$. Since $def(G)=p>0$ and $w_{def}(G)=3p$, so to
complete the proof it is sufficient to show that $W_{def}(G)\geq
3p+\frac{p-1}{2}=3p+l$. We will prove a more general statement for all
complete graphs with odd number of vertices. We will show that if $n=p2^{q}$,
where $p$ is odd and $q\in\mathbb{Z}_{+}$, then

$W_{def}(K_{2n+1})\geq 3n+\frac{p-1}{2}$.

Figure 1: We divide the vertices of $K_{p2^{q+1}+1}$ into $2^{q+1}$ groups,
such that the intersection of each pair of groups is the vertex $v_{0}$.

We construct an edge-coloring $\phi$ of $K_{p2^{q+1}+1}$ by composing three
colorings of different graphs.

  1. 1.

We need interval $\left(\frac{3}{2}(p+1)-2\right)$-coloring $\alpha$ of
$K_{p+1}$ as described in the proof of Theorem 4 from [25]. We denote the
vertices of $K_{p+1}$ in the following way:
$V(K_{p+1})=\\{u_{i}:i=0,\ldots,p\\}$. The coloring $\alpha$ has an important
property that $\underline{S}(u_{i},\alpha)=\lfloor\frac{i}{2}\rfloor+1$ for
every $i=0,\ldots,p$.

  2. 2.

Next, we need the interval coloring $\beta$ of $K_{p,p}$ described in Lemma
2.6. We denote the vertices of $K_{p,p}$ in the following way:
$V(K_{p,p})=\\{x_{i},y_{i}:i=1,\ldots,p\\}$. Lemma 2.6 guarantees that for
every $i=1,\ldots,p$,
$\underline{S}(x_{i},\beta)=\underline{S}(y_{i},\beta)=\left\lfloor\frac{i}{2}\right\rfloor+1$.

  3. 3.

Finally, we need a proper edge-coloring $\gamma$ of $K_{2^{q+1}+1}$ with
$3\cdot 2^{q}$ colors. We denote its vertices by
$V(K_{2^{q+1}+1})=\left\\{w^{j}:j=0,\ldots,2^{q+1}\right\\}$. The coloring
$\gamma$ must satisfy the following condition:
$def(K_{2^{q+1}+1},\gamma)=def(w^{0},\gamma)=2^{q}$. Colorings with these
properties are described in the proof of Theorem 4.2 in [14] and in the proof
of Theorem 29 in [31].

We denote the vertices of $K_{p2^{q+1}+1}$ in the following way (Fig. 1):

$\displaystyle
V\left(K_{p2^{q+1}+1}\right)=\\{v_{0}\\}\cup\left\\{v_{i}^{j}:i=1,\ldots,p,\
j=1,\ldots,2^{q+1}\right\\}.$

We construct its edge-coloring $\phi$ in the following way:

$\displaystyle\phi\left(v_{i_{1}}^{j}v_{i_{2}}^{j}\right)$
$\displaystyle=\alpha(u_{i_{1}}u_{i_{2}})+p\left(\gamma(w^{0}w^{j})-1\right),$
$\displaystyle 0\leq i_{1}<i_{2}\leq p,$ $\displaystyle 1\leq j\leq 2^{q+1};$
$\displaystyle\phi\left(v_{i_{1}}^{j_{1}}v_{i_{2}}^{j_{2}}\right)$
$\displaystyle=\beta(x_{i_{1}}y_{i_{2}})+p\left(\gamma(w^{j_{1}}w^{j_{2}})-1\right),$
$\displaystyle 1\leq i_{1},i_{2}\leq p,$ $\displaystyle 1\leq j_{1}<j_{2}\leq
2^{q+1}.$

The symbols $v_{0}^{j}$ in the above formulas refer to the same vertex
$v_{0}$, for all $j=1,\ldots,2^{q+1}$. The first formula colors the edges that
have both ends in the same group in Fig. 1, while the second formula colors
the edges that join vertices from different groups. We show that the spectrums
of the vertices $v_{i}^{j}$, $i=1,\ldots,p$, $j=1,\ldots,2^{q+1}$ are
intervals.

$\displaystyle S\left(v^{j}_{i},\phi\right)$
$\displaystyle=\left[\underline{S}(u_{i},\alpha)+p\left(\gamma(w^{0}w^{j})-1\right),\overline{S}(u_{i},\alpha)+p\left(\gamma(w^{0}w^{j})-1\right)\right]$
$\displaystyle\cup\bigcup\limits_{j^{\prime}\in[1,2^{q+1}]\setminus\\{j\\}}{\left[\underline{S}(x_{i},\beta)+p\left(\gamma(w^{j}w^{j^{\prime}})-1\right),\overline{S}(x_{i},\beta)+p\left(\gamma(w^{j}w^{j^{\prime}})-1\right)\right]}.$

We have that
$\underline{S}(u_{i},\alpha)=\underline{S}(x_{i},\beta)=\lfloor\frac{i}{2}\rfloor+1$
for every $i=1,\ldots,p$. So the above expression becomes:

$\displaystyle S\left(v^{j}_{i},\phi\right)$
$\displaystyle=\left[\left\lfloor\frac{i}{2}\right\rfloor+1+p\left(\gamma(w^{0}w^{j})-1\right),\left\lfloor\frac{i}{2}\right\rfloor+p+p\left(\gamma(w^{0}w^{j})-1\right)\right]$
$\displaystyle\cup\bigcup\limits_{j^{\prime}\in[1,2^{q+1}]\setminus\\{j\\}}{\left[\left\lfloor\frac{i}{2}\right\rfloor+1+p\left(\gamma(w^{j}w^{j^{\prime}})-1\right),\left\lfloor\frac{i}{2}\right\rfloor+p+p\left(\gamma(w^{j}w^{j^{\prime}})-1\right)\right]}$
$\displaystyle=\bigcup\limits_{j^{\prime}\in[0,2^{q+1}]\setminus\\{j\\}}{\left[\left\lfloor\frac{i}{2}\right\rfloor+1+p\left(\gamma(w^{j}w^{j^{\prime}})-1\right),\left\lfloor\frac{i}{2}\right\rfloor+p+p\left(\gamma(w^{j}w^{j^{\prime}})-1\right)\right]}$
$\displaystyle=\left[\left\lfloor\frac{i}{2}\right\rfloor+1+p\left(\underline{S}(w^{j},\gamma)-1\right),\left\lfloor\frac{i}{2}\right\rfloor+p+p\left(\overline{S}(w^{j},\gamma)-1\right)\right].$

The last equation holds because the spectrum $S\left(w^{j},\gamma\right)$ is
an interval for $j=1,\ldots,2^{q+1}$. Finally, the spectrum of $v_{0}$ and the
deficiency of $\phi$ at $v_{0}$ will be:

$\displaystyle S\left(v_{0},\phi\right)$
$\displaystyle=\bigcup\limits_{j^{\prime}\in[1,2^{q+1}]}{\left[\underline{S}(u_{0},\alpha)+p\left(\gamma(w^{0}w^{j^{\prime}})-1\right),\overline{S}(u_{0},\alpha)+p\left(\gamma(w^{0}w^{j^{\prime}})-1\right)\right]}$
$\displaystyle=\bigcup\limits_{j^{\prime}\in[1,2^{q+1}]}{\left[1+p\cdot\gamma(w^{0}w^{j^{\prime}})-p,p\cdot\gamma(w^{0}w^{j^{\prime}})\right]},$
$\displaystyle def(v_{0},\phi)$
$\displaystyle=\overline{S}(v_{0},\phi)-\underline{S}(v_{0},\phi)-d_{K_{2n+1}}(v_{0})+1$
$\displaystyle=p\cdot\overline{S}(w^{0},\gamma)-(1+p\cdot\underline{S}(w^{0},\gamma)-p)-p\cdot
2^{q+1}+1$
$\displaystyle=p\left(\overline{S}(w^{0},\gamma)-\underline{S}(w^{0},\gamma)-d_{K_{2^{q+1}+1}}(w^{0})+1\right)=p\cdot
def(w^{0},\gamma)=p2^{q}=n.$

Let $w^{\underline{j}}$ and $w^{\overline{j}}$ be the vertices of
$K_{2^{q+1}+1}$ such that
$\underline{S}\left(w^{\underline{j}},\gamma\right)=1$ and
$\overline{S}\left(w^{\overline{j}},\gamma\right)=3\cdot 2^{q}$. It is easy to
see that $\underline{S}\left(v^{\underline{j}}_{1},\phi\right)=1$ and
$\overline{S}\left(v^{\overline{j}}_{p},\phi\right)=\left\lfloor\frac{p}{2}\right\rfloor+p+p\left(3\cdot
2^{q}-1\right)=3n+\frac{p-1}{2}$. So, $\phi$ is a proper edge-coloring of
$K_{2n+1}$ with $3n+\frac{p-1}{2}$ colors having
$def(K_{2n+1},\phi)=def\left(v_{0},\phi\right)=n$. ∎

The last theorem of this section generalizes Theorem 2.2.

######  Theorem 3.12.

Let $\alpha_{0}$ be a proper $t_{0}$-edge-coloring of a regular graph $G$ and
$D\subseteq V(G)$ be a subset of its vertices. If for every $v\in
V(G)\setminus D$, $def(v,\alpha_{0})=0$, then for every $t$,
$\overline{S}(D,\alpha_{0})-\underline{S}(D,\alpha_{0})+1\leq t\leq t_{0}$,
$G$ has a proper $t$-edge-coloring $\alpha$ such that
$def(v,\alpha)=def(v,\alpha_{0})$ for every vertex $v\in V(G)$.

###### Proof.

Let $a=\underline{S}(D,\alpha_{0})-1$ and
$b=t_{0}-\overline{S}(D,\alpha_{0})$. Basically we have $a+b$ colors outside
the range $[\underline{S}(D,\alpha_{0}),\overline{S}(D,\alpha_{0})]$ and we
need to get rid of $t_{0}-t$ of them. We construct the edge-coloring $\alpha$
of $G$ by copying colors of all the edges from $\alpha_{0}$ and then modifying
some of them. First we try to remove the colors larger than
$\overline{S}(D,\alpha_{0})$, and if these are not enough, we remove the
colors smaller than $\underline{S}(D,\alpha_{0})$.

If $t_{0}-t\leq b$, then for every $e\in E(G)$ with
$\alpha_{0}(e)\in\left[t+1,t_{0}\right]$, we set
$\alpha(e)=\alpha_{0}(e)-\Delta(G)$.

If $t_{0}-t>b$, then for every $e\in E(G)$ with
$\alpha_{0}(e)\in\left[\overline{S}(D,\alpha_{0})+1,t_{0}\right]$, we set
$\alpha(e)=\alpha_{0}(e)-\Delta(G)$. Next, for every $e\in E(G)$ with
$\alpha_{0}(e)\in\left[1,t_{0}-t-b\right]$, we set
$\alpha(e)=\alpha_{0}(e)+\Delta(G)$. In both cases, the spectrums of the
vertices from $D$ are not modified and the spectrums of the other vertices
remain intervals. If $\underline{S}(V(G),\alpha)>1$, then we subtract
$\underline{S}(V(G),\alpha)-1$ from colors of all the edges to obtain the
final coloring. ∎

Note that if we apply the above theorem on an interval colorable regular graph
$G$ by taking its interval $W(G)$-coloring as $\alpha_{0}$ and any set
containing a single vertex as $D$, we obtain Theorem 2.2.

Theorems 3.11 and 3.12 imply the following result.

######  Corollary 3.13.

Let $n=p2^{q}$, where $p$ is odd and $q\in\mathbb{Z}_{+}$. For every $t$,
$3n\leq t\leq 3n+\frac{p-1}{2}$, $K_{2n+1}$ has a proper $t$-edge-coloring
$\alpha$ such that $def(K_{2n+1},\alpha)=n$.

###### Proof.

It is enough to take a proper $\left(3n+\frac{p-1}{2}\right)$-edge-coloring
$\alpha_{0}$ of the graph $K_{2n+1}$ from the proof of Theorem 3.11 and a set
$D=\\{v_{0}\\}$, where $v_{0}\in V(K_{2n+1})$ and
$def(v_{0},\alpha_{0})=def(K_{2n+1},\alpha_{0})=n$, and notice that
$\overline{S}(D,\alpha_{0})-\underline{S}(D,\alpha_{0})+1=\overline{S}(v_{0},\alpha_{0})-\underline{S}(v_{0},\alpha_{0})+1=def(v_{0},\alpha_{0})+d_{K_{2n+1}}(v_{0})=n+2n=3n$.
∎

##  4 The deficiency of certain graphs

This section is devoted to the deficiency of near-complete graphs and some
complete tripartite graphs. We begin our consideration with near-complete
graphs. Recently, it was shown that the following result holds.

######  Theorem 4.1.

[7] If $G$ is a graph with an odd number of vertices, then

$def(G)\geq\frac{2|E(G)|-(|V(G)|-1)\Delta(G)}{2}$.

######  Corollary 4.2.

[7] For any $n,m\in\mathbb{N}$, we have

$def(K_{2n+1}-mK_{2})\geq n-m$, where $1\leq m\leq n$.

In general, the lower bound on $def(K_{2n+1}-mK_{2})$ ($1\leq m\leq n$) is not
sharp, since for any maximum matching $M$ of $K_{2n+1}$ ($n\geq 2$),
$K_{2n+1}-M\notin\mathfrak{N}$ [25], hence $def(K_{2n+1}-nK_{2})>0$. However,
the lower bound is sharp for $K_{2n+1}-e$ as it was conjectured in [7].

######  Theorem 4.3.

If $n\in\mathbb{N}$, then $def(K_{2n+1}-e)=n-1$.

###### Proof.

By Corollary 4.2, we have $def(K_{2n+1}-e)\geq n-1$ for any $n\in\mathbb{N}$.
For the proof, it suffices to construct a proper edge-coloring $\beta$ of
$K_{2n+1}-e$ with deficiency $def(K_{2n+1}-e,\beta)=n-1$. Let
$V(K_{2n+1}-e)=\left\\{v_{0},v_{1},\ldots,v_{2n}\right\\}$. Without loss of
generality we may assume that $e=v_{1}v_{2n}$.

Define an edge-coloring $\beta$ of $K_{2n+1}-e$. For each edge $v_{i}v_{j}\in
E(K_{2n+1})$ with $i<j$ and $(i,j)\neq(1,2n)$, define a color
$\beta\left(v_{i}v_{j}\right)$ as follows:

$\beta\left(v_{i}v_{j}\right)=\left\\{\begin{tabular}[]{ll}$1$,&if $i=0$,
$j=1$;\\\ $2n+1$,&if $i=0$, $j=2$;\\\ $j-1$,&if $i=0$, $3\leq j\leq n$;\\\
$n+1+j$,&if $i=0$, $n+1\leq j\leq 2n-2$;\\\ $n$,&if $i=0$, $j=2n-1$;\\\
$2n$,&if $i=0$, $j=2n$;\\\ $i+j-1$,&if $1\leq
i\leq\left\lfloor\frac{n}{2}\right\rfloor$, $2\leq j\leq n$, $i+j\leq n+1$;\\\
$i+j+n-2$,&if $2\leq i\leq n-1$, $\left\lfloor\frac{n}{2}\right\rfloor+2\leq
j\leq n$, $i+j\geq n+2$;\\\ $n+1+j-i$,&if $3\leq i\leq n$, $n+1\leq j\leq
2n-2$, $j-i\leq n-2$;\\\ $j-i+1$,&if $1\leq i\leq n$, $n+1\leq j\leq 2n$,
$j-i\geq n$;\\\ $2i-1$,&if $2\leq i\leq
1+\left\lfloor\frac{n-1}{2}\right\rfloor$, $n+1\leq j\leq
n+\left\lfloor\frac{n-1}{2}\right\rfloor$, $j-i=n-1$;\\\ $i+j-1$,&if
$\left\lfloor\frac{n-1}{2}\right\rfloor+2\leq i\leq n$,
$n+1+\left\lfloor\frac{n-1}{2}\right\rfloor\leq j\leq 2n-1$, $j-i=n-1$;\\\
$i+j-2n+1$,&if $n+1\leq i\leq n+\left\lfloor\frac{n}{2}\right\rfloor-1$,
$n+2\leq j\leq 2n-2$, $i+j\leq 3n-1$;\\\ $i+j-n$,&if $n+1\leq i\leq 2n-1$,
$n+\left\lfloor\frac{n}{2}\right\rfloor+1\leq j\leq 2n$, $i+j\geq
3n$.\end{tabular}\right.$

Let us prove that $\beta$ is a proper $(3n-1)$-edge-coloring of $K_{2n+1}-e$
with deficiency $def(K_{2n+1}-e,\beta)=n-1$.

Let $G$ be the subgraph of $K_{2n+1}-e$ induced by
$\\{v_{1},\ldots,v_{2n}\\}$. Clearly, $G$ is isomorphic to $K_{2n}-e$. This
edge-coloring $\beta$ of $K_{2n+1}-e$ is constructed on the interval
$(3n-2)$-coloring of $K_{2n}$ which is described in the proof of Theorem 4
from [25]. We use this interval $(3n-2)$-coloring of $K_{2n}$ and then we
shift all colors of the edges of $G$ by one. Let $\alpha$ be this edge-
coloring of $G$. Using the property of this edge-coloring which is described
in the proof of Corollary 6 from [25], we get

1)

$S\left(v_{1},\alpha\right)=[2,2n-1]$ and $S\left(v_{2},\alpha\right)=[2,2n]$,

2)

$S\left(v_{i},\alpha\right)=S\left(v_{n+i-2},\alpha\right)=[i,2n-2+i]$ for
$3\leq i\leq n$,

3)

$S\left(v_{2n-1},\alpha\right)=[n+1,3n-1]$ and
$S\left(v_{2n},\alpha\right)=[n+1,3n-1]\setminus\\{2n\\}$.

Now, by the definition of $\beta$, we have

1)

$S\left(v_{0},\beta\right)=[1,n]\cup[2n,3n-1]$,

2)

$S\left(v_{1},\beta\right)=[1,2n-1]$ and $S\left(v_{2},\beta\right)=[2,2n+1]$,

3)

$S\left(v_{i},\beta\right)=[i-1,2n-2+i]$ and
$S\left(v_{n+i-2},\beta\right)=[i,2n-1+i]$ for $3\leq i\leq n$,

4)

$S\left(v_{2n-1},\beta\right)=[n,3n-1]$ and
$S\left(v_{2n},\beta\right)=[n+1,3n-1]$.

This shows that $\beta$ is a proper $(3n-1)$-edge-coloring of $K_{2n+1}-e$
with deficiency $def(K_{2n+1}-e,\beta)=n-1$. Hence, $def(K_{2n+1}-e)=n-1$.
(see Fig. 2). ∎

$1$$1$$7$$7$$2$$2$$8$$8$$3$$3$$6$$6$$2$$2$$3$$3$$4$$4$$5$$5$$6$$6$$3$$3$$4$$4$$5$$5$$5$$5$$7$$7$$4$$4$$6$$6$$7$$7$$8$$8$$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$
Figure 2: Proper $8$-edge-coloring $\beta$ of $K_{7}-e$ with
$def(v_{0},\beta)=def(K_{7}-e)=2$.

######  Theorem 4.4.

If $n\in\mathbb{N}$, then $w_{def}(K_{2n+1}-e)=3n-1$.

###### Proof.

From the proof of Theorem 4.3, we have that $K_{2n+1}-e$ has a proper
$(3n-1)$-edge-coloring $\alpha$ with deficiency
$def(K_{2n+1}-e,\alpha)=def(K_{2n+1}-e)=n-1$. This implies that
$w_{def}(K_{2n+1}-e)\leq 3n-1$. On the other hand, since $K_{2n+1}-e$ has no
perfect matching, $\delta(K_{2n+1}-e)=2n-1$ and $def(K_{2n+1}-e)=n-1$, by
Theorem 3.7, we obtain $w_{def}(K_{2n+1}-e)\geq 2(2n-1)-n+1=3n-1$. ∎

In [10], it was shown that $def\left(K_{1,1,n}\right)=0$ if $n$ is even, and
$def\left(K_{1,1,n}\right)=1$ if $n$ is odd. Here we generalize this result
and determine the deficiency of $K_{1,m,n}$ for any $m,n\in\mathbb{N}$.

######  Theorem 4.5.

For any $m,n\in\mathbb{N}$, we have

$def\left(K_{1,m,n}\right)=\left\\{\begin{tabular}[]{ll}$0$,&if
$\gcd(m+1,n+1)=1$,\\\ $1$,&otherwise.\\\ \end{tabular}\right.$

###### Proof.

By Theorem 2.5, we have $K_{1,m,n}\in\mathfrak{N}$ if and only if
$\gcd(m+1,n+1)=1$ for any $m,n\in\mathbb{N}$. This implies that
$def\left(K_{1,m,n}\right)=0$ if $\gcd(m+1,n+1)=1$, and
$def\left(K_{1,m,n}\right)\geq 1$ if $\gcd(m+1,n+1)>1$. We now show that
$def\left(K_{1,m,n}\right)\leq 1$.

Let $V\left(K_{1,m,n}\right)=\\{u_{1},\ldots,u_{m},v_{1},\ldots,v_{n},w\\}$
and $E\left(K_{1,m,n}\right)=\left\\{u_{i}v_{j}\colon\,1\leq i\leq m,1\leq
j\leq n\right\\}\cup\\{wu_{i}\colon\,1\leq i\leq
m\\}\cup\\{wv_{j}\colon\,1\leq j\leq n\\}$.

Define an edge-coloring $\alpha$ of $K_{1,m,n}$ as follows:

(1)

for $1\leq i\leq m$ and $1\leq j\leq n$, let
$\alpha\left(u_{i}v_{j}\right)=i+j$,

(2)

for $1\leq i\leq m$, let $\alpha\left(wu_{i}\right)=i$,

(3)

for $1\leq j\leq n$, let $\alpha\left(wv_{j}\right)=m+1+j$.

Let us prove that $\alpha$ is a proper $(m+n+1)$-edge-coloring of $K_{1,m,n}$
with deficiency $def\left(K_{1,m,n},\alpha\right)=1$.

By the definition of $\alpha$, we have

1)

for $1\leq i\leq m$,

$S\left(u_{i},\alpha\right)=[i+1,n+i]\cup\\{i\\}=[i,n+i]$ due to (1) and (2),

2)

for $1\leq j\leq n$,

$S\left(v_{j},\alpha\right)=[j+1,m+j]\cup\\{m+1+j\\}=[j+1,m+1+j]$ due to (1)
and (3),

3)

$S\left(w,\alpha\right)=[1,m]\cup[m+2,m+n+1]$ due to (2) and (3).

This implies that $\alpha$ is a proper $(m+n+1)$-edge-coloring of $K_{1,m,n}$
with deficiency $def\left(K_{1,m,n},\alpha\right)=1$ ($m,n\in\mathbb{N}$);
thus $def\left(K_{1,m,n}\right)\leq 1$ if $\gcd(m+1,n+1)>1$. ∎

##  5 Concluding Remarks

In 1999, Giaro, Kubale and Małafiejski [13] showed that there are bipartite
graphs whose deficiency approaches the number of vertices. On the other hand,
in [9] Bouchard, Hertz, Desaulniers suggested the following conjecture.

######  Conjecture 5.1.

For every graph $G$,

$def(G)\leq|V(G)|$.

The conjecture is still open, but it holds for regular graphs, some bipartite
graphs and outerplanar graphs [34, 13, 8, 23]. If the conjecture is true,
then, by Corollary 3.2, we obtain that the upper bound $W_{def}(G)\leq
2|V(G)|-1$ holds for every triangle-free graph $G$. Moreover, if the
conjecture is true, then, by the result of Altinakar, Caporossi and Hertz [1],
we derive that the bound $W_{def}(G)\leq 3|V(G)|-4$ holds for every graph $G$
with at least three vertices.

In Section 3, we obtained some results on the parameters $w_{def}(K_{2n+1})$
and $W_{def}(K_{2n+1})$. In particular, we proved that the difference
$W_{def}(K_{2n+1})-w_{def}(K_{2n+1})$ can be arbitrarily large. On the other
hand, we cannot find a proper edge-coloring of $K_{2n+1}$ with more than $3n$
colors having minimum deficiency when $n$ is a power of two. So we would like
to suggest the following conjecture.

######  Conjecture 5.2.

For any $q\in\mathbb{Z}_{+}$,

$w_{def}\left(K_{2^{q+1}+1}\right)=W_{def}\left(K_{2^{q+1}+1}\right)=3\cdot
2^{q}$.

Finally, we would like to introduce the concept of deficiency-critical graphs,
since it will be very useful for investigating deficiency of graphs. A graph
$G$ with $def(G)=k>0$ is _$k$ -deficiency-critical_ if $def(G-e)<def(G)$ for
every edge $e$ in $G$. Clearly, odd cycles $C_{2n+1}$ ($n\in\mathbb{N}$) are
$1$-deficiency-critical graphs. In fact, the conjecture of Borowiecka-
Olszewska, Drgas-Burchardt and Hałuszczak can be reformulated as follows: all
complete graphs $K_{2n+1}$ ($n\in\mathbb{N}$) are $n$-deficiency-critical.
Here we would like to suggest the following problem.

######  Problem 1.

Characterize all $k$-deficiency-critical graphs.

  * Acknowledgement

We would like to thank both referees for many useful comments and suggestions.
The work was made possible by a research grant from the Armenian National
Science and Education Fund (ANSEF) based in New York, USA.

## References

  * [1] S. Altinakar, G. Caporossi, A. Hertz, A comparison of integer and constraint programming models for the deficiency problem, Computers and Oper. Res. 68 (2016) 89-96.
  * [2] A.S. Asratian, R.R. Kamalian, Interval colorings of edges of a multigraph, Appl. Math. 5 (1987) 25-34 (in Russian).
  * [3] A.S. Asratian, R.R. Kamalian, Investigation on interval edge-colorings of graphs, J. Combin. Theory Ser. B 62 (1994) 34-43.
  * [4] A.S. Asratian, T.M.J. Denley, R. Haggkvist, Bipartite Graphs and their Applications, Cambridge University Press, Cambridge, 1998.
  * [5] M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002) 77-94.
  * [6] L.W. Beineke, R.J. Wilson, On the edge-chromatic number of a graph, Discrete Math. 5 (1973) 15-20.
  * [7] M. Borowiecka-Olszewska, E. Drgas-Burchardt, M. Hałuszczak, On the structure and deficiency of $k$-trees with bounded degree, Discrete Appl. Math. 201 (2016) 24-37.
  * [8] M. Borowiecka-Olszewska, E. Drgas-Burchardt, The deficiency of all generalized Hertz graphs and minimal consecutively non-colourable graphs in this class, Discrete Math. 339 (2016) 1892-1908.
  * [9] M. Bouchard, A. Hertz, G. Desaulniers, Lower bounds and a tabu search algorithm for the minimum deficiency problem, J. Comb. Optim. 17 (2009) 168-191.
  * [10] Y. Feng, Q. Huang, Consecutive edge-coloring of the generalized $\theta$-graph, Discrete Appl. Math. 155 (2007) 2321-2327.
  * [11] K. Giaro, M. Kubale, Consecutive edge-colorings of complete and incomplete Cartesian products of graphs, Cong. Num. 128 (1997) 143-149.
  * [12] K. Giaro, M. Kubale, Compact scheduling of zero-one time operations in multi-stage systems, Discrete Appl. Math. 145 (2004) 95-103.
  * [13] K. Giaro, M. Kubale, M. Małafiejski, On the deficiency of bipartite graphs, Discrete Appl. Math. 94 (1999) 193-203.
  * [14] K. Giaro, M. Kubale, M. Małafiejski, Consecutive colorings of the edges of general graphs, Discrete Math. 236 (2001) 131-143.
  * [15] A. Grzesik, H. Khachatrian, Interval edge-colorings of $K_{1,m,n}$, Discrete Appl. Math. 174 (2014) 140-145.
  * [16] H.M. Hansen, Scheduling with minimum waiting periods, MSc Thesis, Odense University, Odense, Denmark, 1992 (in Danish).
  * [17] D. Hanson, C.O.M. Loten, B. Toft, On interval colorings of bi-regular bipartite graphs, Ars Combin. 50 (1998) 23-32.
  * [18] R.R. Kamalian, Interval colorings of complete bipartite graphsand trees, preprint, Comp. Cen. of Acad. Sci. of Armenian SSR, Yerevan, 1989 (in Russian).
  * [19] R.R. Kamalian, Interval edge colorings of graphs, Doctoral Thesis, Novosibirsk, 1990.
  * [20] R.R. Kamalian, A.N. Mirumian, Interval edge colorings of bipartite graphs of some class, Dokl. NAN RA 97 (1997) 3-5 (in Russian).
  * [21] R.R. Kamalian, P.A. Petrosyan, A note on interval edge-colorings of graphs, Math. Probl. Comput. Sci. 36 (2012) 13-16.
  * [22] 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.
  * [23] H.H. Khachatrian, Deficiency of outerplanar graphs, Proceedings of the Yerevan State University (2017), in press.
  * [24] M. Kubale, Graph Colorings, American Mathematical Society, 2004.
  * [25] P.A. Petrosyan, Interval edge-colorings of complete graphs and $n$-dimensional cubes, Discrete Math. 310 (2010) 1580-1587.
  * [26] P.A. Petrosyan, Interval edge colorings of some products of graphs, Discuss. Math. Graph Theory 31(2) (2011) 357-373.
  * [27] 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, in: Proceedings of the CSIT Conference (2007) 86-88.
  * [28] P.A. Petrosyan, H.H. Khachatrian, H.G. Tananyan, Interval edge-colorings of Cartesian products of graphs I, Discuss. Math. Graph Theory 33(3) (2013) 613-632.
  * [29] P.A. Petrosyan, H.H. Khachatrian, L.E. Yepremyan, H.G. Tananyan, Interval edge-colorings of graph products, in: Proceedings of the CSIT Conference (2011) 89-92.
  * [30] P.A. Petrosyan, H.H. Khachatrian, T.K. Mamikonyan, On interval edge-colorings of bipartite graphs, IEEE Computer Science and Information Technologies (CSIT) 2015, 71-76.
  * [31] P.A. Petrosyan, S.T. Mkhitaryan, Interval cyclic edge-colorings of graphs, Discrete Math. 339 (2016) 1848-1860.
  * [32] P.A. Petrosyan, H.E. Sargsyan, On resistance of graphs, Discrete Appl. Math. 159 (2011) 1889-1900.
  * [33] S.V. Sevast’janov, Interval colorability of the edges of a bipartite graph, Metody Diskret. Analiza 50 (1990) 61-72 (in Russian).
  * [34] A. Schwartz, The deficiency of a regular graph, Discrete Math. 306 (2006) 1947-1954.
  * [35] H.H. Tepanyan, P.A. Petrosyan, Interval edge-colorings of composition of graphs, Discrete Appl. Math. 217 (2017) 368-374.
  * [36] V.G. Vizing, The chromatic class of a multigraph, Kibernetika 3 (1965) 29-39 (in Russian).
  * [37] D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 2001.