# Generalization of the Maier-Leibniz Doppler-Shift Method for Gamma-Ray
Correlations in Fission

Stefano Marin<EMAIL_ADDRESS>Department of Nuclear Engineering and
Radiological Sciences, University of Michigan, Ann Arbor, MI 48109, USA  M.
Stephan Okar  Department of Nuclear Engineering and Radiological Sciences,
University of Michigan, Ann Arbor, MI 48109, USA  Shaun D. Clarke  Department
of Nuclear Engineering and Radiological Sciences, University of Michigan, Ann
Arbor, MI 48109, USA  Sara A. Pozzi  Department of Nuclear Engineering and
Radiological Sciences, University of Michigan, Ann Arbor, MI 48109, USA
Department of Physics, University of Michigan, Ann Arbor, MI 48109, USA

###### Abstract

The Maier-Leibniz Doppler-Shift technique is the most popular and accurate
technique used in fission experiments to separate the yield of gamma rays from
each of the two fission fragments. The technique exploits the aberration,
i.e., the change in the angular distribution, of gamma rays emitted by a
moving source. By measuring the speed and direction of the source with a
conventional detector, as well as the yield of gamma rays at several angles
from the direction of motion, the technique can be used to determine the mean
multiplicities of gamma rays from each fragment. We show in this work that it
is possible to extend the technique to also measure second moments of the
gamma ray radiation from each fragment. In particular, given the current
interest in fragment correlations in fission, we show that the covariance of
the emission between the two fragments can be inferred. Experimental
limitations and convergence of the new technique are discussed.

neutron-photon multiplicity competition; fission fragment de-excitation

##  I Introduction

A characteristic feature of the binary fission process is the presence of two
excited nuclear fragments moving antiparallel to one another at moderate
velocities, $\approx 0.05\ c$. The two fragments quickly de-excite by emission
of neutrons, followed by gamma rays in the continuum, and finally gamma rays
in the discrete-level region until the ground state, or a long lived isomeric
state, is reached. Over the past few years, a renewed interest in the fission
reaction was sparked by new measurements and refined theoretical models [1, 2,
3, 4]. Of particular interest are the event-by-event correlations between the
fission fragment properties.

Neutron emission is relatively easy to separate between the two fragments. The
evaporated neutrons have velocities comparable in magnitude to the speed of
the fragments, resulting in strong kinematic focusing of the emission along
the fission axis. By analysing both energy and direction of the neutrons and
the fragments, it is possible to determine with decent accuracy which fragment
emitted each neutron on an event-by-event case [5, 6, 7]. Similarly, the
discrimination of discrete gamma rays can be performed by gating on specific
known transitions of nuclei [2]. The same is not possible in general for
statisical gamma-rays in the continuum. However, as shown by Maier-Leibniz [8]
and Pleasonton et al. [9], the gamma-ray emission can be analysed using
statistical methods such as Maier-Leibniz Doppler-Shift (ML-DS) technique.

The (ML-DS) technique has been successfully applied successfully in several
experimental investigations of fission, including Refs. [9, 10, 11, 1].
However, given the recent interest in fragment correlations (see Refs [2, 12,
13, 3]) we think it is important to present techniques capable of determining
correlations between gamma-ray emission from the two fragments. In this paper,
we will show that a simple generalization to the ML-DS technique allows the
experimenter to separate the second order moments of the gamma-ray
distribution without the need of changing the experimental apparatus.

##  II Overview of Technique

The ML-DS technique has been applied in several experiments and several
variants of the techniques exist. In its original formulation [8, 9], the
method only employs a single gamma ray detector. One of the main recent
variants of this technique, from Travar et al. [1], used two detectors in
order to eliminate the effect of a fragment detector asymmetry. This version
is briefly discussed here.

Let $N^{L}$ and $N^{H}$ be the random variables describing the gamma-ray
multiplicities from the light and heavy fragments, respectively. Let us then
take two detectors placed along the line of motion of the fragments, such that
the light fragment flies in the direction of detector $I$ and the heavy
fragment flies in the direction of detector $II$. Let $D^{I}$ and $D^{II}$ be
the random variables describing the measured gamma-ray multiplicity
distributions in detectors $I$ and $II$, respectively. Assuming that each
gamma ray is independently detected , and thus the system response can be
modeled as a binomial response, we have

$\displaystyle D^{I}$ $\displaystyle=$
$\displaystyle\hat{B}(\epsilon_{L+})N^{L}+\hat{B}(\epsilon_{H-})N^{H}$ (1a)
$\displaystyle D^{II}$ $\displaystyle=$
$\displaystyle\hat{B}(\epsilon_{L-})N^{L}+\hat{B}(\epsilon_{H+})N^{H}$ (1b)

where $\hat{B}(\epsilon)$ is the binomial response operator that models the
effect of a system efficiency in measuring multiplicities, and the Doppler-
corrected detection efficiency

$\epsilon_{F\pm}=\epsilon(1\pm 2\beta_{F})\ ,$

is given in terms of the detection efficiency $\epsilon$ of each detector to
an isotropic source and the speed $\beta_{F}$, as a ratio of the speed of
light, of the fragment $F=L,H$ emitting the radiation. Taking the mean of Eq.
(1), we find the well-known formula for inferring the mean gamma-ray emission
[1]

$\displaystyle\langle N^{L}\rangle$ $\displaystyle=$
$\displaystyle\frac{(1+2\beta_{H})\langle D^{I}\rangle-(1-2\beta_{H})\langle
D^{II}\rangle}{4\epsilon(\beta_{L}+\beta_{H})}$ (2a) $\displaystyle\langle
N^{H}\rangle$ $\displaystyle=$ $\displaystyle\frac{(1+2\beta_{L})\langle
D^{II}\rangle-(1-2\beta_{L})\langle
D^{I}\rangle}{4\epsilon(\beta_{L}+\beta_{H})}\ .$ (2b)

Eq. (2) is the conventional ML-DS technique. We now extend its use by
obtaining the covariance between the emitting sources. Analysing the second
order moments of Eq. (1) distributions, we find that they are related to the
emitted multiplicity distribution by the following

$\begin{bmatrix}\Sigma^{2}(D^{I})\\\ \Sigma^{2}(D^{II})\\\
\text{cov}(D^{I},D^{II})\end{bmatrix}=\begin{bmatrix}\epsilon_{L+}^{2}&\epsilon_{H-}^{2}&2\epsilon_{L+}\epsilon_{H-}\\\
\epsilon_{L-}^{2}&\epsilon_{H+}^{2}&2\epsilon_{L-}\epsilon_{H+}\\\
\epsilon_{L+}\epsilon_{L-}&\epsilon_{H-}\epsilon_{H+}&\epsilon_{L+}\epsilon_{H+}+\epsilon_{L-}\epsilon_{H-}\end{bmatrix}\begin{bmatrix}\sigma^{2}(N^{L})\\\
\sigma^{2}(N^{H})\\\ \text{cov}(N^{L},N^{L})\end{bmatrix}\ ,$ (3)

where we have introduced the reduced variances,

$\displaystyle\Sigma^{2}(D^{I})$ $\displaystyle=$
$\displaystyle\sigma^{2}(D^{I})-\langle
N^{L}\rangle\epsilon_{L+}(1-\epsilon_{L+})-\langle
N^{H}\rangle\epsilon_{H-}(1-\epsilon_{H-})$ (4a)
$\displaystyle\Sigma^{2}(D^{II})$ $\displaystyle=$
$\displaystyle\sigma^{2}(D^{II})-\langle
N^{L}\rangle\epsilon_{L-}(1-\epsilon_{L-})-\langle
N^{H}\rangle\epsilon_{H+}(1-\epsilon_{H+})\ .$ (4b)

The reduced variance has a physical meaning. We subtract the expected variance
introduced by the binomial operator from the variance observed in the
detectors. This subtraction can be understood in terms of removing the noise
associated to an information channel, i.e., the binomial response. The mean
emitted multiplicities appearing in the reduced variances can be determined
using Eq. (2).

After inverting the matrix equation in Eq. (3), we obtain an expression for
the covariance in the emission from the two fragments

$\text{cov}(N^{L},N^{H})=\frac{2\text{cov}\left(D^{I},D^{II}\right)(1+4\beta_{H}\beta_{L})-\left[(1+2\beta_{H})(1-2\beta_{L})\Sigma^{2}(D^{I})+(1-2\beta_{H})(1+2\beta_{L})\Sigma^{2}(D^{II})\right]}{16\epsilon^{2}(\beta_{L}+\beta_{H})^{2}}\
.$ (5)

We note that Eq. (5) represents the difference of two factors similar in size,
which is then amplified by the division of the very small factor in the
denominator. For this reason, the equation has a very slow convergence and
requires high statistics. Numerical analysis using reasonable values for the
emission, efficiencies, and speed of the fragments, only converge after
approximately $1\times 10^{8}$ events, thus requiring extremely long
measurement times.

A factor that affects the determination of the covariance, and to a lesser
extent the mean, is the capability of the detector of measuring the
multiplicity. If only detectors capable of measuring a single interaction per
event are used, both the mean and the covariance expression require that the
probability of two incident particles on the detector be much smaller than 1.
This restriction further increases the measurement time. To increase the
efficiency of the system, it is possible to place detectors off of the
fragment-motion axis. However, the efficiency of each detector would have to
be modeled independently because the aberration of gamma-rays, apart for
points along the fission axis, is in general dependent on the angular
distribution of gamma rays in the inertial frame of the fragment.

Notwithstanding these limitations, as far as we know Eq. (5) represents the
only technique capable of measuring the covariance between the emission of
gamma rays by two sources moving at relatively small speeds. This technique
represents the missing piece in the experimental analysis of fission emission
correlations. Together with the techniques discussed for separating the
emission of neutrons and discrete gamma rays, this technique will allow to
determine the correlations in the initial conditions of the fission fragments
and gain a deeper understanding of the fission process.

###### Acknowledgements.

This work was funded in-part by the Consortium for Monitoring, Technology, and
Verification under Department of Energy National Nuclear Security
Administration award number DE-NA0003920.

## References

  * Travar  _et al._ [2021] M. Travar, V. Piau, A. Göök, O. Litaize, J. Nikolov, A. Oberstedt, S. Oberstedt, J. Enders, M. Peck, W. Geerts, and M. Vidali, Experimental information on mass- and tke-dependence of the prompt fission gamma-ray multiplicity, Physics Letters B 817, 136293 (2021).
  * Wilson  _et al._ [2021] J. N. Wilson, D. Thisse, M. Lebois, N. Jovančević, D. Gjestvang, R. Canavan, M. Rudigier, D. Étasse, R.-B. Gerst, L. Gaudefroy, E. Adamska, P. Adsley, A. Algora, M. Babo, K. Belvedere, J. Benito, G. Benzoni, A. Blazhev, A. Boso, S. Bottoni, M. Bunce, R. Chakma, N. Cieplicka-Oryńczak, S. Courtin, M. L. Cortés, P. Davies, C. Delafosse, M. Fallot, B. Fornal, L. Fraile, A. Gottardo, V. Guadilla, G. Häfner, K. Hauschild, M. Heine, C. Henrich, I. Homm, F. Ibrahim, Ł. W. Iskra, P. Ivanov, S. Jazrawi, A. Korgul, P. Koseoglou, T. Kröll, T. Kurtukian-Nieto, L. Le Meur, S. Leoni, J. Ljungvall, A. Lopez-Martens, R. Lozeva, I. Matea, K. Miernik, J. Nemer, S. Oberstedt, W. Paulsen, M. Piersa, Y. Popovitch, C. Porzio, L. Qi, D. Ralet, P. H. Regan, K. Rezynkina, V. Sánchez-Tembleque, S. Siem, C. Schmitt, P.-A. Söderström, C. Sürder, G. Tocabens, V. Vedia, D. Verney, N. Warr, B. Wasilewska, J. Wiederhold, M. Yavahchova, F. Zeiser, and S. Ziliani, Angular momentum generation in nuclear fission, Nature 590, 566 (2021).
  * Schmidt and Jurado [2011] K. H. Schmidt and B. Jurado, Final excitation energy of fission fragments, Phys. Rev. C 83, 061601 (2011).
  * Talou  _et al._ [2018] P. Talou, R. Vogt, J. Randrup, M. E. Rising, S. A. Pozzi, J. Verbeke, M. T. Andrews, S. D. Clarke, P. Jaffke, M. Jandel, T. Kawano, M. J. Marcath, K. Meierbachtol, L. Nakae, G. Rusev, A. Sood, I. Stetcu, and C. Walker, Correlated prompt fission data in transport simulations, The European Physical Journal A 54, 9 (2018).
  * Signarbieux  _et al._ [1972] C. Signarbieux, J. Poitou, M. Ribrag, and J. Matuszek, Correlation entre les energies d’excitation des deux fragments complementaires dans la fission spontanee de 252cf, Physics Letters B 39, 503 (1972).
  * Nifenecker [1970] H. Nifenecker, Correction for fission neutron detector efficiency and unfolding of neutron multiplicity histograms, Nuclear Instruments and Methods 81, 45 (1970).
  * Gavron and Fraenkel [1971] A. Gavron and Z. Fraenkel, Measurement of the variance of the number of neutrons emitted in fission of ${}^{252}\mathrm{Cf}$ as a function of the fragment mass and total kinetic energy, Phys. Rev. Lett. 27, 1148 (1971).
  * Maier-Leibnitz  _et al._ [1965] H. Maier-Leibnitz, H. Schmitt, and P. Armbruster, Proceedings of the symposium on the physics and chemistry of fission, salzburg 1965 (1965) p. 143.
  * Pleasonton  _et al._ [1972] F. Pleasonton, R. Ferguson, and H. Schmitt, Prompt gamma rays emitted in the thermal-neutron-induced fission of u235, Physical Review C 6, 1023 (1972).
  * Schmid-Fabian [1988] R. Schmid-Fabian,  _Investigation of the Spontaneous Fission of Cf-252 at the Heidelberg-Darmstadt Crystal-Ball-Spectrometer_ , Ph.D. thesis, University of Heidelberg (1988).
  * Wang  _et al._ [2016] T. Wang, G. Li, L. Zhu, Q. Meng, L. Wang, H. Han, W. Zhang, H. Xia, L. Hou, R. Vogt, and J. Randrup, Correlations of neutron multiplicity and $\gamma$ -ray multiplicity with fragment mass and total kinetic energy in spontaneous fission of Cf 252, Physical Review C 93, 1 (2016).
  * Vogt and Randrup [2021] R. Vogt and J. Randrup, Angular momentum effects in fission, Phys. Rev. C 103, 014610 (2021).
  * Bulgac [2020] A. Bulgac, Fission-fragment excitation energy sharing beyond scission, Phys. Rev. C 102, 044609 (2020).


N_{i+1}$. This implies that $n_{1}\rho_{1},\ldots,n_{d+1}\rho_{d+1}$ are
$D$-linearly dependent modulo $N_{i+1}$, as we wanted to show. ∎

######  Remark 7.7.

If $\underline{\cal A}$ is wild, so is ${\cal F}(\Delta^{\prime})$ (and so is
${\cal F}(\Delta)$). Indeed, a composition functor

$k\langle x,y\rangle\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{\ \ Z\otimes_{k\langle x,y\rangle}-\ \
}}\underline{A}\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{\ \ L_{\underline{\cal A}}\ \
}}\underline{\cal A}\hbox{-}{\rm Mod}$

which preserves isoclasses and indecomposables as in (2.9) composed with the
equivalence $H:\underline{\cal A}\hbox{-}{\rm mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}{\cal F}(\Delta^{\prime})$, determines a
functor

$HL_{\underline{\cal A}}(Z\otimes_{k\langle x,y\rangle}-):k\langle
x,y\rangle\hbox{-}{\rm mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}{\cal F}(\Delta^{\prime})$

which preserves isoclasses and indecomposables. Moreover, by (6.3), it is such
that $HL_{\underline{\cal A}}(Z\otimes_{k\langle
x,y\rangle}-)\cong\Gamma\otimes_{\underline{A}}Z\otimes_{k\langle
x,y\rangle}-$, where $\Gamma\otimes_{\underline{A}}Z$ is a finitely generated
projective $k\langle x,y\rangle$-module. So ${\cal F}(\Delta^{\prime})$ is
wild. If we compose with the equivalence $\Omega:{\cal
F}(\Delta^{\prime})\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}{\cal F}(\Delta)$, we obtain a functor
$\Omega HL_{\underline{\cal A}}(Z\otimes_{k\langle x,y\rangle}-)$ and a
bimodule producing the wildness of ${\cal F}(\Delta)$.

######  Theorem 7.8.

Assume that ${\cal F}(\Delta^{\prime})$ is not wild. Then, for any
$d\in\mathbb{N}$, consider the functor $F:{\cal B}\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}\underline{\cal
A}\hbox{-}{\rm Mod}$ associated to the composition of reductions of (5.2) and
the equivalence $H:\underline{\cal A}\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}\widetilde{\cal F}(\Delta^{\prime})$.

  1. 1.

The $\Gamma\hbox{-}B$-bimodule $T^{\prime}:=\Gamma\otimes_{\underline{A}}F(B)$
is finitely generated by the right and the composition

$B\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{L_{\cal B}}}{\cal B}\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits^{F}}\underline{\cal
A}\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{H}}\widetilde{\cal F}(\Delta^{\prime})$

is naturally isomorphic to $T^{\prime}\otimes_{B}-$.

In particular, $HF(N)\cong T^{\prime}\otimes_{B}N$, for any $N\in{\cal
B}\hbox{-}{\rm Mod}$. If $N$ is a proper ${\cal B}\hbox{-}E$-bimodule, for
some $k$-algebra $E$, then we have an isomorphism of proper
$\Gamma\hbox{-}E$-bimodules $H_{E}F_{E}(N)\cong T^{\prime}\otimes_{B}(N_{E})$.

  2. 2.

The $\Gamma$-modules of the form $G\cong T^{\prime}\otimes_{B}Q_{i}$ are
generic modules for ${\cal F}(\Delta^{\prime})$.

  3. 3.

Every indecomposable $\Gamma$-module $M\in\widetilde{\cal F}(\Delta^{\prime})$
with $\hbox{\rm endol}\,(M)\leq d$ is isomorphic to $T^{\prime}\otimes_{B}N$,
for some indecomposable ${\cal B}$-module $N$ with finite endolength.

Moreover, if $M$ is generic, we have ${\rm
End}_{\Gamma}(M)^{op}=Q^{\prime}_{M}\bigoplus{\rm rad}{\rm
End}_{\Gamma}(M)^{op}$, for some subalgebra $Q^{\prime}_{M}\cong k(x)$ of
${\rm End}_{\Gamma}(M)^{op}$.

  4. 4.

If $M$ is generic, the $B$-module $N$ is pregeneric and has a natural
structure of $B\hbox{-}k(x)$-bimodule. The morphism of algebras
$\mu:k(x)\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}{\rm
End}_{\Gamma}(T^{\prime}\otimes_{B}N)^{op}$ given by
$\mu(q)=(id_{T^{\prime}}\otimes\mu_{q},0)$ gives $M$ the structure of a proper
$\Gamma\hbox{-}k(x)$-bimodule $T^{\prime}\otimes_{B}N\cong HF(N)\cong M$ such
that $\hbox{\rm endol}\,(M)=\dim_{k(x)}M$.

###### Proof.

(1): From (5.4), we already know that $B\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{L_{\cal B}}}{\cal B}\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits^{F}}\underline{\cal
A}\hbox{-}{\rm Mod}$ is naturally isomorphic to $L_{\underline{\cal
A}}(\overline{T}\otimes_{B}-)$. From (6.3), we know that $HL_{\underline{\cal
A}}\cong\Gamma\otimes_{\underline{A}}-$. So, applying $H$ to the first
isomorphism, we get a natural isomorphism

$HFL_{\cal B}\cong HL_{\underline{\cal
A}}(\overline{T}\otimes_{B}-)\cong\Gamma\otimes_{\underline{A}}(\overline{T}\otimes_{B}-)=T^{\prime}\otimes_{B}-.$

If $N$ is a proper $B\hbox{-}E$-bimodule, from (5.4), so is
$\overline{T}\otimes_{B}N$. Hence, from (7.4), so is $T^{\prime}\otimes_{B}N$.
Moreover, $H_{E}F_{E}(N)\cong T^{\prime}\otimes_{B}N$.

(2): It follows from (5.4) and the fact that $H$ maps pregeneric
$\underline{\cal A}$-modules on generic $\Gamma$-modules in $\widetilde{\cal
F}(\Delta^{\prime})$, see (7.5).

(3)&(4): Suppose first that $M$ is a finite-dimensional indecomposable in
$\widetilde{\cal F}(\Delta^{\prime})$ with $\dim_{k}M=\hbox{\rm
endol}\,(M)\leq d$. Since $H:\underline{\cal A}\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}\widetilde{\cal
F}(\Delta^{\prime})$ is an equivalence, there is a finite-dimensional
indecomposable $N^{\prime}\in\underline{\cal A}\hbox{-}{\rm Mod}$ with
$H(N^{\prime})\cong M$. From (7.5), we know that $\hbox{\rm
endol}\,(N^{\prime})=\dim_{k}N^{\prime}\leq\dim_{k}H(N^{\prime})=\dim_{k}M\leq
d$. Thus, from (5.4), there is a finite-dimensional indecomposable $B$-module
$N$ such that $F(B)\otimes_{B}N\cong N^{\prime}$. So, we get
$M\cong\Gamma\otimes_{\underline{A}}N^{\prime}\cong T^{\prime}\otimes_{B}N$,
where $N$ has finite endolength $\hbox{\rm endol}\,(N)=\dim_{k}N$.

Now, assume that $M$ is a generic $\Gamma$-module in $\widetilde{\cal
F}(\Delta^{\prime})$ with $\hbox{\rm endol}\,(M)\leq d$. Since
$H:\underline{\cal A}\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}\widetilde{\cal F}(\Delta^{\prime})$ is an
equivalence, there is an indecomposable infinite-dimensional
$N\in\underline{\cal A}\hbox{-}{\rm Mod}$ with $H(N)\cong M$. By (7.6), $N$ is
a pregeneric $\underline{\cal A}$-module. By (7.5), we have $\hbox{\rm
endol}\,(N)\leq\hbox{\rm endol}\,(H(N))=\hbox{\rm endol}\,(M)\leq d$. Applying
(5.4)(4) to $N$, we get a pregeneric ${\cal B}$-module $\overline{N}$ such
that $F(B)\otimes_{B}\overline{N}\cong N$, so
$T^{\prime}\otimes_{B}\overline{N}\cong\Gamma\otimes_{\underline{A}}N\cong M$.
Since $H:{\rm End}_{\underline{\cal A}}(N)^{op}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}{\rm End}_{\Gamma}(M)^{op}$ is an
isomorphism of algebras, the splitting of the radical for the second algebra,
follows immediately from the same property for the first one. The fact that
$M$ es a proper $\Gamma\hbox{-}k(x)$-bimodule follows from the corresponding
property for $N$, stated in (5.4)(4), and (7.4). ∎

######  Theorem 7.9.

Assume that ${\cal F}(\Delta)$ is not wild and take any $d\in\mathbb{N}$.
Consider the equivalence $H:\underline{\cal A}\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}\widetilde{\cal
F}(\Delta^{\prime})$ and the Morita equivalence $\Omega:\Gamma\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}\Lambda\hbox{-}{\rm
Mod}$, as in [4](12.9). Assume that $\Omega$ is given as a tensor product
functor $P\otimes_{\Gamma}-$, for an appropriate progenerator $P\in{\rm
mod}\hbox{-}\Gamma$, and that a quasi-inverse for $\Omega$ is given as a
tensor product functor $P^{\prime}\otimes_{\Lambda}-:\Lambda\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}\Gamma\hbox{-}{\rm
Mod}$, for an appropriate progenerator $P^{\prime}\in{\rm
mod}\hbox{-}\Lambda$. Then, consider the functor $F:{\cal B}\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}\underline{\cal
A}\hbox{-}{\rm Mod}$ associated to the composition of reductions of (5.2) and
the natural number $d^{\prime}:=\dim_{k}P^{\prime}\times d$. Then, we have:

  1. 1.

The $\Gamma\hbox{-}B$-bimodule
$T:=P\otimes_{\Gamma}\Gamma\otimes_{\underline{A}}F(B)$ is finitely generated
by the right and the composition

$B\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{L_{\cal B}}}{\cal B}\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits^{F}}\underline{\cal
A}\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{H}}\widetilde{\cal
F}(\Delta^{\prime})\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{\Omega}}\widetilde{\cal F}(\Delta)$

is naturally isomorphic to $T\otimes_{B}-$.

In particular, $\Omega HF(N)\cong T\otimes_{B}N$, for any $N\in{\cal
B}\hbox{-}{\rm Mod}$. If $N$ is a proper ${\cal B}\hbox{-}E$-bimodule, for
some $k$-algebra $E$, then we have an isomorphism of proper
$\Lambda\hbox{-}E$-bimodules $\Omega_{E}H_{E}F_{E}(N)\cong
T\otimes_{B}(N_{E})$.

  2. 2.

The $\Lambda$-modules of the form $G\cong T\otimes_{B}Q_{i}$ are generic
modules for ${\cal F}(\Delta)$.

  3. 3.

Every indecomposable $\Lambda$-module $M\in\widetilde{\cal F}(\Delta)$ with
$\hbox{\rm endol}\,(M)\leq d$ is isomorphic to $T\otimes_{B}N$, for some
indecomposable ${\cal B}$-module $N$ with finite endolength.

Moreover, if $M$ is generic we have ${\rm
End}_{\Lambda}(M)^{op}=Q_{M}\bigoplus{\rm rad}{\rm End}_{\Lambda}(M)^{op}$,
for some subalgebra $Q_{M}\cong k(x)$ of ${\rm End}_{\Lambda}(M)^{op}$.

  4. 4.

If $M$ is generic, the $B$-module $N$ is pregeneric and has a natural
structure of $B\hbox{-}k(x)$-bimodule. The morphism of algebras
$\mu:k(x)\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}{\rm
End}_{\Lambda}(T\otimes_{B}N)^{op}$ given by $\mu(q)=(id_{T}\otimes\mu_{q},0)$
gives $M$ the structure of a proper $\Lambda\hbox{-}k(x)$-bimodule
$T\otimes_{B}N\cong\Omega HF(N)\cong M$ such that $\hbox{\rm
endol}\,(M)=\dim_{k(x)}M$.

###### Proof.

(1): From (7.8), we know that $B\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{L_{\cal B}}}{\cal B}\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits^{F}}\underline{\cal
A}\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{H}}\widetilde{\cal F}(\Delta^{\prime})$ is
naturally isomorphic to $T^{\prime}\otimes_{B}-$. So, applying
$\Omega=P\otimes_{\Gamma}-$ to the first isomorphism, we get a natural
isomorphism

$\Omega HFL_{\cal B}\cong\Omega(T^{\prime}\otimes_{B}-)\cong T\otimes_{B}-.$

If $N$ is a proper $B\hbox{-}E$-bimodule, from (7.9), so is
$T^{\prime}\otimes_{B}N$. Hence, so is $T\otimes_{B}N$. Moreover,
$\Omega_{E}H_{E}F_{E}(N)\cong T\otimes_{B}N$.

(2): It follows from (7.8) and the fact that $\Omega$ preserves generic
modules.

(3)&(4): Suppose first that $M$ is a finite-dimensional indecomposable in
$\widetilde{\cal F}(\Delta)$ with $\dim_{k}M=\hbox{\rm endol}\,(M)\leq d$.
Then, $M^{\prime}:=P^{\prime}\otimes_{\Lambda}M$ is a finite-dimensional
indecomposable in ${\cal F}(\Delta^{\prime})$ with $\hbox{\rm
endol}\,(M^{\prime})=\dim_{k}M^{\prime}\leq d^{\prime}$. From (7.8), there is
a finite-dimensional indecomposable $B$-module $N$ such that
$T^{\prime}\otimes_{B}N\cong M^{\prime}$. So, we get $M\cong
P\otimes_{\Gamma}M^{\prime}\cong T\otimes_{B}N$, where $N$ has finite
endolength $\hbox{\rm endol}\,(N)=\dim_{k}N$.

Now, assume $M$ is a generic $\Lambda$-module in $\widetilde{\cal F}(\Delta)$
with $\hbox{\rm endol}\,(M)\leq d$. Since
$\Omega=P\otimes_{\Gamma}-:\widetilde{\cal
F}(\Delta^{\prime})\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}\widetilde{\cal F}(\Delta)$ is an
equivalence, the infinite-dimensional indecomposable
$M^{\prime}:=P^{\prime}\otimes_{\Lambda}M\in\widetilde{\cal
F}(\Delta^{\prime})$ satisfies $\Omega(M^{\prime})\cong M$. We know that
$\hbox{\rm endol}\,(M^{\prime})\leq\dim_{k}P^{\prime}\times\hbox{\rm
endol}\,(M)\leq\dim_{k}P^{\prime}\times d=d^{\prime}$, see for instance
[2](11.1). So, $M^{\prime}$ is a generic $\Gamma$-module in $\widetilde{\cal
F}(\Delta^{\prime})$ with $\hbox{\rm endol}\,(M^{\prime})\leq d^{\prime}$. By
(7.8), there is a pregeneric ${\cal B}$-module $N$ such that
$T^{\prime}\otimes_{B}N\cong M^{\prime}$. Therefore, we obtain
$T\otimes_{B}N\cong
P\otimes_{\Gamma}\Gamma\otimes_{\underline{A}}F(B)\otimes_{B}N\cong M$. Since
$\Omega:{\rm End}_{\Gamma}(M^{\prime})^{op}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}{\rm End}_{\Lambda}(M)^{op}$ is an
isomorphism, the splitting of the radical for the second algebra follows from
the same property for the first one. The fact that $M$ is a proper
$\Lambda\hbox{-}k(x)$-bimodule follows from the corresponding property for
$M^{\prime}$. ∎

##  8 Generic modules for ${\cal F}(\Delta)$

Proof of Theorem (1.5). Let $d:=\hbox{\rm endol}\,(G)$ and apply (7.9) to
obtain the minimal ditalgebra ${\cal B}$ and the composition of functors

$B\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{L_{\cal B}}}{\cal B}\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits^{F}}\underline{\cal
A}\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{H}}\widetilde{\cal
F}(\Delta^{\prime})\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{\Omega}}\widetilde{\cal F}(\Delta),$

isomorphic to a suitable tensor functor $T\otimes_{B}-$.

By (7.9)(2), there is a generic $B$-module $N\in{\cal B}\hbox{-}{\rm Mod}$
with $\Omega HF(N)\cong T\otimes_{B}N$. In fact,
$N=Be_{i}\otimes_{Be_{i}}Q_{i}$, where $Q_{i}$ is the field of fractions of
$\Gamma_{i}=Be_{i}$ considered as a $\Gamma_{i}$-module. Here $Be_{i}$ is a
rational $k$-algebra and $Q_{i}=k(x)$.

We have

$G\cong T\otimes_{B}N=T\otimes_{B}Be_{i}\otimes_{Be_{i}}Q_{i}\cong
Te_{i}\otimes_{Be_{i}}Q_{i},$

where $Te_{i}$ is a right finitely generated $Be_{i}$-module, so there is some
$g\in Be_{i}$ such that $Z_{G}:=Te_{i}\otimes_{Be_{i}}(Be_{i})_{g}$ is a free
finitely generated right $Be_{i}$-module. Moreover, the field of fractions
$Q_{G}$ of the rational algebra $\Gamma_{G}:=(Be_{i})_{g}$ coincides with
$k(x)=Q_{i}$, and we have

$Z_{G}\otimes_{\Gamma_{G}}Q_{G}=Te_{i}\otimes_{Be_{i}}(Be_{i})_{g}\otimes_{(Be_{i})_{g}}Q_{i}\cong
Te_{i}\otimes_{Be_{i}}Q_{i}\cong G.$

From the last statement of (7.9), we know that $\dim_{k(x)}G=\hbox{\rm
endol}\,(G)$ and from the last displayed formula, the rank of $Z_{G}$ is
$\dim_{k(x)}G$, so (1) is proved.

(2): Since ${\cal B}$ is a minimal ditalgebra, we know that $L_{\cal
B}:B\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}{\cal B}\hbox{-}{\rm Mod}$ preserves
isoclasses, indecomposability and maps almost split sequences onto almost
split conflations, see for instance [5](32.3). Since $\Omega$, $H$, and $F$
are full and faithful functors, they all preserve isoclasses and
indecomposability. Then, the functor $T\otimes_{B}-\cong\Omega HFL_{\cal B}$
preserves isoclasses and indecomposability. The localization morphism
$\phi:Be_{i}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}(Be_{i})_{h}=\Gamma_{G}$ is an epimorphism
which induces a full and faithful functor $F_{\phi}:\Gamma_{G}\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}Be_{i}\hbox{-}{\rm
Mod}$ which can be composed with the embedding functor $E:Be_{i}\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}B\hbox{-}{\rm
Mod}$. Then the functor $Z_{G}\otimes_{\Gamma_{G}}-\cong\Omega HFL_{\cal
B}EF_{\phi}$ preserves isoclasses and indecomposables.

(3): We know that, given any Roiter interlaced weak ditalgebra
$\underline{\cal A}$, the category $\underline{\cal A}\hbox{-}{\rm Mod}$ has a
natural exact structure ${\cal E}_{\underline{\cal A}}$, see [4](10.11). From
(2.10), we know that $\underline{\cal A}^{z}$ is a Roiter interlaced weak
ditalgebra whenever $\underline{\cal A}$ is so, for $z\in\\{a,r,q,d,X\\}$.
Moreover, by (6.5) we know that $\underline{\cal A}(\Delta)\hbox{-}{\rm mod}$
has almost split conflations.

By [4](10.5), the functor $F^{X}:\underline{\cal A}^{X}\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}\underline{\cal
A}\hbox{-}{\rm Mod}$ is exact, when $\underline{\cal A}$ is a Roiter
interlaced weak ditalgebra, see [5](16.6). The same observations of
[5][(9.8),(9.9),(9.10)] show that the functors $F^{z}:\underline{\cal
A}^{z}\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}\underline{\cal A}\hbox{-}{\rm Mod}$, for
$z\in\\{a,r,q,d\\}$, as in (2.1), (2.2), (2.3), (2.4), are exact, when
$\underline{\cal A}$ is a Roiter interlaced weak ditalgebra. These statements,
and the corresponding ones for reduction functors $F^{z}$ of type
$z\in\\{a,r,d,e,u\\}$ between module categories of Roiter ditalgebras, imply
that the functor $F$ is exact (since it is a composition of such exact
functors). So the composition $F:{\cal B}\hbox{-}{\rm mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}\underline{\cal A}(\Delta)\hbox{-}{\rm mod}$
is a full and faithful exact functor between Krull-Schmidt categories with
exact structures which admit almost split conflations.

From (6.7), we know that there are only finitely many indecomposable
$\Gamma_{G}$-modules of the form $E_{\lambda}:=\Gamma_{G}/\langle
x-\lambda\rangle$ such that $FL_{\cal B}EF_{\phi}(E_{\lambda})\not\cong\tau
FL_{\cal B}EF_{\phi}(E_{\lambda})$. If this occurs for
$\lambda_{1},\ldots,\lambda_{t}\in k$, we can replace the polynomial $g$ used
at the begining of this proof by
$g^{\prime}:=g(x-\lambda_{1})\cdots(x-\lambda_{t})$ to obtain a rational
algebra $\Gamma^{\prime}_{G}=(Ee_{i})_{g^{\prime}}$ such that $FL_{\cal
B}EF_{\phi}(E_{\lambda})\cong\tau FL_{\cal B}EF_{\phi}(E_{\lambda})$, for all
such indecomposables $E_{\lambda}$ of $\Gamma^{\prime}_{G}$, and we adjust
$Z^{\prime}_{G}:=Te_{i}\otimes_{Be_{i}}(Be_{i})_{g^{\prime}}$ accordingly.
Moreover, (1) and (2), still hold for this $Z^{\prime}_{G}$. So we can assume
that $\Gamma_{G}$ and $Z_{G}$ already have this property and we can apply
[5](32.7), to obtain that $FL_{\cal B}FEF_{\phi}$ preserves almost split
conflations. Since $H$ and $\Omega$ are exact equivalences, so does
$Z_{G}\otimes_{\Gamma_{G}}-\cong\Omega HFL_{\cal B}EF_{\phi}$. $\square$

######  Proposition 8.1.

If ${\cal F}(\Delta)$ is not wild, then it is generically tame.

Moreover, in this case, for any $d\in\mathbb{N}$, almost all indecomposable
$\Lambda$-modules $M\in{\cal F}(\Delta)$ with $\dim_{k}M\leq d$ are of the
form $M\cong Z_{G}\otimes_{\Gamma_{G}}N$, for some generic module $G$ for
${\cal F}(\Delta)$ with $\hbox{\rm endol}\,(G)\leq d$ and some indecomposable
$N\in\Gamma_{G}\hbox{-}{\rm mod}$, with the notation of (1.5).

###### Proof.

Take $d\in\mathbb{N}$ and and apply (7.9) to obtain the minimal ditalgebra
${\cal B}$ and the composition of functors

$B\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{L_{\cal B}}}{\cal B}\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits^{F}}\underline{\cal
A}\hbox{-}{\rm Mod}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{H}}\widetilde{\cal
F}(\Delta^{\prime})\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits^{\Omega}}\widetilde{\cal F}(\Delta),$

isomorphic to a suitable tensor functor $T\otimes_{B}-$.

Then, from (7.9), we know that the generic $\Lambda$-modules in
$\widetilde{\cal F}(\Delta)$ with endolength $\leq d$, up to isomorphism, are
$G_{1},\ldots,G_{n}$, with $G_{i}=\Omega HFL_{\cal B}(Q_{i})$, for
$i\in[1,n]$, where $n$ is the number of rational factors of the minimal
algebra of the layer of ${\cal B}$. Here $Q_{i}$ is the $B$-module described
in (5.3).

From (7.9) applied to indecomposable $\Lambda$-modules in ${\cal F}(\Delta)$,
we get that any indecomposable $\Lambda$-module $M\in{\cal F}(\Delta)$ with
$\dim_{k}M\leq d$ is isomorphic to $T\otimes_{B}N$, for some indecomposable
$Be_{i}$-module $N$ with bounded dimension. Now, recall from the preceding
proof that each bimodule $Z_{i}=Te_{i}\otimes_{Be_{i}}(Be_{i})_{h}$,
associated to a given generic module $G_{i}$ for ${\cal F}(\Delta)$, involves
a localization of $k$-algebras $\phi:Be_{i}\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}(Be_{i})_{h}$ whose restriction functor
$F_{\phi}:\Gamma_{G}\hbox{-}{\rm mod}=(Be_{i})_{h}\hbox{-}{\rm
mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}Be_{i}\hbox{-}{\rm
mod}$ hits all isoclasses of indecomposable $Be_{i}$-modules with bounded
dimension, with only finitely many exceptions. Then, the second statement of
this theorem holds. ∎

######  Proposition 8.2.

If ${\cal F}(\Delta)$ is wild, then it is not generically tame.

###### Proof.

We adapt the argument of the proof of [9](4.4). Since ${\cal F}(\Delta)$ is
wild (resp. generically tame) iff ${\cal F}(\Delta^{\prime})$ is wild (resp.
generically tame), see [3](1.6) and [5](22.6), it will be enough to prove the
statement for ${\cal F}(\Delta^{\prime})$.

Assume ${\cal F}(\Delta^{\prime})$ is wild, then there is a
$\Gamma\hbox{-}k\langle x,y\rangle$-bimodule $Z$, which is free finitely
generated as a right module, such that the functor

$W=Z\otimes_{k\langle x,y\rangle}-:k\langle x,y\rangle\hbox{-}{\rm
mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}{\cal
F}(\Delta^{\prime})$

preserves isoclasses and indecomposables. The argument in the proofs of
[3][(11.4) and (1.3)], see also [3](7.11), shows that we may assume that the
bimodule $Z$ determines a functor

$W=Z\otimes_{k\langle x,y\rangle}-:k\langle x,y\rangle\hbox{-}{\rm
Mod}\smash{\mathop{\hbox to20.0pt{\rightarrowfill}}\limits}\widetilde{\cal
F}(\Delta^{\prime}),$

which preserves isoclasses and idecomposables. As in [5][(31.3) and (31.5)],
we consider the $k\langle x,y\rangle$-modules
$H_{\lambda}=k(x)[y]/(y-\lambda)$, for $\lambda\in k$, where $k\langle
x,y\rangle$ acts by restriction through the epimorphism of algebras

$k\langle x,y\rangle\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}k[x,y]\smash{\mathop{\hbox
to20.0pt{\rightarrowfill}}\limits}k[x,y]_{k[x]^{*}}\cong k(x)[y].$

The family $\\{H_{\lambda}\\}_{\lambda\in k}$ is an infinite family of
pairwise non-isomorphic generic $k\langle x,y\rangle$-modules with endolength
1. Make $G_{\lambda}:=W(H_{\lambda})$, for $\lambda\in k$. So
$\\{G_{\lambda}\\}_{\lambda\in k}$, is an infinite family of pairwise non-
isomorphic generic $\Gamma$-modules in $\widetilde{F}(\Delta^{\prime})$ with
bounded endolength. So ${\cal F}(\Delta^{\prime})$ is not generically tame. ∎

######  Theorem 8.3.

${\cal F}(\Delta)$ is generically tame iff ${\cal F}(\Delta)$ is tame.

###### Proof.

From (1.9), we already know that $\underline{\cal A}$ is pregenerically tame
iff $\underline{\cal A}$ is not wild.

If ${\cal F}(\Delta)$ is tame then, by [3](1.3), ${\cal F}(\Delta)$ is not
wild. So, by (7.7), we know that $\underline{\cal A}$ is not wild and, as
mentioned before, this means that it is pregenerically tame. Thus given
$d\in\mathbb{N}$, any generic module $G$ for ${\cal F}(\Delta)$ with
$\hbox{\rm endol}\,(G)\leq d$ is the image under $\Omega H$ of a pregeneric
$\underline{\cal A}$-module $M$ with bounded endolength, so there are only a
finite number of non-isomorphic generic modules for ${\cal F}(\Delta)$ with
endolength $\leq d$. Hence, ${\cal F}(\Delta)$ is generically tame.

Conversely, assume that ${\cal F}(\Delta)$ is generically tame. By (8.2), it
can not be wild. So, by [3](1.3), it is tame. ∎

## References

  * [1] R. Bautista, E. Pérez, and L. Salmerón. On generically tame algebras over perfect fields. Adv. in Math. 231 (2012) 436–481.
  * [2] R. Bautista, E. Pérez, and L. Salmerón. Generic modules of tame algebras over real closed fields. J. of Algebra 419 (2014) 223–276.
  * [3] R. Bautista, E. Pérez, and L. Salmerón, Tame and wild theorem for the category of filtered by standard modules for a quasi-hereditary algebra, Preprint: arXiv: 1706.07386v1, June, 2017.
  * [4] R. Bautista, E. Pérez, and L. Salmerón. Homological systems and bocses. Preprint arXiv: 2012.13781v1, 2020.
  * [5] R. Bautista, L. Salmerón, and R. Zuazua. Differential Tensor Algebras and their Module Categories. London Math. Soc. Lecture Note Series 362. Cambridge University Press, 2009.
  * [6] W.L. Burt and M.C.R. Butler, Almost split sequences for bocses. Representations of finite dimensional algebras. Canadian Math. Soc. Conference Proceedings, 11 (1990) 89–121.
  * [7] W.L. Burt, Almost split sequences and bocses, Unpublished Monograph (2005).
  * [8] W.W. Crawley-Boevey. On tame algebras and bocses. Proc. London Math. Soc. (3) 56 (1988) 451–483.
  * [9] W.W. Crawley-Boevey. Tame algebras and generic modules. Proc. London Math. Soc. (3) 63 (1991) 241–265.
  * [10] W.W. Crawley-Boevey. Modules of Finite Length over their Endomorphism Rings. London Math. Soc. Lecture Note Series 168, Cambridge University Press, (1992) 127–184
  * [11] V. Dlab and C.M. Ringel. The Module Theoretical Approach to Quasi-hereditary Algebras. London Math. Soc. Lecture Note Series 168, Cambridge University Press, (1992) 200–224
  * [12] S. Koenig, J. Külshammer, and S. Ovsienko. _Quasi-hereditary algebras, exact Borel subalgebras, $A_{\infty}$-categories and boxes._ Adv. Math. 262 (2014), 546–592.

R. Bautista
Centro de Ciencias Matemáticas
Universidad Nacional Autónoma de México
Morelia, México
<EMAIL_ADDRESS>

E. Pérez
Facultad de Matemáticas
Universidad Autónoma de Yucatán
Mérida, México
<EMAIL_ADDRESS>

L. Salmerón
Centro de Ciencias Matemáticas
Universidad Nacional Autónoma de México
Morelia, México
<EMAIL_ADDRESS>


# Odd Colorings of Sparse Graphs

Daniel W. Cranston Department of Computer Science, Virginia Commonwealth
University, Richmond, VA, USA<EMAIL_ADDRESS>
###### Abstract

A proper coloring of a graph is called _odd_ if every non-isolated vertex has
some color that appears an odd number of times on its neighborhood. The
smallest number of colors that admits an odd coloring of a graph $G$ is
denoted $\chi_{o}(G)$. This notion was introduced by Petruševski and
Škrekovski, who proved that if $G$ is planar then $\chi_{o}(G)\leq 9$; they
also conjectured that $\chi_{o}(G)\leq 5$. For a positive real number
$\alpha$, we consider the maximum value of $\chi_{o}(G)$ over all graphs $G$
with maximum average degree less than $\alpha$; we denote this value by
$\chi_{o}(\mathcal{G}_{\alpha})$. We note that
$\chi_{o}(\mathcal{G}_{\alpha})$ is undefined for all $\alpha\geq 4$. In
contrast, for each $\alpha\in[0,4)$, we give a (nearly sharp) upper bound on
$\chi_{o}(\mathcal{G}_{\alpha})$. Finally, we prove
$\chi_{o}(\mathcal{G}_{20/7})=5$ and $\chi_{o}(\mathcal{G}_{3})=6$. Both of
these results are sharp.

##  1 Introduction

A proper coloring of a graph is _odd_ ††margin:  odd coloring if every non-
isolated vertex has some color that appears an odd number of times on its
neighborhood. The smallest number of colors that admits an odd coloring of a
graph $G$ is denoted _$\chi_{o}(G)$_ ††margin:  $\chi_{o}(G)$ . Clearly,
$\chi_{o}(G)\leq|V(G)|$, since we can simply color each vertex with its own
color. This notion was introduced by Petruševski and Škrekovski [13], who
proved that if $G$ is planar then $\chi_{o}(G)\leq 9$; they also conjectured
that $\chi_{o}(G)\leq 5$.

Odd coloring is motivated by various types of hypergraph coloring. A
hypergraph $\mathcal{H}$ consists of a set $\mathcal{V}$ of vertices and a set
$\mathcal{E}$ of (hyper)edges, each of which consists of an arbitrary set of
vertices in $\mathcal{V}$. Most varieties of hypergraph coloring assign colors
(integers in $\\{1,\ldots,k\\}$) to the elements of $\mathcal{V}$ subject to
certain constraints. Standard hypergraph coloring requires only that no edge
in $\mathcal{E}$ is monochromatic. Even et al. [6] introduced _conflict-free_
coloring, which requires that each edge in $\mathcal{E}$ has some color that
appears exactly once on its vertices. This topic has been widely studied [5,
8, 9, 12, 14]. Cheilaris et al. [4] studied _odd_ coloring of hypergraphs,
which requires that each edge in $\mathcal{E}$ has some color that appears an
odd number of times on its vertices. Aspects of this problem have been studied
in [1, 2, 7]. For graphs, Cheilaris [3] studied conflict-free colorings with
respect to open neighborhoods. That is, for each vertex $v$ some color appears
exactly once on $N(v)$. Finally, Petruševski and Škrekovski [13] studied odd
colorings of graphs, which are proper colorings where each vertex $v$ has some
color that appears an odd number of times on $N(v)$. It is this parameter that
we consider in the present short note.

The average degree of a graph $H$ is $2|E(H)|/|V(H)|$. The _maximum average
degree_ of a graph $G$, denoted _$\mathrm{mad}(G)$_ ††margin:
$\mathrm{mad}(G)$ , is the maximum, over all non-empty subgraphs $H$ of $G$,
of the average degree of $H$. That is, $\mathrm{mad}(G):=\max_{H\subseteq
G}2|E(H)|/|V(H)|$. For each positive real number $\alpha$, let
$\mathcal{G}_{\alpha}$ denote the family of graphs $G$ with
$\mathrm{mad}(G)<\alpha$. We denote by
$\chi_{o}(\mathcal{G}_{\alpha})$††margin:  $\mathcal{G}_{\alpha}$,
$\chi_{o}(\mathcal{G}_{\alpha})$ the maximum value of $\chi_{o}(G)$ over all
$G\in\mathcal{G}_{\alpha}$. The focus of this paper is bounding
$\chi_{o}(\mathcal{G}_{\alpha})$ for various values of $\alpha$. We observe
that $\chi_{o}(\mathcal{G}_{\alpha})$ is undefined for all $\alpha\geq 4$.
That is, there exists a sequence of graphs $G_{n}$ such that
$\chi_{o}(G_{n})=n$ and $\mathrm{mad}(G_{n})<4$ for all $n$. In contrast, for
each $\alpha\in[0,4)$, we give a (nearly sharp) upper bound on
$\chi_{o}(\mathcal{G}_{\alpha})$. We have two main results.

######  Theorem 1.

Fix $\epsilon$ such that $0<\epsilon\leq 8/5$. If $\mathrm{mad}(G)\leq
4-\epsilon$, then $\chi_{o}(G)\leq\lfloor 8/\epsilon\rfloor+2$. As
$\epsilon\to 0$, infinitely often there exists $G_{\epsilon}$ such that
$\mathrm{mad}(G_{\epsilon})=4-\epsilon$ and $\chi_{o}(G_{\epsilon})=\lfloor
8/\epsilon\rfloor-1$.

When $\epsilon\in\\{1,8/7\\}$, we prove sharper upper bounds on
$\chi_{o}(G_{4-\epsilon})$.

######  Theorem 2.

Fix a graph $G$. (a) If $\mathrm{mad}(G)<3$, then $\chi_{o}(G)\leq 6$; and (b)
if $\mathrm{mad}(G)<20/7$, then $\chi_{o}(G)\leq 5$. Furthermore, neither of
these upper bounds on $\chi_{o}(G)$ can be decreased, and neither of the
inequalities can be weakened to allow equality.

For a proper coloring $\varphi$ of some subgraph $H$ of $G$, let
_$\varphi_{o}(v)$_ ††margin:  $\varphi_{o}(v)$ denote the unique color that
appears an odd number of times in $N_{H}(v)$ if such a color exists;
otherwise, $\varphi_{o}(v)$ is undefined. Most of the rest of our notation and
definitions are standard. But for the reader’s convenience we highlight a few
terms. The _girth_ ††margin:  girth of a graph $G$ is the length of a shortest
cycle in $G$ (the girth of an acyclic graph is infinite). A
$k$-vertex††margin:  $k$/$k^{+}$/$k^{-}$-vertex is a vertex of degree $k$. A
$k^{+}$-vertex (resp. $k^{-}$-vertex) is a vertex of degree at least (resp. at
most) $k$. A $k$-neighbor††margin:  $k$/$k^{+}$/$k^{-}$-neighbor of a vertex
$v$ is a neighbor of $v$ that is a $k$-vertex. Both $k^{+}$-neighbor and
$k^{-}$-neighbor are defined analogously.

To close this introduction, we prove three easy results about graphs $G$ with
$\chi_{o}(G)\leq 4$.

######  Proposition 1.

A graph $G$ has $\chi_{o}(G)=1$ if and only if $G$ has vertices but no edges.
And $G$ has $\chi_{o}(G)=2$ if and only if $G$ is bipartite and the degree of
each vertex in $G$ is either 0 or odd.

###### Proof.

The first statement is obvious, so now we prove the second. If $G$ is
bipartite, then $G$ has a proper 2-coloring $\varphi$. If the degree of each
vertex is either 0 or odd, then $\varphi$ is also an odd 2-coloring of $G$. If
$G$ is not bipartite, then $G$ has no proper 2-coloring, so clearly
$\chi_{o}(G)>2$. Suppose instead $G$ is bipartite, but some vertex $v$ has
positive even degree. Now the component of $G$ containing $v$ has only a
single 2-coloring (up to permuting colors), but this 2-coloring is not odd
since $N(v)$ has only a single color, which appears an even number of times. ∎

######  Proposition 2.

If $3|n$, then $\chi_{o}(C_{n})=3$. If $n=5$, then $\chi_{o}(C_{n})=5$.
Otherwise, $\chi_{o}(C_{n})=4$.

###### Proof.

If $3|n$, then we can repeat the colors $1,2,3,1,2,3,\ldots$ around $C_{n}$ to
get an odd 3-coloring. Suppose instead that $3\nmid n$. By the Pigeonhole
principle, in every proper 3-coloring $\varphi$ some color appears twice on
the neighborhood of some vertex $v$, so $\varphi$ is not odd. Thus,
$\chi_{o}(C_{n})\geq 4$. If $3\nmid n$ and $n\neq 5$, then we can begin with
$1,2,3,4$ or $1,2,3,4,1,2,3,4$ and continue with $1,2,3,1,2,3\ldots$. Finally,
it is easy to check that each proper 4-coloring $\varphi$ of $C_{5}$ uses the
same color on both neighbors of some vertex, so $\varphi$ is not an odd
coloring. Thus, $\chi_{o}(C_{5})=5$. ∎

It is interesting to note that the class of graphs $G$ with
$\mathrm{mad}(G)=2$ and $\chi_{o}(G)=4$ is richer than simply cycles $C_{n}$
with $3\nmid n$. Denote the vertices of $C_{n}$ by $v_{1},\ldots,v_{n}$.
Starting from such a graph, we can add arbitrarily many leaves at each $v_{i}$
with $3|i$. It is straightforward to check that the resulting graph
$G^{\prime}$ also has $\mathrm{mad}(G^{\prime})=2$ and
$\chi_{o}(G^{\prime})=4$. More generally, we can identify these $v_{i}$ with
vertices of an arbitrary graph and $\chi_{o}$ will not decrease.

######  Proposition 3.

Every tree $T$ has $\chi_{o}(T)\leq 3$. Thus, if $\mathrm{mad}(T)<2$, then
$\chi_{o}(T)\leq 3$. This bound on $\mathrm{mad}(T)$ is sharp.

###### Proof.

Let $T$ be a tree. We use induction on $|T|$. The case $|T|=1$ is trivial. Now
suppose that $|T|\geq 2$. Let $v$ be a leaf of $T$. Let $T^{\prime}:=T-v$ and
note that $T^{\prime}$ is a tree. By hypothesis, $T^{\prime}$ has an odd
3-coloring $\varphi$. Let $w$ be the neighbor of $v$ in $T$. To extend
$\varphi$ to an odd 3-coloring of $T$, we color $v$ with a color outside
$\\{\varphi(w),\varphi_{o}(w)\\}$. This gives the desired odd 3-coloring of
$T$.

If $\mathrm{mad}(G)<2$, then $G$ is a forest. So the second statement follows
from the first. Finally, the third statement follows from Proposition 2. ∎

The following proposition is folklore. But we include a proof for
completeness.

######  Proposition 4.

If $G$ is a planar graph with girth at least $g$, then
$\mathrm{mad}(G)<2g/(g-2)$.

###### Proof.

Fix a plane embedding of a planar graph $G$ with girth at least $g$. Since
each subgraph of $G$ also has girth at least $g$, it suffices to show that
$2|E(G)|/|V(G)|<2g/(g-2)$. Summing the lengths of all facial walks gives
$2|E(G)|\geq g|F|$, where $F$ is the set of all faces. To prove the
proposition, we substitute this inequality into Euler’s formula and solve for
$2|E(G)|/|V(G)|$. ∎

##  2 $\mathrm{Mad}(G)<4$

Recall, for each $\alpha>0$, that $\mathcal{G}_{\alpha}$ denotes the set of
all graphs $G$ with $\mathrm{mad}(G)<\alpha$; and we write
$\chi_{o}(\mathcal{G}_{\alpha})$ to denote the maximum value of $\chi_{o}(G)$
over all $G\in\mathcal{G}_{\alpha}$. Proposition 3 shows that
$\chi_{o}(G_{2})=3$. In this section, we determine the set of all values
$\alpha$ such that $\chi_{o}(\mathcal{G}_{\alpha})$ is defined; when it is
defined, we prove a (nearly sharp) upper bound on its value.

We denote by _$K_{n}^{*}$_ ††margin:  $K_{n}^{*}$ the graph formed from
$K_{n}$ by subdiving each edge once.

######  Lemma 5.

We have $\chi_{o}(K_{n}^{*})=n$ and $\mathrm{mad}(K_{n}^{*})=4-8/(n+1)$.

###### Proof.

For each $n\geq 1$, let $\epsilon_{n}:=8/(n+1)$. To show that
$\mathrm{mad}(K^{*}_{n})=4-\epsilon_{n}$, we give a fractional orientation of
$K^{*}_{n}$ where each vertex has indegree exactly $2-\epsilon_{n}/2$. We
orient each edge with fraction $1-\epsilon_{n}/4$ towards its endpoint of
degree 2 and fraction $\epsilon_{n}/4$ toward its endpoint of degree $n$. Each
2-vertex has indegree $2(1-\epsilon_{n}/4)=2-\epsilon_{n}/2$. Each
$(n-1)$-vertex has indegree
$(n-1)(\epsilon_{n}/4)=(n-1)(2/(n+1))=(2n-2)/(n+1)=2-4/(n+1)=2-\epsilon_{n}/2$.
Thus, $\mathrm{mad}(G)=4-\epsilon_{n}$, as desired.

In an odd coloring of $K^{*}_{n}$, all $(n-1)$-vertices must get distinct
colors. So $\chi_{o}(K^{*}_{n})\geq n$. Given any coloring where all
$(n-1)$-vertices get distinct colors, it is easy to extend to an odd
$n$-coloring of $K^{*}_{n}$. Thus, as claimed, $\chi_{o}(K^{*}_{n})=n$. ∎

######  Corollary 6.

There exists a sequence $\epsilon_{1},\epsilon_{2},\ldots$ such that
$\epsilon_{n}>0$ for all $n\geq 1$ and $\lim_{n\to\infty}\epsilon_{n}=0$ and
for each $n\geq 1$ there exists a graph $G_{n}$ with
$\mathrm{mad}(G_{n})=4-\epsilon_{n}$ and $\chi_{o}(G_{n})=8/\epsilon_{n}-1$.

###### Proof.

Let $\epsilon_{n}:=8/(n+1)$ and $G_{n}:=K^{*}_{n}$. Now
$\chi_{o}(G_{n})=n=(n+1)-1=8/\epsilon_{n}-1$. ∎

######  Corollary 7.

$\chi_{o}(\mathcal{G}_{\alpha})$ is undefined whenever $\alpha\geq 4$.

In Lemma 5, we considered $K^{*}_{n}$ which is formed by subdividing each edge
of $K_{n}$. Applying the same construction to any $n$-chromatic graph $H$
yields a graph $H^{\prime}$ with $\chi_{o}(H^{\prime})=n$ and
$\mathrm{mad}(H^{\prime})<4$. Since there exist graphs $H$ with both chromatic
number and girth arbitrarily large, there also exist graphs $H^{\prime}$ with
$\chi_{o}(H^{\prime})$ and girth arbitrarily large, and with
$\mathrm{mad}(H^{\prime})<4$. However, every $n$-chromatic graph $H$ that does
not contain $K_{n}$ as a subgraph gives an upper bound on $4-\epsilon$ that is
worse (larger) than that in Corollary 6. Consider an $n$-critical (sub)graph
$H$ with $a$ vertices and $b$ edges. Recall that $\delta(H)\geq n-1$. But $H$
is not $(n-1)$-regular, by Brooks’ Theorem. Thus,
$b=|E(H)|>(n-1)|V(H)|/2=(n-1)a/2$. Subdividing each edge of $H$ gives
$H^{\prime}$ with $|V(H^{\prime})|=a+b$ and $|E(H^{\prime})|=2b>a(n-1)$. Thus,
$\mathrm{mad}(H^{\prime})\geq
2|E(H^{\prime})|/|V(H^{\prime})|=4b/(a+b)>2a(n-1)/(a(n-1)/2+a)=2a(n-1)/(a(n+1)/2)=4(n-1)/(n+1)=4-8/(n+1)$.

We next show that the construction $K_{n}^{*}$ in Lemma 5 is nearly sharp.

######  Theorem 1.

Fix $\epsilon$ such that $0<\epsilon\leq 8/5$. If $\mathrm{mad}(G)\leq
4-\epsilon$, then $\chi_{o}(G)\leq\lfloor 8/\epsilon\rfloor+2$. As
$\epsilon\to 0$, infinitely often there exists $G_{\epsilon}$ such that
$\mathrm{mad}(G_{\epsilon})=4-\epsilon$ and $\chi_{o}(G_{\epsilon})=\lfloor
8/\epsilon\rfloor-1$.

###### Proof.

The second statement follows directly from Corollary 6.

For the first statement, let $k:=\lfloor 8/\epsilon\rfloor+2$††margin:  $k$
and note that $k\geq 7$. Our proof is by induction on $|V(G)|$. The base case
is when $|V(G)|=1$, so $\chi_{o}(G)=1$. Instead assume $|V(G)|\geq 2$. If $G$
contains a 1-vertex $v$ with neighbor $w$, then $G-v$ has an odd $k$-coloring
$\varphi$ and we can extend $\varphi$ to $v$ by coloring $v$ to avoid
$\varphi(w)$ and $\varphi_{o}(w)$. If $G$ contains a 3-vertex $v$, then denote
$N(v)$ by $\\{w_{1},w_{2},w_{3}\\}$. Now $G-v$ has an odd $k$-coloring
$\varphi$ and we can extend $\varphi$ to $v$ by coloring $v$ to avoid
$\\{\varphi(w_{1}),\varphi(w_{2}),\varphi(w_{3}),\varphi_{o}(w_{1}),\varphi_{o}(w_{2}),\varphi_{o}(w_{3})\\}$.
So we assume that $G$ has neither 1-vertices nor 3-vertices. Suppose that $G$
has adjacent 2-vertices $v_{1}$ and $v_{2}$, and denote the remaining
neighbors of $v_{1}$ and $v_{2}$, respectively, by $v_{0}$ and $v_{3}$. Now
$G-\\{v_{1},v_{2}\\}$ has an odd $k$-coloring $\varphi$. To extend this to
$v_{1}$ and $v_{2}$, we first color $v_{1}$ to avoid
$\\{\varphi(v_{0}),\varphi_{o}(v_{0}),\varphi(v_{3})\\}$ and then color
$v_{2}$ to avoid the new color on $v_{1}$ as well as
$\\{\varphi(v_{0}),\varphi(v_{3}),\varphi_{o}(v_{3})\\}$.

Since $\mathrm{mad}(G)<4$, we know that $\delta(G)=2$. We use discharging to
show that some vertex $v$ with $d(v)\leq 8/\epsilon-2$ has “many” 2-neighbors.
Similar to the case of adjacent 2-vertices above, we will delete $v$ and its
2-neighbors, find an odd $k$-coloring $\varphi$ for this smaller graph, and
extend $\varphi$ to all of $G$. Let $x:=1-\epsilon/2$††margin:  $x$ . We give
each vertex $v$ initial charge $d(v)$ and use the following single discharging
rule: Each 2-vertex takes charge $x$ from each neighbor. Since $G$ does not
have adjacent 2-vertices, each 2-vertex finishes with charge
$2+2x=4-\epsilon$. For each $4^{+}$-vertex $v$, let _$d_{2}(v)$_ ††margin:
$d_{2}(v)$ denote the number of 2-neighbors of $v$. Now $v$ finishes with
charge $d(v)-xd_{2}(v)$. If $d(v)-xd_{2}(v)>2+2x=4-\epsilon$ for each $v$,
then we contradict the assumption $\mathrm{mad}(G)\leq 4-\epsilon$. So there
exists $v$ such that $d(v)-xd_{2}(v)\leq 2+2x$.

Form $G^{\prime}$ from $G$ by deleting $v$ and all of its 2-neighbors. By
induction, $G^{\prime}$ has an odd $k$-coloring $\varphi$. To extend $\varphi$
to $G$, we first color $v$ to avoid the colors on the colored neighbors (in
$G$) of its deleted 2-neighbors (in $G^{\prime}$) as well as, for each
$4^{+}$-neighbor $w$, to avoid $\varphi(w)$ and $\varphi_{o}(w)$. For
convenience, we denote this color used on $v$ by $\varphi(v)$. Then we color
each 2-neighbor $x$ of $v$, with other neighbor $y$, to avoid
$\\{\varphi(v),\varphi_{o}(v),\varphi(y),\varphi_{o}(y)\\}$. This gives an odd
coloring $\varphi^{\prime}$ of $G$. We must only show that $\varphi^{\prime}$
uses at most $k$ colors. In total, $v$ must avoid at most $2d(v)-d_{2}(v)$
colors. So it will suffice to show that $k\geq 1+(2d(v)-d_{2}(v))$. Note that
$1+2d(v)-d_{2}(v)<1+d(v)+(d(v)-xd_{2}(v))\leq 1+d(v)+2+2x<1+d(v)+4$. Since
$1+2d(v)-d_{2}(v)$ is an integer, $1+2d(v)-d_{2}(v)\leq d(v)+4$. So now we
must bound $d(v)$. Clearly, $d(v)-d(v)x\leq d(v)-d_{2}(v)x\leq 2+2x$. So
$d(v)\leq(2+2x)/(1-x)=(4-\epsilon)/(\epsilon/2)=8/\epsilon-2$. Since $d(v)$ is
an integer, $d(v)\leq\lfloor 8/\epsilon\rfloor-2$. Thus, $d(v)+4\leq(\lfloor
8/\epsilon\rfloor-2)+4=\lfloor 8/\epsilon\rfloor+2=k$. ∎

######  Remark 8.

In the previous proof we handled adjacent 2-vertices as follows. “Suppose that
$G$ has adjacent 2-vertices $v_{1}$ and $v_{2}$, and denote the remaining
neighbors of $v_{1}$ and $v_{2}$, respectively, by $v_{0}$ and $v_{3}$. Now
$G-\\{v_{1},v_{2}\\}$ has an odd $k$-coloring $\varphi$. To extend this to
$v_{1}$ and $v_{2}$, we first color $v_{1}$ to avoid
$\\{\varphi(v_{0}),\varphi_{o}(v_{0}),\varphi(v_{3})\\}$ and then color
$v_{2}$ to avoid the new color on $v_{1}$ as well as
$\\{\varphi(v_{0}),\varphi(v_{3}),\varphi_{o}(v_{3})\\}$.” In this argument we
implicitly assumed that $v_{3}\neq v_{0}$. Otherwise, our choice for color on
$v_{1}$ might create a problem for $v_{3}$. Specifically, suppose that $v_{0}$
is adjacent to 2-vertices $v_{1}$ and $v_{2}$, which are also adjacent to each
other, and that colors 1 and 2 each appear once on $N(v)$ under $\varphi$ (and
no other color appears an odd number of times); this is possible when
$v_{3}=v_{0}$. Now $\varphi_{o}(v_{0})$ is undefined. But if we are careless
and color $v_{1}$ with 1 and color $v_{2}$ with 2, then we create a problem
for $v_{0}$. This obstacle has an easy work-around. Rather than defining
$\varphi_{o}(v_{0})$ relative to the coloring $\varphi$, we define it relative
to the _current coloring_ , including any vertices that were deleted but are
now already colored. For brevity, we omit mention of this issue throughout the
paper, since the solution above always works.

It is natural to consider a list-coloring analogue of odd coloring (although
we omit a formal definition). We note that, with minor modifications, the
proof of Theorem 1 works equally well in the context of odd list-coloring and
even in the context of odd correspondence coloring. The same is true for the
proofs of Theorem 2(a) and Theorem 2(b).

We suspect that the construction in Lemma 5 is sharp.

######  Conjecture 1.

Fix $\epsilon$ such that $0<\epsilon\leq 8/5$. If $\mathrm{mad}(G)\leq
4-\epsilon$, then $\chi_{o}(G)\leq\lfloor 8/\epsilon\rfloor-1$.

Conjecture 1 cannot be extended to allow $\epsilon=2$, since
$\mathrm{mad}(C_{3s+1})=2$, but $\chi_{o}(C_{3s+1})=4$, for each positive
integer $s$. In contrast, when $\epsilon=1$ and $\epsilon=8/7$, we prove the
conjecture in a stronger form. We show that if $\mathrm{mad}(G)\leq
4-\epsilon$, then $\chi_{o}(G)\leq\lfloor 8/\epsilon\rfloor-2$ unless $G$
contains as a subgraph $K^{*}_{s}$, where $s:=\lfloor 8/\epsilon\rfloor-1$. We
present these proofs in Sections 3 and 4.

Recall that a graph $H$ is _$k$ -critical_††margin:  $k$-critical if
$\chi(H)=k$ and $\chi(H-e)<k$ for every edge $e\in E(H)$. Analogously, a graph
$H$ is _odd- $k$-critical_††margin:  odd-$k$-critical if $\chi_{o}(H)=k$ and
$\chi_{o}(H-e)<k$ for every edge $e\in E(H)$. The latter notion is more
subtle111An interesting example is $C_{5}$, since $\chi_{o}(C_{5})=5$, but
$C_{5}$ has no odd-4-critical subgraph., since possibly $H^{\prime}$ is a
subgraph of $H$, but $\chi_{o}(H^{\prime})>\chi_{o}(H)$. More concretely, if
we form $H$ from $K^{*}_{n}$ with $n\geq 3$ by adding a leaf adjacent to each
vertex, then $\chi_{o}(H)\leq 3$, even though $\chi_{o}(K^{*}_{n})=n$. It is
easy to check that subdividing every edge of a $k$-critical graph, with $k\geq
6$, yields an odd-$k$-critical graph. Kostochka and Yancey [10, 11] showed
that the sparsest $k$-critical graphs are so-called $k$-Ore graphs. For each
$k\geq 6$, by subdividing all edges in $k$-Ore graphs, we get an infinite
family of odd-$k$-critical graphs with maximum average degrees slightly larger
than $4-8/(k+3)$. We suspect that in the limit no infinite family of
odd-$k$-critical graphs has smaller maximum average degree.

##  3 Odd 6-Colorings

The goal of this section is to prove the following result.

######  Theorem 2(a).

If $\mathrm{mad}(G)<3$, then $\chi_{o}(G)\leq 6$. This includes all planar $G$
of girth at least 6.

Note that Theorem Theorem 2(a) is sharp in two senses. First,
$\mathrm{mad}(K_{6}^{*})=4-8/(6+1)=2+6/7$ and $\chi_{o}(K_{6}^{*})=6$, so the
upper bound of 6 cannot be decreased. Second,
$\mathrm{mad}(K_{7}^{*})=4-8/(7+1)=3$ and $\chi_{o}(K_{7}^{*})=7$, so the
hypothesis $\mathrm{mad}(G)<3$ cannot be weakened at all.

###### Proof.

The second statement follows from the first by Proposition 4. So we prove the
first. Assume the statement is false, and $G$ is a counterexample with as few
vertices as possible. As in the proof of Theorem 1, we assume $G$ has no
1-vertex and $G$ has no adjacent 2-vertices. Suppose $G$ has a 3-vertex $v$
with neighbors $w_{1},w_{2},w_{3}$, where $d(w_{1})=2$. Denote the other
neighbor of $w_{1}$ by $x_{1}$. Let $G^{\prime}:=G-\\{v,w_{1}\\}$. By
minimality, $G^{\prime}$ has an odd 6-coloring $\varphi$. To extend $\varphi$
to $G$, we color $v$ to avoid
$\\{\varphi(w_{1}),\varphi(w_{2}),\varphi(w_{3}),\varphi_{o}(w_{2}),\varphi_{o}(w_{3})\\}$
and then color $w_{1}$ to avoid the new color on $v$ and also to avoid
$\\{\varphi(x_{1}),\varphi_{o}(x_{1})\\}$. Thus, no 3-vertex has a 2-neighbor.

Suppose $G$ has a 4-vertex with neighbors $w_{1},w_{2},w_{3},w_{4}$, where
$d(w_{1})=d(w_{2})=d(w_{3})=2$. For each $i\in\\{1,2,3\\}$, denote the other
neighbor of $w_{i}$ by $x_{i}$. Let $G^{\prime}:=G-\\{v,w_{1},w_{2},w_{3}\\}$.
By minimality, $G^{\prime}$ has an odd 6-coloring $\varphi$. To extend
$\varphi$ to $G$, color $v$ to avoid
$\\{\varphi(x_{1}),\varphi(x_{2}),\varphi(x_{3})$,
$\varphi(w_{4}),\varphi_{o}(w_{4})\\}$ and then color each $w_{i}$ to avoid
the new color on $v$ and also avoid $\\{\varphi(x_{i})$,
$\varphi_{o}(x_{i}),\varphi(w_{4})\\}$. Thus, no 4-vertex in $G$ has three (or
more) 2-neighbors.

Suppose $G$ has a 5-vertex $v$ with five 2-neighbors
$w_{1},w_{2},w_{3},w_{4},w_{5}$. For each $i\in\\{1,\ldots,5\\}$, denote the
other neighbor of $w_{i}$ by $x_{i}$. Let
$G^{\prime}:=G-\\{v,w_{1},w_{2},w_{3},w_{4},w_{5}\\}$. By minimality,
$G^{\prime}$ has an odd 6-coloring $\varphi$. To extend $\varphi$ to $G$, we
color $v$ to avoid
$\\{\varphi(x_{1}),\varphi(x_{2}),\varphi(x_{3}),\varphi(x_{4}),\varphi(x_{5})\\}$.
We then color each $w_{i}$ to avoid the new color on $v$, as well as
$\\{\varphi(x_{i}),\varphi_{o}(x_{i}),\varphi(v)\\}$. Thus, no 5-vertex in $G$
has five 2-neighbors.

Now we use discharging to reach a contradiction, which will finish the proof.
We give each vertex $v$ initial charge $d(v)$ and use the following single
discharging rule: Each 2-vertex takes $1/2$ from each neighbor. We show that
each vertex finishes with charge at least 3, which contradicts the hypothesis
$\mathrm{mad}(G)<3$. Recall that $\delta(G)\geq 2$.

If $d(v)=2$, then $v$ finishes with $2+2(1/2)=3$. If $d(v)=3$, then $v$ has no
2-neighbors, so $v$ finishes with 3. If $d(v)=4$, then $v$ has at most two
2-neighbors, so $v$ finishes with at least $4-2(1/2)=3$. If $d(v)=5$, then $v$
has at most four 2-neighbors, so $v$ finishes with at least $5-4(1/2)=3$. If
$d(v)\geq 6$, then $v$ finishes with at least $d(v)-d(v)/2=d(v)/2\geq 3$,
since $d(v)\geq 6$. This finishes the proof. ∎

With a bit more analysis, we can prove the following stronger result.

######  Corollary 9.

If $\mathrm{mad}(G)\leq 3$ and $G$ does not contain $K^{*}_{7}$ as a subgraph,
then $\chi_{o}(G)\leq 6$.

###### Proof.

In the proof of Theorem Theorem 2(a), to contradict the hypothesis
$\mathrm{mad}(G)<3$, we showed that each vertex finished with charge at least
3. To contradict the weaker hypothesis $\mathrm{mad}(G)\leq 3$, it suffices to
show that also some vertex finishes with charge more than 3. Suppose the
contrary.

Now $G$ has no $7^{+}$-vertex and each 6-vertex has six 2-neighbors. Each
5-vertex has exactly four 2-neighbors and each 4-vertex has exactly two
2-neighbors. Now it is straightforward to check that $G$ cannot have any two
adjacent $3^{+}$-vertices $v$ and $w$; in each case, we delete $v$, $w$, and
their 2-neighbors, color the smaller graph and extend. Thus, $G$ is bipartite,
where one part consists of 2-vertices and the other consists of 6-vertices.
Form $G^{\prime}$ from $G$ by contracting one edge incident to each 2-vertex.
Now $G^{\prime}$ is 6-regular, but no component is $K_{7}$, so
$\chi(G^{\prime})\leq 6$ by Brooks’ Theorem. A 6-coloring of $G^{\prime}$
induces a 6-coloring of the 6-vertices in $G$, which we can easily extend to
an odd 6-coloring of $G$. ∎

##  4 Odd 5-Colorings

The goal of this section is to prove the following result.

######  Theorem 2(b).

If $\mathrm{mad}(G)<20/7$, then $\chi_{o}(G)\leq 5$. This includes all planar
$G$ of girth at least 7.

###### Proof.

The second statement follows from the first by Proposition 4. So we prove the
first. Assume the statement is false, and $G$ is a counterexample with as few
vertices as possible. As in the proof of Theorem 1, we assume $G$ has no
1-vertex and $G$ has no adjacent 2-vertices. Suppose $G$ has a 3-vertex $v$
with neighbors $w_{1},w_{2},w_{3}$, where $d(w_{1})=d(w_{2})=2$. Denote the
other neighbors of $w_{1}$ and $w_{2}$ by, respectively, $x_{1}$ and $x_{2}$.
Let $G^{\prime}:=G-\\{v,w_{1},w_{2}\\}$. By minimality, $G^{\prime}$ has an
odd 5-coloring $\varphi$. To extend $\varphi$ to $G$, we color $v$ to avoid
$\\{\varphi(w_{1}),\varphi(w_{2}),\varphi(w_{3}),\varphi_{o}(w_{3})\\}$ and
color each $w_{i}$ to avoid the new color on $v$ and avoid
$\\{\varphi(x_{i}),\varphi_{o}(x_{i}),\varphi(w_{3})\\}$. Thus, each 3-vertex
has at most one 2-neighbor. More generally, each 3-vertex has at most one
$3^{-}$-neighbor. If not, then we delete $v$ and any 2-neighbors. We color $v$
to avoid the color on each 3-neighbor, the color on the colored neighbor of
each (deleted) 2-neighbor, as well as $\\{\varphi(w),\varphi_{o}(w)\\}$, where
$w$ is the third neighbor of $v$. Thus, each 3-vertex has at most one
$3^{-}$-neighbor.

Suppose $G$ has a 4-vertex with four 2-neighbors $w_{1},w_{2},w_{3},w_{4}$.
For each $i\in\\{1,2,3,4\\}$, denote the other neighbor of $w_{i}$ by $x_{i}$.
Let $G^{\prime}:=G-\\{v,w_{1},w_{2},w_{3},w_{4}\\}$. By minimality,
$G^{\prime}$ has an odd 5-coloring $\varphi$. To extend $\varphi$ to $G$,
color $v$ to avoid $\\{\varphi(x_{1}),\varphi(x_{2}),\varphi(x_{3})$,
$\varphi(x_{4})\\}$ and then color each $w_{i}$, in succession, to avoid the
new color on $v$ and also avoid $\\{\varphi(x_{i})$,
$\varphi_{o}(x_{i}),\varphi_{o}(v)\\}$. Thus, no 4-vertex in $G$ has four
2-neighbors. Similarly, if each $w_{i}$ has degree at most 3 and at least one
$w_{i}$ is a 2-vertex, then we form $G^{\prime}$ from $G$ by deleting $v$ and
all its 2-neighbors. Again $G^{\prime}$ has an odd 5-coloring $\varphi$. We
extend $\varphi$ to $v$ by avoiding the color on each 3-neighbor and the color
on the other neighbor of each 2-neighbor. Finally, we can extend the coloring
to all 2-neighbors to get an odd 5-coloring of $G$. Thus, $G$ has no 4-vertex
with at least one 2-neighbor and all $3^{-}$-neighbors. Similarly, $G$ does
not contain adjacent 4-vertices, $v$ and $w$, each with three 2-neighbors. If
so, then $G-(N[v]\cup N[w])$ has an odd 5-coloring. We color $v$ and $w$ with
distinct colors that each differ from the colors on the three colored vertices
at distance two in $G$. Again, we can extend this coloring to an odd
5-coloring of $G$.

Now we use discharging to reach a contradiction, which will finish the proof.
We give each vertex $v$ initial charge $d(v)$ and use the following two
discharging rules.

  1. (R1)

Each 2-vertex takes $3/7$ from each neighbor.

  2. (R2)

Each 3-vertex with a 2-neighbor and each 4-vertex with three 2-neighbors takes
$1/7$ from each $3^{+}$-neighbor.

We show that each vertex finishes with charge at least 20/7, which contradicts
the hypothesis $\mathrm{mad}(G)<20/7$. Recall that $\delta(G)\geq 2$. If
$d(v)=2$, then $v$ finishes with $2+2(3/7)=20/7$. If $d(v)=3$, then $v$ has at
most one 2-neighbor. Further, $v$ does not give away charge by (R2), since no
3-vertex has both a 2-neighbor and a 3-neighbor, and also no 4-vertex has both
three 2-neighbors and a 3-neighbor. So, if $v$ has a 2-neighbor, then it has
two $4^{+}$-neighbors and receives charge $1/7$ from each. Thus, $v$ finishes
with at least $3-3/7+2(1/7)=20/7$. If $v$ has no 2-neighbor, then $v$ starts
and finishes with 3.

Let $v$ be a 4-vertex, and recall that $v$ has at most three 2-neighbors. If
$v$ has at most two 2-neighbors, then $v$ finishes with at least
$4-2(3/7)-2(1/7)=20/7$. If $v$ has three 2-neighbors, then its fourth neighbor
is a $4^{+}$-neighbor that does not receive charge from $v$ by (R2) but rather
gives $v$ charge $1/7$ by (R2). So $v$ finishes with $4-3(3/7)+1/7=20/7$.

If $v$ is a $5^{+}$-vertex, then $v$ finishes with at least
$d(v)-3d(v)/7=4d(v)/7\geq 20/7$, since $d(v)\geq 5$. This finishes the proof.
∎

With a bit more analysis, we can prove the following stronger result. The
proof is similar to that of Corollary 9, so we just provide a sketch.

######  Corollary 10.

If $\mathrm{mad}(G)\leq 20/7$ and $G$ does not contain $K^{*}_{6}$ as a
subgraph, then $\chi_{o}(G)\leq 5$.

###### Proof Sketch..

Assume $G$ is a counterexample. So $G$ has no $6^{+}$-vertices and each
5-vertex in $G$ has five 2-neighbors. Each 3-vertex has a single 2-neighbor.
Each 4-vertex either has exactly three 2-neighbors or has exactly two
2-neighbors and gives charge 1/7 to each of it $3^{+}$-neighbors. In this
case, we delete $v$, its 4-neighbors and the 2-neighbors of all deleted
4-vertices. This smaller graph has an odd 5-coloring $\varphi$, and it is
straightforward to check that we can extend $\varphi$ to $G$. So $G$ has no
4-vertices. This implies, in turn, that $G$ has no 3-vertices, since $G$ has
no 3-vertex with two $3^{-}$-neighbors. So $G$ is bipartite with vertices in
one part of degree 2 and those in the other part of degree 5. We contract one
edge incident to each 2-vertex, and 5-color the resulting graph by Brooks’
Theorem. Finally, we extend this 5-coloring to an odd 5-coloring of $G$. ∎

## References

  * [1] D. P. Bunde, K. Milans, D. B. West, and H. Wu.  Parity and strong parity edge-coloring of graphs.  In Proceedings of the Thirty-Eighth Southeastern International Conference on Combinatorics, Graph Theory and Computing, volume 187, pages 193–213, 2007.
  * [2] D. P. Bunde, K. Milans, D. B. West, and H. Wu.  Optimal strong parity edge-coloring of complete graphs.  Combinatorica, 28(6):625–632, 2008.
  * [3] P. Cheilaris.  Conflict-Free Coloring.  2009\.  Thesis (Ph.D.)–City University of New York.
  * [4] P. Cheilaris, B. Keszegh, and D. Pálvölgyi.  Unique-maximum and conflict-free coloring for hypergraphs and tree graphs.  SIAM J. Discrete Math., 27(4):1775–1787, 2013.
  * [5] P. Cheilaris and G. Tóth.  Graph unique-maximum and conflict-free colorings.  J. Discrete Algorithms, 9(3):241–251, 2011.
  * [6] G. Even, Z. Lotker, D. Ron, and S. Smorodinsky.  Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks.  SIAM J. Comput., 33(1):94–136, 2003.
  * [7] I. Fabrici and F. Göring.  Unique-maximum coloring of plane graphs.  Discuss. Math. Graph Theory, 36(1):95–102, 2016.
  * [8] R. Glebov, T. Szabó, and G. Tardos.  Conflict-free colouring of graphs.  Combin. Probab. Comput., 23(3):434–448, 2014.
  * [9] A. Kostochka, M. Kumbhat, and T. Łuczak.  Conflict-free colourings of uniform hypergraphs with few edges.  Combin. Probab. Comput., 21(4):611–622, 2012.
  * [10] A. Kostochka and M. Yancey.  Ore’s conjecture on color-critical graphs is almost true.  J. Combin. Theory Ser. B, 109:73–101, 2014.
  * [11] A. Kostochka and M. Yancey.  A Brooks-type result for sparse critical graphs.  Combinatorica, 38(4):887–934, 2018.
  * [12] J. Pach and G. Tardos.  Conflict-free colourings of graphs and hypergraphs.  Combin. Probab. Comput., 18(5):819–834, 2009.
  * [13] M. Petruševski and R. Škrekovski.  Colorings with neighborhood parity condition.  Dec. 2021, arXiv:2112.13710.
  * [14] S. Smorodinsky.  Conflict-free coloring and its applications.  In Geometry---intuitive, discrete, and convex, volume 24 of Bolyai Soc. Math. Stud., pages 331--389. János Bolyai Math. Soc., Budapest, 2013.