[]Sarthak Das []Kuan Eng Johnson Goh

]Institute of Materials Research and Engineering (IMRE), Agency for Science,
Technology and Research (A*STAR), Singapore, 138634, Republic of Singapore

# Electrical control of valley polarized charged biexcitons in monolayer WS2

<EMAIL_ADDRESS>Ding Huang  Ivan Verzhbitskiy  Zi-En Ooi  Chit Siong
Lau  Rainer Lee  Calvin Pei Yu Wong  *<EMAIL_ADDRESS>[

###### Abstract

Excitons are key to the optoelectronic applications of van der Waals
semiconductors with the potential for versatile on-demand tuning of
properties. Yet, their electrical manipulation is complicated by their
inherent charge neutrality and the additional loss channels induced by
electrical doping. We demonstrate the dynamic control of valley polarization
in charged biexciton (quinton) states of monolayer tungsten disulfide,
achieving up to a sixfold increase in the degree of circular polarization
under off-resonant excitation. In contrast to the weak direct tuning of
excitons typically observed using electrical gating, the quinton
photoluminescence remains stable, even with increased scattering from electron
doping. By exciting at the exciton resonances, we observed the reproducible
non-monotonic switching of the charged state population as the electron doping
is varied under gate bias, indicating a coherent interplay between neutral and
charged exciton states.

###### keywords:

valley polarization, trion and quinton, motional narrowing, exchange
interaction, resonant excitation, coherent coupling.

## Introduction

Excitons in monolayer transition metal dichalcogenides (TMDs) have high
binding energy [1, 2, 3], enabling strong resonances even at room temperature.
This makes TMDs highly attractive for a wide range of applications in
optoelectronics [4, 5, 6, 7] and quantum technologies [8, 9, 10].
Particularly, the valley-dependent optical selection rules in monolayer TMDs,
due to the presence of two inequivalent valleys with spin–valley locking and a
direct bandgap, allow high degree of optical control over valley polarizations
[11, 12, 13, 14] and valley coherence [15, 16].

Although neutral excitons can host highly polarized optical states [11, 12,
13, 14, 15, 16], their charge neutrality makes excitons insensitive to
electrical bias, limiting the on-demand control of excitonic properties, such
as the resonance energies, radiative and non-radiative lifetimes, and
photoluminescence (PL) brightness. Moreover, these states are susceptible to
environmental noise, which can result in a loss of quantum information. The
challenges are further exacerbated by interactions with charges, spins,
disorders, and thermal excitations. As a result, an electrically controlled,
valley-polarized photon source remains unfulfilled.

Earlier studies have shown that the modulation of valley polarization of
neutral and charged states can be implemented with gate voltage [17, 18],
temperature [18], screening [19], strain [20] or magnetic field [21] but
simultaneous electrical control along with the polarized photon yield remains
a challenge. Moreover, the majority of the strategies implemented to achieve
external control with valley-polarized excitons compromise the photon yield
due to different non-radiative losses. To address the limitations of neutral
exciton and explore valley-polarized charge states, we utilize optically
generated valley-polarized emission from the charged states, controlled via
electrical injection.

In addition to the excitons, the monolayer TMDs can host a nexus of many-body
quasiparticles such as three-particle charged excitons or trions [22, 23, 24,
25, 26, 27], four-particle biexciton [28, 29, 30], five-particle charged
biexcitons or quintons [31, 32, 33, 34, 35, 36, 37, 38, 39] and even higher
many body species [40, 41]. The experimental observation of all these multi-
particle complex states has its genesis in the high binding energy of the
underlying excitons.

In the presence of free carriers, neutral excitons can capture additional
carriers to form charged excitons. While these charged species are
electrically controllable, it is important to ascertain that they still
preserve the spin-valley coupling characteristics (shown by valley
polarization). Here, we demonstrate dynamic control over electrically tuneable
steady-state valley polarization, effectively preserving valley information in
the presence of enhanced scattering. By resonantly exciting excitons, we can
achieve a controlled generation of charged states, wherein multi-particle
excitonic quasiparticles become coherently coupled to excitons. Investigating
the coherent coupling between neutral and charged states through gate-
dependent photoluminescence spectroscopy under excitonic resonance reveals
potential mechanisms to control the quantum states further.

Harnessing valley selective carrier populations from helicity-controlled
excitations holds immense potential for generating, storing, processing, and
transmitting information based on valley state. The TMD is advantageous due to
its ability to leverage both optical (direct bandgap) and electronic (quasi-
particle bandgap with strong spin-orbit interactions) benefits. In addition,
the electronic degree of freedom allows for ease of control and integration
with conventional electronic systems. However, the robust electrical control
of a valley state via quinton species has not yet been demonstrated. For the
charged excitonic species, we demonstrate that valley polarization can be
electrically switched between high- and low-polarized states along with its
dynamic modulation. This marks a significant step towards achieving practical
applications of valleytronic devices. We discuss the implications of these
findings in the context of coherent control of charged excitons where the
charged exciton population can be controlled with neutral exciton resonance
along with the retention of valley polarization. Our findings not only shed
light on the manipulation of valley-polarized charge states in monolayer TMDs
but also underline their potential as robust platforms for preserving quantum
information in the presence of various environmental disturbances.

## Results and Discussions

Our sample consists of a monolayer of tungsten disulfide (1L WS2) sandwiched
between two hexagonal Boron Nitride ($h$BN) layers. A graphite layer
underneath the bottom $h$BN layer serves as a back gate electrode (figure 1a).
The 1L WS2 is connected to an electrode via another graphite layer (see
Supporting Information S1 and Methods for further details). Just as a bright
exciton in WS2 can capture an electron and form intra- or inter-valley trions
(singlet $T_{s}$ or triplet $T_{t}$ trion), a dark exciton can also form dark
trion states ($T_{D}$) [26, 27]. Also, due to the presence of the lowest
energy dark states in WS2, the bright exciton can combine with $T_{D}$ to form
a five-particle quinton (or charged biexciton state, $Q$) [33, 34, 42]. The
different configurations of the energy states are schematically presented in
figure 1b. The low temperature ($T$ = 4.6 K) micro-photoluminescence ($\mu$PL)
spectra from the sample are presented in figure 1c with $\lambda_{exc}$ = 570
nm excitation (above optical bandgap, non-resonant) and back gate voltage
$V_{g}$ = 0 V. The different energy states are extracted from the Lorentz fit
and highlighted as exciton ($X$ at 596 nm or $\sim$ 2.078 eV), trion ($T$ at
606 nm or $\sim$ 2.044 eV), quinton ($Q$ at 614 nm or $\sim$ 2.019 eV) and
dark trion ($T_{D}$ at 618 nm or $\sim$ 2.006 eV) based on their energy
position according to the previous reports [27, 43, 44]. Further experimental
observations in support of the peak assignments are provided in Supporting
Information S2.

The exciton population primarily governs the population of the coupled
excitonic quasi-particles. Further, the exciton population can be controlled
efficiently by resonant ($\lambda_{exc}$ = 596 nm) vs non-resonant excitation.
Figure 1d shows a 2D color map of PL excitation (PLE) spectra measured near
the neutral exciton resonance ($\sim$ 596 nm, horizontal dashed line) at
$V_{g}$ = 0 V. At excitation energies higher than the neutral exciton
emission, the spectra reflect an off-resonant regime where the PL emission of
$T$ and $Q$ peaks is low due to fast non-radiative recombination processes
[38]. However, as the excitation energy approaches the exciton resonance
($E_{X}$), PL peaks of the individual energy states get stronger while the
width is reduced (see the Supporting Information S3). The peak intensity
reaches the maximum at the neutral exciton resonance (596 nm at $V_{g}$ = 0
V), then decreases due to sub-bandgap optical excitation. The red (yellow)
vertical dashed lines follow the $T$ ($Q$) energy states. Figure 1e shows the
normalized intensity profile at $T$ and $Q$ resonances as a function of
excitation energy, highlighting the PL enhancement of the charged excitons (at
the $X$ resonance shown by the black dashed line) due to efficient down-
conversion from the resonantly formed neutral excitons. The Lorentzian profile
broadening along the resonance energy gives an estimation of the intrinsic
linewidth corresponding to the multi-particle complex states. This also
denotes the efficient coupling between the neutral and charged states [25,
45]. Figure 1f represents the horizontal line cut from figure 1d at exciton
resonance with $\lambda_{exc}$ = 596 nm. The solid vertical line denotes the
excitation wavelength at 596 nm, while the dashed vertical line represents the
edge of the cut-off filter for reference (see the Methods section for further
details). The different energy states ($T_{t}$, $T_{s}$, and $Q$) below the
$X$ state are well identified for resonant excitation at $X$.

When an external DC bias is applied to the monolayer via the back gate, as we
can observe in figures 2a-b, the energy states exhibit a shift in energy
position, change in intensity, and variation in the valley polarization as
reported in other works [33, 42, 38]. The two-dimensional colorplot for gate-
dependent PL spectra for non-resonant excitation ($\lambda_{exc}$ = 570 nm) is
presented in the upper panel of figure 2a. The representative spectra and
fittings are shown in Supporting Information S4. Due to the optical
selectivity and unique spin-valley configuration, the right (left) circularly-
polarized light can selectively address the $K(K^{\prime})$ valley in 1L WS2.
Here, the PL intensity is recorded for both the co-($\sigma^{+}$ excitation
and $\sigma^{+}$ detection, $\sigma^{+}/\sigma^{+}$) and cross-polarized
($\sigma^{+}$ excitation and $\sigma^{-}$ detection, $\sigma^{+}/\sigma^{-}$)
modes (see Methods section for further details). The intensity mapping
presented in figure 2a is for the co-polarized mode, while the cross-polarized
spectra are shown in Supporting Information S5. The corresponding degree of
circular polarization ($\mathcal{P_{C}}$) in steady-state can be obtained from
the relation:

$\mathcal{P_{C}}=\frac{I_{co}-I_{cross}}{I_{co}+I_{cross}}$ (1)

where $I_{co/cross}$ denotes the intensity of the co- or cross-polarized PL.
All the energy states discussed above show a distinct polarization upon
circularly polarized light excitation. The bottom panel in 2a, shows the color
plot of $\mathcal{P_{C}}$ as a function of applied $V_{g}$. The peak positions
of the individual energy states are extracted from the individual peak
fittings and plotted in figure 2b. We observe three regions with distinct
behaviors as follows:

(i) For $V_{g}<0$, the individual energy state’s position and corresponding
intensity remain unaltered. The charged excitonic complex states are highly
sensitive to doping. However, due to the relative band alignment between 1L
WS2 and graphite, it is difficult to inject holes into the WS2 [46, 47].
Hence, the exciton and other excitonic complexes undergo negligible modulation
while $V_{g}$ is negative.

(ii) At small positive $V_{g}$, the electrons are injected into the system.
These free electrons are captured by the optically created neutral excitons
($X$) and thus form three-particle negatively charged exciton ($T$) or five-
particle quintons ($Q$, charged biexciton). Also, in this process, neutral
excitons transfer their oscillator strength to the charged species. As a
result, the intensities of the $T$ and $Q$ states start to increase (see
Supporting Information S5) while the $X$ intensity fades away.

(iii) As doping increases further ($V_{g}>0$), the spectrum is dominated by
the five-particle $Q$ state. This is because the lowest energy state in 1L WS2
is dark [48, 49, 50], thus favoring the formation of $Q$ states rather than
$T$ states. This $Q$ state experiences monotonic enhancement of the intensity
and gradual red-shift due to Pauli blocking with the increasing $V_{g}$ [34,
42] (marked as $n_{++}$ in the figures 2a-b). The red shift of the $Q$ state
is almost linear over the experimental range, with a slope of $\sim$ 35 meV
per decade.

The $\mathcal{P_{C}}$ corresponding to the $Q$ state is presented in figure
2c. As shown in figures 2a-b, the energy states are not sensitive to the
external bias for the $V_{g}<0$ V region. This is also true for
$\mathcal{P_{C}}$. As the intensity of the $Q$ state grows with the number of
free electrons, the $\mathcal{P_{C}}$ of the Q state is modified non-
monotonically. As shown in figure 2c, $\mathcal{P_{C}}$ changes from $<$ 10%
to $>$ 60% at carrier density ($n$) of $\sim$ 4 $\times$ $10^{12}$ cm-2 (six-
fold enhancement) then gradually decreases and finally saturates at $\sim$ 30
% after $\sim$ 8 $\times$ $10^{12}$ cm-2. Earlier studies have shown that the
modulation of $\mathcal{P_{C}}$ of neutral ($X$) and charged ($T$) states can
be implemented with gate voltage [17, 18], temperature [18], screening [19],
strain [20] or magnetic field [21]. Importantly, the modulation of the neutral
states by electrostatic doping is limited to the low carrier density regime
only. Hence, the dynamic modulation of $\mathcal{P_{C}}$ in charged states is
of particular interest.

Since the $n$ doping is increasing linearly with the gate voltage, the non-
monotonic behavior of $\mathcal{P_{C}}$ can be understood as a product of
parallel contributions from different depolarization mechanisms. Here, the
non-monotonic behavior is explained using a combination of factors such as
long-range electron-hole exchange ($J^{LR}$), $V_{g}$-dependent dispersion of
quinton state in exciton momentum ($q$) space, and the corresponding momentum
scattering rate ($\gamma_{p}$). Recently, the Maialle-Silva-Sham (MSS)
mechanism caused by the intervalley electron-hole ($e–h$) exchange interaction
has been suggested to dominate the spin and valley relaxation in monolayers
[51, 16, 52, 19]. Here, the $J^{LR}(q)$ acts as a momentum-dependent effective
magnetic field where different multi-particle energy species with a different
center of mass (CoM) precess around the effective magnetic field with
different frequencies [13, 19]. The exchange-driven steady-state valley
polarization can be expressed as [52, 18]:

$\mathcal{P_{C}}=\frac{1}{1+\frac{J^{LR}(q)}{\hbar/\tau[\hbar/\tau+\hbar/\tau_{p}]}}$
(2)

Here $\tau$ refers to the radiative lifetime of the state, $\tau_{p}$ is the
depolarization related to momentum scattering, with $\frac{1}{\tau_{p}}$ =
$\gamma_{p}$ being the momentum scattering rate, while the intervalley
exchange interaction with CoM momentum is $q$, and $J^{LR}(q)$ reads as

$J^{LR}(q)=-|\psi(r_{e-h}=0)|^{2}(\frac{at}{E_{g}})^{2}V_{q}q^{2}e^{-2i\theta}$
(3)

where $|\psi(r_{e-h}=0)|^{2}$ is the overlap between electron and hole
wavefunction which is approximated by $1/{a^{2}_{B}}$, $a_{B}$ refers to the
Bohr radius, $a$ is lattice constant, $t$ is the hopping parameter, $E_{g}$ is
the electronic bandgap, and $V_{q}$ is the Coulomb potential defined by
$V_{q}=\frac{2\pi e^{2}}{\epsilon q}\frac{1}{1+r_{0}q}$, where $e$ is the
elementary charge, $\epsilon$ is the effective dielectric, and $r_{0}$ is the
fitting parameter.

For recombination of the neutral excitons, the radiative photon is confined
within a light cone due to the conservation of momentum, resulting in a small
kinetic energy. In contrast, the constraint on the recombination of charged
states is not as stringent, as the energy of the final state for recombination
of the charged state changes with $q$ [53, 42]. Thus, a recombination process
of charged states can also occur at different $q$ values. While the
recombination at $V_{g}$ $\approx$ 0 V is from the band edge $q=0$, the
recombination occurs at higher $q$ values when $V_{g}$ increases. Now, the
difference in effective mass between the five-particle $Q$ state and the
three-particle $T_{D}$ state results in pronounced kinetic energy. To conserve
energy and momentum, the emitted photon undergoes a redshift over the applied
voltage range as shown in figure 2d. The energy difference can be mapped from
the following relation:

$\Delta
E(V_{g})=\hbar\omega(V_{g})-\hbar\omega(V_{g}=0)=\frac{\hbar^{2}q^{2}}{2}[\frac{1}{M_{3}}-\frac{1}{M_{5}}]$
(4)

Here $M_{3}(M_{5})$ is the mass of the three-(five-) particle species, and
$\hbar\omega(V_{g})$ denotes the photon energy for given $V_{g}$. As the
carrier density or $n$ doping increases, the $J^{LR}(q)$ also increases due to
$q$-space dispersion. The $V_{g}$-dependent $J^{LR}(q)$ can be used in
equation 2 to match the experimental $\mathcal{P_{C}}$ value for a given
$\tau$. Further details on this are described in Supporting Information S6.
Assuming the radiative lifetime is constant across $n$, we can further extract
the momentum scattering rate ($\gamma_{p}$).

In figure 2e, $\gamma_{p}$ gradually increases with carrier density at the
low-doping regime and then saturates after $n$ reaches $\sim$ 4 $\times$
$10^{12}$ cm-2. If the $\tau$ of the charged state is constant over the
carrier density, we observe a strong variation in $\gamma_{p}$ for the charged
excitons, owing to their increased $q$-space dispersion. The initial increase
in momentum scattering leads to the enhancement of valley polarization
observed in figure 2c. Similar behavior was recently reported for monolayer
TMDs, where the spin/valley polarization of neutral exciton increases with an
increase in carrier density [13, 18], and this is attributed to the motional
narrowing effect [54, 55]. However, with higher doping, this effect vanishes
with enhanced kinetic energy and $J^{LR}(q)$ (see Supporting Information S6).
This is also reflected in the width reduction of the PL peaks at the low-
doping regime, as shown in the inset of figure 2c and Supporting Information
S5. Contrary to the almost constant, small value of the exchange interaction
for the neutral exciton, the $J^{LR}(q)$ of the charged states show pronounced
variation [16, 52, 18] with increasing $n$ as shown in figure 2f. Also, the
CoM momentum distribution of the $Q$ state across the carrier density,
extracted from the experimental red-shift of the peak position (from figure 2b
and equation 4) presented in the inset of figure 2f.

As discussed earlier, the formation of the charged states under resonance can
be controlled efficiently via coherent coupling between neutral and charged
excitons [23, 25, 56]. The neutral exciton population is more dominant with
resonant excitation, while the charged states population can be modulated via
external doping. Hence, changing the carrier density at the exciton resonance
opens up a channel to control the coupling parameters between neutral and
charged states. The 2D colorplot in figure 3a represents the PL for the lower
energy states relative to $X$ across the range of $V_{g}$ (see the Methods
section for further details). Here, the excitation energy is set to neutral
exciton resonance (596 nm). Unlike the non-resonant case, the intensity of the
$T$ and $Q$ charged quasi-particles excited at the exciton resonance exhibit a
non-monotonic gate dependence, as shown in figure 3b.

For $V_{g}<0$ V, we do not observe evidence of significant external doping in
figure 3a ($p$ doping is highly unlikely [46, 47]), and the Fermi level stays
within the bandgap. Hence, the exciton population remains unaltered throughout
this region (as shown in figure 3a). Also, since the excitation is exactly at
the excitation resonance, there is a scarcity of optically generated free
carriers. Thus, the charged excitons are formed either through defect-assisted
processes [57] or via photo-ionized carriers [58]. As a consequence, there is
no significant variation in the population of charged excitons, and their
total density remains relatively low.

At small positive gate voltages ($0<V_{g}<1$ V), we observe in figures 3a-b
that the population of free electrons starts to increase (denoted as $n$),
promoting the formation of charged $T$ and $Q$ species. The population of
charged excitons is further expected to be enhanced by the resonant condition
that assists the down-conversion of the neutral excitons [45]. The resonantly
formed excitons can now efficiently capture carriers and form multi-particle
states. In this regime, the coherent coupling between neutral and charged
excitons reaches the maximum, resulting in an order-of-magnitude increase of
the charged exciton densities. Under resonance, the net population density of
the charged states is a product of the exciton population (oscillator strength
of the neutral exciton) and the coupling parameter. As the doping increases
with increasing $V_{g}$, the exciton oscillator strength decreases, causing a
decrease in the population of coupled charged excitons, reaching its minimum
at $V_{g}=+2.5$ V (denoted as $n_{+}$ in figures 3a-b).

For $V_{g}>3$ V, where the system is electron-rich in figures 3a-b, the
steady-state population of the charged states is not coherently coupled. This
can further be confirmed by performing the PLE experiment similar to figure 1d
but in an electron-rich environment (shown in Supporting Information S7). As a
consequence, it grows with increasing doping, similar to non-resonant
excitation, as shown in figure 2a (denoted as $n_{++}$ region).

Here, the charged states are primarily dependent upon the neutral exciton
population, especially for the low-doping regime. This anomalous behavior of
the charged states population is a unique example of the doping dependence of
the coherent coupling between neutral and charged states. The above plausible
scenarios are schematically presented in figure 3c for four different regimes
($V_{g}<0$ V, and three $n$-doping regions marked as $n$, $n_{+}$ and $n_{++}$
are presented with different background colors). Resonant excitation persists
throughout the applied voltage and is shown via a red vertical arrow, and the
relatively weaker processes are denoted by the dashed curved arrows. The
intensity profile for the individual effects is demonstrated in the top panel
of Figure 3d, and the collective trend is depicted in the bottom panel of the
same figure (the color coding follows the same conventions as those in the
prior figure). The intensity modulation of charged states with the change in
gate voltage is due to the combination of the various processes described
above.

Similar to the non-resonant regime, the motional narrowing effect for valley
polarization of charged excitons persists with resonant excitation of neutral
species at low doping densities ($<$ 4$\times$1012 cm-2) (see discussions in
Supporting Information S8-S9). The efficient down-conversion from the neutral
to the charged states can be enhanced in the presence of resonant optical
phonons (Fröhlich interaction) [59]. Indeed, the energy difference between the
$X$ and $T$ states matches quite well with the vibrational phonon mode
($E_{2g}^{1}$ mode) of the monolayer WS2. Hence, the existence of phonon-
driven “virtual trion” is highly probable [60]. However, it has been reported
that only optical phonons are favorable for this efficient down-conversion,
and so the same argument does not hold for the efficient generation of the $Q$
state from the $X$ state resonance [61, 60]. While there is no optical phonon
with energy that can match the energy difference between $Q$ and $X$ excitons,
the down-conversion may result from interactions with overtones or a
combination of (optical and acoustic) phonon modes [62] (see Supporting
Information S11 for further details).

Finally, we show the repeatable voltage-dependent switching of the degree of
polarization for reconfigurable $Q$ states for up to 40 cycles. By altering
the $V_{g}$ polarity, the $P_{c}$ can be switched from the high polarized
state to a low polarized state as shown in figure 4a. To show the
reproducibility of our observations we have repeated all the operations in a
separate device D2 similarly fabricated (details are described in Supporting
Information S12). For a demonstration of stable switching control, we chose a
threshold of $<$ 10% for the low state and $>$ 40% for the high state, for
both the non-resonant and resonant excitation. Here, we record the average
$P_{c}$ with the statistical error over a selected voltage window primarily
within the $Q$ energy state over the cycles by altering the polarity of
$V_{g}$. The recorded $P_{c}$ of the second device shows stable switching in
either high or low-polarized states within measurement errors. The electrical
switching of valley polarization corresponding to the bright $Q$ states is
represented in figure 4b in the main text with quasi-resonant excitation,
while the same for the first device is shown in Supporting Information S13.

## Conclusion

In conclusion, our work demonstrates the ability to deterministically control
the valley-polarized emission from charged exciton states in monolayer TMDs
using an external electrical bias, thereby overcoming the limitations of
neutral excitons. Through careful selection of scattering mechanisms, we can
generate strong valley-polarised emission of a given chirality or suppress it
on demand. We also found that this polarization is resilient against
environmental noise fluctuations associated with our devices. By using
electrical bias, we can efficiently vary the exchange interaction and
scattering rates of charged states, accentuating the motional narrowing
effect, and yielding a deterministic valley-polarized emission from charged
states and simultaneously boasting remarkable optical brightness.
Specifically, we show electrical control over charged biexciton (quinton)
which thereby enabled the deterministic control of valley polarization in
monolayer WS2 devices where $P_{c}$ can be tuned from $<$ 10% up to $>$ 60%,
representing a 6-fold increase under electrical bias. The exquisite electrical
tunability of the spectral resonance of charged states promises coherent
control of valley polarization through the intricate interplay between the
charged and neutral exciton states, and the electrical control of coherent
valley polarization bodes well for exploiting the valley degree of freedom for
information storage and manipulation. This research represents a key step
towards advanced optoelectronic devices and opens up new possibilities for
applications such as valley-selective optical switching and valley-based
quantum technologies with enhanced stability and reliability.

Supplementary Information

This article contains supplementary information from S1 to S13.

Acknowledgments

We acknowledge the useful discussion with Prof. Goki Eda. We acknowledge the
funding support from the Agency for Science, Technology and Research #21709
and C230917006. D.H. acknowledges the funding support from A*STAR project
C222812022 and MTC YIRG M22K3c0105, C.S.L. acknowledges the funding support
from A*STAR under its MTC YIRG grant No. M21K3c0124 and C.P.Y.W. acknowledges
funding support from the A*STAR AME YIRG Grant No. A2084c0179.

Competing Interests

The authors declare no competing financial or non-financial interests.

Data Availability

Data is available on reasonable request from the corresponding author.

Author Contribution

S.D. and K.E.J.G. conceptualized the experiment. S.D. fabricated the device
with the help of R.L., C.S.L. and C.P.Y.W. and performed the experiments.
D.H., I.V. and Z.E.O. helped in optical measurements. S.D. conducted the data
analysis with inputs from D.H., I.V., and K.E.J.G. All authors contributed to
the manuscript writing.

## References

  * [1] Chernikov, A. _et al._ Exciton binding energy and nonhydrogenic Rydberg series in monolayer WS2.  _Physical review letters_ 113, 076802 (2014).
  * [2] Van Tuan, D., Yang, M. & Dery, H.  Coulomb interaction in monolayer transition-metal dichalcogenides.  _Physical Review B_ 98, 125308 (2018).
  * [3] Das, S., Gupta, G. & Majumdar, K.  Layer degree of freedom for excitons in transition metal dichalcogenides.  _Physical Review B_ 99, 165411 (2019).
  * [4] Xiao, D., Liu, G.-B., Feng, W., Xu, X. & Yao, W.  Coupled spin and valley physics in monolayers of MoS2 and other group-VI dichalcogenides.  _Physical review letters_ 108, 196802 (2012).
  * [5] Xu, X., Yao, W., Xiao, D. & Heinz, T. F.  Spin and pseudospins in layered transition metal dichalcogenides.  _Nature Physics_ 10, 343–350 (2014).
  * [6] Schaibley, J. R. _et al._ Valleytronics in 2D materials.  _Nature Reviews Materials_ 1, 1–15 (2016).
  * [7] Mak, K. F., Xiao, D. & Shan, J.  Light–valley interactions in 2D semiconductors.  _Nature Photonics_ 12, 451–460 (2018).
  * [8] Bussolotti, F. _et al._ Roadmap on finding chiral valleys: screening 2D materials for valleytronics.  _Nano Futures_ 2, 032001 (2018).
  * [9] Goh, K. E. J. _et al._ Toward valley-coupled spin qubits.  _Advanced Quantum Technologies_ 3, 1900123 (2020).
  * [10] Bussolotti, F., Das, S., Tong, W. & Goh, K. E. J.  Valley addressability and controllability.  In _Valleytronics in 2D Materials_ , 79–141 (World Scientific, 2023).
  * [11] Mak, K. F., He, K., Shan, J. & Heinz, T. F.  Control of valley polarization in monolayer MoS2 by optical helicity.  _Nature nanotechnology_ 7, 494–498 (2012).
  * [12] Yu, T. & Wu, M.  Valley depolarization due to intervalley and intravalley electron-hole exchange interactions in monolayer MoS2.  _Physical Review B_ 89, 205303 (2014).
  * [13] Yan, T., Qiao, X., Tan, P. & Zhang, X.  Valley depolarization in monolayer WSe2.  _Scientific reports_ 5, 15625 (2015).
  * [14] Yu, T. & Wu, M.  Valley depolarization dynamics and valley hall effect of excitons in monolayer and bilayer MoS2.  _Physical Review B_ 93, 045414 (2016).
  * [15] Yang, L. _et al._ Long-lived nanosecond spin relaxation and spin coherence of electrons in monolayer MoS2 and WS2.  _Nature Physics_ 11, 830–834 (2015).
  * [16] Hao, K. _et al._ Direct measurement of exciton valley coherence in monolayer WSe2.  _Nature Physics_ 12, 677–682 (2016).
  * [17] Shinokita, K. _et al._ Continuous control and enhancement of excitonic valley polarization in monolayer WSe2 by electrostatic doping.  _Advanced Functional Materials_ 29, 1900260 (2019).
  * [18] Wu, Y.-C., Taniguchi, T., Watanabe, K. & Yan, J.  Enhancement of exciton valley polarization in monolayer MoS2 induced by scattering.  _Physical Review B_ 104, L121408 (2021).
  * [19] Gupta, G., Watanabe, K., Taniguchi, T. & Majumdar, K.  Observation of $\sim$ 100 % valley-coherent excitons in monolayer MoS2 through giant enhancement of valley coherence time.  _Light: Science & Applications_ 12, 173 (2023).
  * [20] An, Z. _et al._ Strain control of exciton and trion spin-valley dynamics in monolayer transition metal dichalcogenides.  _Physical Review B_ 108, L041404 (2023).
  * [21] Smoleński, T. _et al._ Tuning valley polarization in a WSe2 monolayer with a tiny magnetic field.  _Physical Review X_ 6, 021024 (2016).
  * [22] Mak, K. F. _et al._ Tightly bound trions in monolayer MoS2.  _Nature materials_ 12, 207–211 (2013).
  * [23] Singh, A. _et al._ Coherent electronic coupling in atomically thin MoSe2.  _Physical review letters_ 112, 216804 (2014).
  * [24] Singh, A. _et al._ Trion formation dynamics in monolayer transition metal dichalcogenides.  _Physical Review B_ 93, 041401 (2016).
  * [25] Hao, K. _et al._ Coherent and incoherent coupling dynamics between neutral and charged excitons in monolayer MoSe2.  _Nano letters_ 16, 5109–5113 (2016).
  * [26] Robert, C. _et al._ Spin/valley pumping of resident electrons in WS2 and WSe2 monolayers.  _Nature Communications_ 12, 5455 (2021).
  * [27] Zinkiewicz, M. _et al._ Excitonic complexes in n-doped WS2 monolayer.  _Nano letters_ 21, 2519–2525 (2021).
  * [28] Steinhoff, A. _et al._ Biexciton fine structure in monolayer transition metal dichalcogenides.  _Nature Physics_ 14, 1199–1204 (2018).
  * [29] Conway, M. _et al._ Direct measurement of biexcitons in monolayer WS2.  _2D Materials_ 9, 021001 (2022).
  * [30] Muir, J. B. _et al._ Interactions between fermi polarons in monolayer WS2.  _Nature Communications_ 13, 6164 (2022).
  * [31] You, Y. _et al._ Observation of biexcitons in monolayer WSe2.  _Nature Physics_ 11, 477–481 (2015).
  * [32] Mostaani, E. _et al._ Diffusion quantum monte carlo study of excitonic complexes in two-dimensional transition-metal dichalcogenides.  _Physical Review B_ 96, 075431 (2017).
  * [33] Barbone, M. _et al._ Charge-tuneable biexciton complexes in monolayer WSe2.  _Nature communications_ 9, 3721 (2018).
  * [34] Ye, Z. _et al._ Efficient generation of neutral and charged biexcitons in encapsulated WSe2 monolayers.  _Nature communications_ 9, 3718 (2018).
  * [35] Rodin, A., Trushin, M., Carvalho, A. & Castro Neto, A.  Collective excitations in 2D materials.  _Nature Reviews Physics_ 2, 524–537 (2020).
  * [36] Chatterjee, S. _et al._ Probing biexciton in monolayer WS2 through controlled many-body interaction.  _2D Materials_ 9, 015023 (2021).
  * [37] Mostaani, E. _et al._ Charge-carrier complexes in monolayer semiconductors.  _Phys. Rev. B_ 108, 035420 (2023).
  * [38] Das, S. _et al._ Highly nonlinear biexcitonic photocurrent from ultrafast interlayer charge transfer.  _ACS Nano_ 16, 9728–9735 (2022).
  * [39] Wei, K. _et al._ Charged biexciton polaritons sustaining strong nonlinearity in 2d semiconductor-based nanocavities.  _Nature Communications_ 14, 5310 (2023).
  * [40] Van Tuan, D., Shi, S.-F., Xu, X., Crooker, S. A. & Dery, H.  Six-body and eight-body exciton states in monolayer WSe2.  _Physical Review Letters_ 129, 076801 (2022).
  * [41] Choi, J., Li, J., Van Tuan, D., Dery, H. & Crooker, S.  Emergence of 6-particle” hexciton”states in WSe2 and MoSe2 monolayers.  _arXiv preprint arXiv:2312.09476_ (2023).
  * [42] Chatterjee, S. _et al._ Trion-trion annihilation in monolayer WS2.  _Physical Review B_ 105, L121409 (2022).
  * [43] Prando, G. A. _et al._ Revealing excitonic complexes in monolayer WS2 on talc dielectric.  _Physical Review Applied_ 16, 064055 (2021).
  * [44] Chand, S. B. _et al._ Interaction-driven transport of dark excitons in 2D semiconductors with phonon-mediated optical readout.  _Nature Communications_ 14, 3712 (2023).
  * [45] Ayari, S., Jaziri, S., Ferreira, R. & Bastard, G.  Phonon-assisted exciton/trion conversion efficiency in transition metal dichalcogenides.  _Physical Review B_ 102, 125410 (2020).
  * [46] Lau, C. S. _et al._ Quantum transport in two-dimensional WS2 with high-efficiency carrier injection through indium alloy contacts.  _ACS nano_ 14, 13700–13708 (2020).
  * [47] Lau, C. S. _et al._ Gate-defined quantum confinement in CVD 2D WS2.  _Advanced Materials_ 34, 2103907 (2022).
  * [48] Liu, G.-B., Shan, W.-Y., Yao, Y., Yao, W. & Xiao, D.  Three-band tight-binding model for monolayers of group-VIB transition metal dichalcogenides.  _Physical Review B_ 88, 085433 (2013).
  * [49] Zhang, X.-X., You, Y., Zhao, S. Y. F. & Heinz, T. F.  Experimental evidence for dark excitons in monolayer WSe2.  _Physical review letters_ 115, 257403 (2015).
  * [50] Echeverry, J., Urbaszek, B., Amand, T., Marie, X. & Gerber, I. C.  Splitting between bright and dark excitons in transition metal dichalcogenide monolayers.  _Physical Review B_ 93, 121107 (2016).
  * [51] Yu, H., Liu, G.-B., Gong, P., Xu, X. & Yao, W.  Dirac cones and Dirac saddle points of bright excitons in monolayer transition metal dichalcogenides.  _Nature communications_ 5, 3876 (2014).
  * [52] Chen, S.-Y. _et al._ Superior valley polarization and coherence of 2s excitons in monolayer WSe2.  _Physical review letters_ 120, 046402 (2018).
  * [53] Wang, H. _et al._ Radiative lifetimes of excitons and trions in monolayers of the metal dichalcogenide MoS2.  _Physical Review B_ 93, 045407 (2016).
  * [54] Dal Conte, S. _et al._ Ultrafast valley relaxation dynamics in monolayer MoS2 probed by nonequilibrium optical techniques.  _Physical Review B_ 92, 235425 (2015).
  * [55] Cadiz, F. _et al._ Excitonic linewidth approaching the homogeneous limit in MoS2-based van der waals heterostructures.  _Physical Review X_ 7, 021026 (2017).
  * [56] Kallatt, S., Das, S., Chatterjee, S. & Majumdar, K.  Interlayer charge transport controlled by exciton–trion coherent coupling.  _npj 2D Materials and Applications_ 3, 15 (2019).
  * [57] Gao, F. _et al._ Valley trion dynamics in monolayer MoSe2.  _Physical Review B_ 94, 245413 (2016).
  * [58] Mitioglu, A. _et al._ Optical manipulation of the exciton charge state in single-layer tungsten disulfide.  _Physical Review B_ 88, 245403 (2013).
  * [59] Miller, B. _et al._ Tuning the Fröhlich exciton-phonon scattering in monolayer MoS2.  _Nature communications_ 10, 807 (2019).
  * [60] Van Tuan, D., Jones, A. M., Yang, M., Xu, X. & Dery, H.  Virtual trions in the photoluminescence of monolayer transition-metal dichalcogenides.  _Physical Review Letters_ 122, 217401 (2019).
  * [61] Shree, S. _et al._ Observation of exciton-phonon coupling in MoSe2 monolayers.  _Physical Review B_ 98, 035302 (2018).
  * [62] Molas, M. R., Nogajewski, K., Potemski, M. & Babiński, A.  Raman scattering excitation spectroscopy of monolayer WS2.  _Scientific reports_ 7, 5036 (2017).

Figure 1: Device schematic and $\mu$PL of the excitonic complexes for resonant
and non-resonant excitations. (a) The schematic diagram of the sample device
where monolayer WS2 is sandwiched between two $h$BN layers over the graphite
back gate. (b) The spin-valley configurations of $e-h$ pair for intravalley
(singlet trion, $T_{s}$), intervalley (triplet trion, $T_{t}$), dark trion
($T_{D}$) and the combination of bright exciton ($X$) and $T_{D}$ or the five-
particle charged biexcitons (quintons, $Q$). The solid (dotted) line
represents up(-down) spin bands at the zone edges ($K$ and $K^{\prime}$
valleys). (c) Representative micro-photoluminescence ($\mu$PL) spectra of the
monolayer for non-resonant $\lambda_{exc}$ = 570 nm excitation at $T$ = 4.6 K.
Individual energy states are identified ($X$ at 596 nm or $\sim$ 2.078 eV),
$T$ at 606 nm or $\sim$ 2.044 eV, $Q$ at 614 nm or $\sim$ 2.019 eV and $T_{D}$
at 618 nm or $\sim$ 2.006 eV) with multi-peak fitting. The energy separation
relative to the neutral exciton (in meV) is marked for gate voltage, $V_{g}$ =
0 V with the excitation power $\sim$ 20 $\mu$W. (d) The normalized intensity
map of the excitation wavelength-dependent emission spectra recorded below the
exciton energy at $T$ = 4.6 K. The right vertical axis represents the excess
energy [energy difference between laser excitation ($E_{exc}$) and neutral
exciton ($E_{X}$)]. The red (yellow) vertical dashed line denotes the $T$
($Q$) energy resonance across the excitation. The brightest region corresponds
to the exciton resonance ($\lambda_{exc}$ = 596 nm) denoted by the white
horizontal dashed line with $V_{g}=0$ V. (e) The normalized intensity of the
charged states (following the vertical lines in the previous figure) over the
photo-luminescence excitation (PLE). The intensity is the maximum when the
excess energy is the minimum. The profile is fitted with a Lorentzian curve to
estimate the intrinsic broadening $\Gamma$ or carrier lifetime as
$\tau=\hbar/2\Gamma$. (f) Representative micro-photoluminescence ($\mu$PL)
spectra of the monolayer for resonant $\lambda_{exc}$ = 596 nm excitation
(following in horizontal line cut from figure d). The solid vertical line
denotes the exciton resonance (excitation wavelength, $\lambda_{exc}$ = 596
nm) and the dashed line denotes the cut-off filter for reference. The
individual peaks are fitted with Lorentzian multi-peak fitting to show the
$T_{s}$, $T_{t}$ and $Q$ energy states with an incident laser power of $\sim$
8.7 $\mu$W. Figure 2: Gate dependent spectroscopy for non-resonant excitation
and dynamic modulation of valley polarization for the charged states. (a) The
two-dimensional colorplot for the $V_{g}$ dependent $\mu$PL spectroscopy under
non-resonant excitation shown in the upper panel with co-polarized mode (where
$I_{co}$ is the intensity under $\sigma^{+}$ excitation and $\sigma^{+}$
detection, $\sigma^{+}$/$\sigma^{+}$). The energy states are mostly
featureless for $V_{g}<0$ V. However, when electron injection starts (for
$V_{g}>0$ V) the neutral state intensity drops and charged state intensity
grows monotonically with a pronounced red shift dominated by the $Q$ state in
the high $n$-doped region (labelled as $n_{++}$). The bottom panel represents
the colorplot of the corresponding $P_{c}$ within the wavelength range as a
function of gate voltage. (b) The gate-dependent variation in energy positions
corresponding to different energy states extracted from the individual peak
fittings. The $Q$ state shows a noticeable red shift under positive gate bias
of $\sim$ 35 meV compared to the neutral region. (c) The gate dependent valley
polarization $\mathcal{P_{C}}$ or the degree of circular polarization
($P_{c}$) of the $Q$ state. The $P_{c}$ shows a non-monotonic behavior as the
carrier density increases. Inset: Corresponding linewidth ($\Gamma$) of the
$Q$ state extracted from the fitting across the carrier density. (d)
Representative diagram describing about the $V_{g}$ dependent transitions from
charged biexcitonic state (quinton state, $Q$) to a $T_{D}$ state. At
$V_{g}=0$ V the vertical transition (represented by the orange arrow) is at
$q=0=Q_{0}$ while the transition occurs ($\hbar\omega$ at $V_{g}>0$ V) at
higher $q$ value (represented by the red arrow) for higher $V_{g}$ because of
Pauli blocking. In-plane projection of the same is presented in the bottom
panel in the $Q_{x}-Q_{y}$ plane for reference. (e) The extracted scattering
rate, $\gamma_{p}$, for a given lifetime of $\tau$ = 50 ps for $Q$ state [31,
33, 36, 38]. The scattering rate increases initially along with the increase
in carrier density and then saturates. The increment in $P_{c}$ along with
$\gamma_{p}$ refers to the motional narrowing regime (shaded region). (f) The
extracted exchange interaction ($J^{LR}(q)$) variation with carrier density
along with the normalized CoM momenta dispersion ($q/K$) mapped from the
kinetic energy difference (inset) for the experimental red shift from figure
2b using equation 4. The $J^{LR}(q)$ increases with increasing carrier
density. Figure 3: Modulation of coherently coupled charged excitonic
complexes under resonant excitation. (a-b) Gate-dependent intensity mapping of
the charged states under resonant excitation with circularly polarized light
in co-polarized ($I_{co}$ or $\sigma^{+}/\sigma^{+}$) mode. A zoomed-in
picture is presented in the figure inset divided into four different regions.
The intensity profile follows a non-monotonic behavior. Non-monotonic
intensity modulation of the charged states corresponding to $T_{s}$, $T_{t}$
and $Q$ states is presented in b. The vertical dashed lines demarcate four
different regions same as in a. (c) Formation of the charged states are
represented schematically for four different conditions (Three particle states
are shown in the schematics for simplicity. The same argument holds for five
particles also). For $V_{g}<0$ V (gray background), the charged states are
formed either through defect/impurity-assisted processes or through photo-
ionization effect (defect states are shown by the discontinuous blue band
below the optical bandgap and the neutral exciton energy is denoted as $E_{X}$
with the oscillator strength represented by the width of the $E_{X}$ band).
This is a relatively weak and inefficient process, so the population of
charged states is low. When $V_{g}$ becomes slightly positive, the resonantly
formed excitons (red vertical arrow) can efficiently capture the electrically
injected (shown by the curved arrow) carriers and hence there is a strong
population of charged states ($n$: yellow background). For the $n_{+}$ region,
the exciton oscillator strength drops with further $n$-doping. Since, the net
population density of the charged states is a product of the exciton
population (oscillator strength of the neutral exciton) and the coupling
parameter under resonance, hence, the coherently coupled charged state density
decreases ($n_{+}$: green background). Finally, for $V_{g}>>0$ V, the system
becomes electron-rich and the $n$-doping induced charged state carrier
population starts to grow as for the non-resonant excitation scenario
($n_{++}$: sky background). (d) The upper panel schematically represents the
individual expected intensity profile of the charged states as a function of
$V_{g}$ for the four cases described above while the combined effect is
represented in the bottom panel as a reference describing the anomalous
experimental trend-line (with black dashed line). The color coding refers to
the different cases for four different regions of $V_{g}$ described above.
Figure 4: Electrical switching of polarization for quinton states. (a) The
degree of circular polarization corresponding to the quinton states can be
electrically switched from a high-polarized state to a low-polarized state by
altering the polarity of $V_{g}$. The circular polarization retains for the
bright $Q$ states when $V_{g}$ is positive i.e. the system is electron-doped
as shown in the left panel. However, the valley information is lost when the
polarity of the $V_{g}$ is altered as shown in the right panel. In our
experimental scheme, we excite with $\sigma^{+}$, and detect $\sigma^{+}$
photon (shown in red) from the $Q$ state with a positive voltage, while
getting the equal intensity of both the helicity of photons with negative
$V_{g}$ (shown in red and blue). (b) The device operation is demonstrated over
several cycles by sequentially altering the polarity of $V_{g}$ and recording
the corresponding $P_{c}$ over a wavelength window of 618 - 624 nm. Here, the
$V_{g}$ is switched between $\pm$ 4 V and the $P_{c}$ is switched between high
(yellow-shaded region) and low-polarized states (grey-shaded region)
efficiently without any noticeable variations. The error comes from the
statistical average within the specified wavelength range.


# The achromatic number of $K_{6}\square K_{q}$
equals $2q+3$ if $q\geq 41$ is odd

Mirko Horňák
Institute of Mathematics, P.J. Šafárik University
Jesenná 5, 040 01 Košice, Slovakia E-mail address<EMAIL_ADDRESS>
###### Abstract

Let $G$ be a graph and $C$ a finite set of colours. A vertex colouring
$f:V(G)\to C$ is complete provided that for any two distinct colours
$c_{1},c_{2}\in C$ there is $v_{1}v_{2}\in E(G)$ such that $f(v_{i})=c_{i}$,
$i=1,2$. The achromatic number of $G$ is the maximum number $\mathrm{achr}(G)$
of colours in a proper complete vertex colouring of $G$. In the paper it is
proved that if $q\geq 41$ is an odd integer, then the achromatic number of the
Cartesian product of $K_{6}$ and $K_{q}$ is $2q+3$.

Keywords: complete vertex colouring, achromatic number, Cartesian product,
complete graph

##  1 Introduction

Let $G$ be a finite simple graph and $C$ a finite set of colours. A vertex
colouring $f:V(G)\to C$ is complete if for any pair of distinct colours
$c_{1},c_{2}\in C$ one can find in $G$ an edge $\\{v_{1},v_{2}\\}$ (often
shortened to $v_{1}v_{2}$) such that $f(v_{i})=c_{i}$, $i=1,2$. The achromatic
number of $G$, denoted by $\mathrm{achr}(G)$, is the maximum cardinality of
the colour set in a proper complete vertex colouring of $G$.

The concept was introduced quite a long ago in Harary, Hedetniemi and Prins
[8], where it was proved the following:

######  Theorem 1.

If $G$ is a graph, and an integer $k$ satisfies $\chi(G)\leq
k\leq\mathrm{achr}(G)$, there exists a proper complete vertex colouring of $G$
using $k$ colours. ∎

There are still only few graph classes $\mathcal{G}$ such that
$\mathrm{achr}(G)$ is known for all $G\in\mathcal{G}$. This is certainly
related to the fact that determining the achromatic number is an NP-complete
problem even for trees, see Cairnie and Edwards [2]. Two surveys are available
on the topic, namely Edwards [6] and Hughes and MacGillivray[10]; more
generally, Chapter 12 in the book [3] by Chartrand and Zhang deals with
complete vertex colourings. A comprehensive list of publications concerning
the achromatic number is maintained by Edwards [7].

Some papers are devoted to the achromatic number of graphs constructed by
graph operations. So, Hell and Miller [9] considered
$\mathrm{achr}(G_{1}\times G_{2})$, where $G_{1}\times G_{2}$ stands for the
categorical product of graphs $G_{1}$ and $G_{2}$ (we follow here the notation
by Imrich and Klavžar [14]).

In this paper we are interested in the achromatic number of the Cartesian
product $G_{1}\square G_{2}$ of graphs $G_{1}$ and $G_{2}$, the graph with
$V(G_{1}\square G_{2})=\\{(v_{1},v_{2}):v_{i}\in V(G_{i}),i=1,2\\}$, in which
$(v_{1}^{1},v_{2}^{1})(v_{1}^{2},v_{2}^{2})\in E(G_{1}\square G_{2})$ if and
only if there is $i\in\\{1,2\\}$ such that $v_{i}^{1}v_{i}^{2}\in E(G_{i})$
and $v_{3-i}^{1}=v_{3-i}^{2}$. As observed by Chiang and Fu [4],
$\mathrm{achr}(G_{1})=p$ and $\mathrm{achr}(G_{2})=q$ implies
$\mathrm{achr}(G_{1}\square G_{2})\geq\mathrm{achr}(K_{p}\square K_{q})$. This
inequality motivates a special interest in the achromatic number of the
Cartesian product of two complete graphs. From the obvious fact that
$G_{2}\square G_{1}$ is isomorphic to $G_{1}\square G_{2}$ it is clear that
when determining $\mathrm{achr}(K_{p}\square K_{q})$ we may suppose without
loss of generality $p\leq q$.

The problem of determining $\mathrm{achr}(K_{p}\square K_{q})$ with $p\leq 4$
was solved in Horňák and Puntigán [13] (for $p\leq 3$ the result was
rediscovered in [4]) and that for $p=5$ in Horňák and Pčola [11], [12]. In [5]
Chiang and Fu proved that if $r$ is an odd projective plane order, then
$\mathrm{achr}(K_{(r^{2}+r)/2}\square K_{(r^{2}+r)/2})=(r^{3}+r^{2})/2$. (For
$r=3$ the fact that $\mathrm{achr}(K_{6}\square K_{6})=18$ was known already
to Bouchet [1].)

Here we show that $\mathrm{achr}(K_{6}\square K_{q})=2q+3$ if $q$ is an odd
integer with $q\geq 41$. This is the first of three papers devoted to
completely solve the problem of finding $\mathrm{achr}(K_{6}\square K_{q})$.

For $k,l\in\mathbb{Z}$ we denote integer intervals by

$[k,l]=\\{z\in\mathbb{Z}:k\leq z\leq
l\\},\qquad[k,\infty)=\\{z\in\mathbb{Z}:k\leq z\\}.$

Further, with a set $A$ and $m\in[0,\infty)$ we use $\binom{A}{m}$ for the set
of $m$-element subsets of $A$.

Now let $p,q\in[1,\infty)$. Under the assumption that $V(K_{r})=[1,r]$,
$r=p,q$, we have $V(K_{p}\square K_{q})=[1,p]\times[1,q]$, while
$E(K_{p}\square K_{q})$ consists of edges $(i,j_{1})(i,j_{2})$ with
$i\in[1,p]$, $j_{1},j_{2}\in[1,q]$, $j_{1}\neq j_{2}$ and $(i_{1},j)(i_{2},j)$
with $i_{1},i_{2}\in[1,p]$, $i_{1}\neq i_{2}$, $j\in[1,q]$.

A vertex colouring $f:[1,p]\times[1,q]\to C$ of the graph $K_{p}\square K_{q}$
can be conveniently described using the $p\times q$ matrix $M=M(f)$ whose
entry in the $i$th row and the $j$th column is $(M)_{i,j}=f(i,j)$. Such a
colouring is proper if any row of $M$ consists of $q$ distinct entries and any
column of $M$ consists of $p$ distinct entries. Further, $f$ is complete
provided that any pair $\\{\alpha,\beta\\}\in\binom{C}{2}$ is good in $M$ in
the following sense: there are
$(i_{1},j_{1}),(i_{2},j_{2})\in[1,p]\times[1,q]$ such that
$\\{(M)_{i_{1},j_{1}},(M)_{i_{2},j_{2}}\\}=\\{\alpha,\beta\\}$ and either
$i_{1}=i_{2}$, which we express by saying that the pair $\\{\alpha,\beta\\}$
is row-based (in $M$), or $j_{1}=j_{2}$, i.e., the pair $\\{\alpha,\beta\\}$
is column-based (in $M$).

Let $\mathcal{M}(p,q,C)$ denote the set of $p\times q$ matrices $M$ with
entries from $C$ such that all rows (columns) of $M$ have $q$ ($p$,
respectively) distinct entries, and each pair
$\\{\alpha,\beta\\}\in\binom{C}{2}$ is good in $M$. So, if
$f:[1,p]\times[1,q]\to C$ is a proper complete vertex colouring of
$K_{p}\square K_{q}$, then $M(f)\in\mathcal{M}(p,q,C)$.

Conversely, if $M\in\mathcal{M}(p,q,C)$, then the mapping
$f_{M}:[1,p]\times[1,q]\to C$ with $f_{M}(i,j)=(M)_{i,j}$ is a proper complete
vertex colouring of $K_{p}\square K_{q}$. Thus, we have proved:

######  Proposition 2.

If $p,q\in[1,\infty)$ and $C$ is a finite set, then the following statements
are equivalent:

$\mathrm{(}1)$ There is a proper complete vertex colouring of $K_{p}\square
K_{q}$ using as colours elements of $C$.

$\mathrm{(}2)$ $\mathcal{M}(p,q,C)\neq\emptyset$. ∎

We have another evident result:

######  Proposition 3.

If $p,q\in[1,\infty)$, $C,D$ are finite sets, $M\in\mathcal{M}(p,q,C)$,
mappings $\rho:[1,p]\to[1,p]$, $\sigma:[1,q]\to[1,q]$, $\pi:C\to D$ are
bijections, and $M_{\rho,\sigma}$, $M_{\pi}$ are $p\times q$ matrices defined
by $(M_{\rho,\sigma})_{i,j}=(M)_{\rho(i),\sigma(j)}$ and
$(M_{\pi})_{i,j}=\pi((M)_{i,j})$, then $M_{\rho,\sigma}\in\mathcal{M}(p,q,C)$
and $M_{\pi}\in\mathcal{M}(p,q,D)$. ∎

Let $M\in\mathcal{M}(p,q,C)$. The frequency of a colour $\gamma\in C$ is the
number $\mathrm{frq}(\gamma)$ of appearances of $\gamma$ in $M$, and the
frequency of $M$, denoted $\mathrm{frq}(M)$, is the minimum of frequencies of
colours in $C$. A colour of frequency $l$ is an $l$-colour. $C_{l}$ is the set
of $l$-colours, $c_{l}=|C_{l}|$, and $C_{l+}$ is the set of colours of
frequency at least $l$, $c_{l+}=|C_{l+}|$. We denote by $\mathbb{R}(i)$ the
set $\\{(M)_{i,j}:j\in[1,q]\\}$ of colours in the $i$th row of $M$ and by
$\mathbb{C}(j)$ the set $\\{(M)_{i,j}:i\in[1,p]\\}$ of colours in the $j$th
column of $M$. Further, for $k\in\\{l,l+\\}$ let

$\displaystyle\mathbb{R}_{k}(i)$ $\displaystyle=C_{k}\cap\mathbb{R}(i),\qquad$
$\displaystyle r_{k}(i)$ $\displaystyle=|\mathbb{R}_{k}(i)|,$
$\displaystyle\mathbb{C}_{k}(j)$ $\displaystyle=C_{k}\cap\mathbb{C}(j),$
$\displaystyle c_{k}(j)$ $\displaystyle=|\mathbb{C}_{k}(j)|.$

If $A\subseteq[1,p]$, $|A|\geq 2$, then

$\mathbb{R}(A)=\bigcap_{l\in A}(C_{|A|}\cap\mathbb{R}(l)),\qquad
r(A)=|\mathbb{R}(A)|$

($\mathbb{R}(A)$ is the set of $|A|$-colours appearing in all rows of $M$
numbered by elements of $A$). Provided that
$A=\\{i,j\\},\\{i,j,k\\},\\{i,j,k,l\\}$, instead of $\mathbb{R}(A)$ we write
$\mathbb{R}(i,j)$, $\mathbb{R}(i,j,k)$, $\mathbb{R}(i,j,k,l)$, while $r(A)$ is
simplified to $r(i,j)$, $r(i,j,k)$, $r(i,j,k,l)$, respectively. With
$\\{i,j\\}\subseteq[1,p]$ and $\\{m,n\\}\subseteq[1,q]$ we set

$\displaystyle\mathbb{R}_{3+}(i,j)$
$\displaystyle=C_{3+}\cap\mathbb{R}(i)\cap\mathbb{R}(j),\qquad$ $\displaystyle
r_{3+}(i,j)$ $\displaystyle=|\mathbb{R}_{3+}(i,j)|,$
$\displaystyle\mathbb{C}(m,n)$
$\displaystyle=C_{2}\cap\mathbb{C}(m)\cap\mathbb{C}(n),$ $\displaystyle
c(m,n)$ $\displaystyle=|\mathbb{C}(m,n)|.$

If $B\subseteq[1,p]$ and $3\leq|B|\leq p-2$, then

$\mathbb{R}^{*}(B)=\bigcup_{l=2}^{|B|}\bigcup_{A\in\binom{B}{l}}\mathbb{R}(A),\qquad
r^{*}(B)=|\mathbb{R}^{*}(B)|.$

For $\gamma\in C$ let

$\mathbb{R}(\gamma)=\\{i\in[1,p]:\gamma\in\mathbb{R}(i)\\}.$

With $S\subseteq[1,p]\times[1,q]$ we say that a colour $\gamma\in C$ occupies
a position in $S$ if there is $(i,j)\in S$ such that $(M)_{i,j}=\gamma$. If
$\emptyset\neq A\subseteq C$, the set of columns covered by $A$ is

$\mathrm{Cov}(A)=\\{j\in[1,q]:\mathbb{C}(j)\cap A\neq\emptyset\\}.$

We define $\mathrm{cov}(A)=|\mathrm{Cov}(A)|$, and with
$A\in\\{\\{\alpha\\},\\{\alpha,\beta\\}\\}$ we use a simplified notation
$\mathrm{Cov}(\alpha)$, $\mathrm{Cov}(\alpha,\beta)$ and
$\mathrm{cov}(\alpha)$, $\mathrm{cov}(\alpha,\beta)$ instead of
$\mathrm{Cov}(A)$ and $\mathrm{cov}(A)$.

##  2 Lower bound

######  Proposition 4.

If $q\in[7,\infty)$ and $q\equiv 1\pmod{2}$, then $\mathrm{achr}(K_{6}\square
K_{q})\geq 2q+3$.

###### Proof.

Let $s=\frac{q-3}{2}$, and let $M$ be the $6\times q$ matrix below. We show
that $M\in\mathcal{M}(6,q,C)$, where $C=[1,9]\cup X_{s}\cup Y_{s}\cup
Z_{s}\cup T_{s}$, $U_{s}=\\{u_{i}:i\in[1,s]\\}$ for $U\in\\{X,Y,Z,T\\}$, and
the sets $[1,9]$, $X_{s},Y_{s},Z_{s},T_{s}$ are pairwise disjoint.

$\setcounter{MaxMatrixCols}{13}\begin{pmatrix}1&2&3&x_{1}&x_{2}&\dots&x_{s-1}&x_{s}&y_{1}&y_{2}&\dots&y_{s-1}&y_{s}\\\
4&5&6&x_{s}&x_{1}&\dots&x_{s-2}&x_{s-1}&z_{1}&z_{2}&\dots&z_{s-1}&z_{s}\\\
7&8&9&t_{1}&t_{2}&\dots&t_{s-1}&t_{s}&x_{1}&x_{2}&\dots&x_{s-1}&x_{s}\\\
3&1&2&z_{1}&z_{2}&\dots&z_{s-1}&z_{s}&t_{1}&t_{2}&\dots&t_{s-1}&t_{s}\\\
5&6&4&t_{s}&t_{1}&\dots&t_{s-2}&t_{s-1}&y_{s}&y_{1}&\dots&y_{s-2}&y_{s-1}\\\
8&9&7&y_{1}&y_{2}&\dots&y_{s-1}&y_{s}&z_{s}&z_{1}&\dots&z_{s-2}&z_{s-1}\end{pmatrix}$

Since $s\geq 2$, because of our assumptions on the structure of $C$ it is
clear that elements in lines (rows and columns) of $M$ are pairwise distinct.
Thus it is sufficient to show that each pair
$\\{\alpha,\beta\\}\in\binom{C}{2}$ is good in $M$.

If $\alpha,\beta\in[1,9]$, then both $\alpha$ and $\beta$ appear twice in the
columns $1,2,3$, hence the pair $\\{\alpha,\beta\\}$ is column-based.

If $\alpha\in C$ and $\beta\in X_{s}\cup Y_{s}\cup Z_{s}\cup T_{s}$, realise
that $\mathbb{R}(\alpha)\in\mathcal{R}_{1}\cup\mathcal{R}_{2}$ and
$\mathbb{R}(\beta)\in\mathcal{R}_{2}$, where
$\mathcal{R}_{1}=\\{\\{1,4\\},\\{2,5\\},\\{3,6\\}\\}$ and
$\mathcal{R}_{2}=\\{[1,3],\\{1,5,6\\},\\{2,4,6\\},$ $[3,5]\\}$. As $R\cap
R_{2}\neq\emptyset$ for any $R\in\mathcal{R}_{1}\cup\mathcal{R}_{2}$ and any
$R_{2}\in\mathcal{R}_{2}$, the pair $\\{\alpha,\beta\\}$ is row-based.

So, Proposition 2 yields $\mathrm{achr}(K_{6}\square K_{q})\geq|C|=4s+9=2q+3$.
∎

##  3 Auxiliary results

If $M\in\mathcal{M}(p,q,C)$ and $\gamma\in C_{l}$, the excess of the colour
$\gamma$ is the number defined by

$\mathrm{exc}(\gamma)=l(p+q-l-1)-(|C|-1).$

######  Lemma 5.

If $p,q\in[1,\infty)$, $C$ is a finite set, $M\in\mathcal{M}(p,q,C)$ and
$\gamma\in C_{l}$, then the following hold:

$1.$ $l\leq\min(p,q)$;

$2.$ $\mathrm{exc}(\gamma)\geq 0$;

$3.$ $l=\mathrm{frq}(M)$ implies $|C|\leq\lfloor\frac{pq}{l}\rfloor$.

###### Proof.

1\. The assumption $l>\min(p,q)$ would mean, by the pigeonhole principle, that
the colouring $f_{M}$ is not proper.

2\. Because of Proposition 3 we may suppose without loss of generality
$(M)_{i,i}=\gamma$ for all $i\in[1,l]$. For simplicity we use (w) to indicate
that it is just Proposition 3, which enables us to restrict our attention to
matrices with a special property.

The colouring $f_{M}$ is complete, hence each of $|C|-1$ colours in
$C\setminus\\{\gamma\\}$ must occupy a position in the set $S=\\{(i,j):(i\leq
l\lor j\leq l)\land i\neq j\\}$. Thus, $|S|=ql+(p-l)l-l\geq|C|-1$ and
$\mathrm{exc}(\gamma)=|S|-(|C|-1)\geq 0$.

3\. If $\gamma^{\prime}\in C\setminus\\{\gamma\\}$, then
$\mathrm{frq}(\gamma^{\prime})\geq\mathrm{frq}(\gamma)=l$. Therefore, the
total number of entries of the matrix $M$ is $pq\geq l|C|$, and the desired
inequality follows. ∎

From the proof of Lemma 5.2 we see that the excess of a colour $\gamma\in C$
is equal to the maximum number of entries (other than $\gamma$) that can be
deleted from $M$ so that each pair
$\\{\gamma,\gamma^{\prime}\\}\in\binom{C}{2}$ is good even in the “partial
matrix” corresponding to the involved restriction of $f_{M}$.

The excess of a matrix $M\in\mathcal{M}(p,q,C)$, denoted by $\mathrm{exc}(M)$,
is the minimum of excesses of colours in $C$.

######  Lemma 6.

If $p,q\in[1,\infty)$, $C$ is a finite set and $M\in\mathcal{M}(p,q,C)$, then
$\mathrm{exc}(M)=\mathrm{exc}(\gamma)$, where $\gamma\in C$ and
$\mathrm{frq}(\gamma)=\mathrm{frq}(M)$.

###### Proof.

Let $m=\min(p,q)$. If $\alpha,\beta\in C$ and
$k=\mathrm{frq}(\alpha)>\mathrm{frq}(\beta)$, then, by Lemma 5.1, $k\leq m$.
As a consequence,
$\mathrm{exc}(\alpha)\geq\mathrm{exc}(\beta)\geq\mathrm{exc}(f)$, since
$\mathrm{exc}(\alpha)=g(k)$, where $g(x)=x(p+q-x-1)-|C|+1$ is increasing in
the interval $\langle 1,\frac{p+q-1}{2}\rangle\supsetneqq\langle
1,m-1\rangle$, and $p=q=m$ implies $g(m-1)=g(m)$. ∎

######  Lemma 7 (see [13], [4]).

If $p,q\in[1,\infty)$ and $p\leq q$, then

$\mathrm{achr}(K_{p}\square K_{q})\leq\max(\min(l(p+q-l-1)+1,\lfloor
pq/l\rfloor):l\in[1,p]).\ \qed$

######  Corollary 8.

If $q\in[7,\infty)$, then $\mathrm{achr}(K_{6}\square K_{q})\leq 2q+7$.

###### Proof.

By Lemma 7 with $p=6$ we obtain $\mathrm{achr}(K_{6}\square
K_{q})\leq\max(q+5,2q+7,2q,\lfloor\frac{6q}{4}\rfloor,\lfloor\frac{6q}{5}\rfloor,q)=2q+7$.
∎

##  4 Properties of matrices in $\mathcal{M}(6,q,C)$

Suppose we know that $\mathrm{achr}(K_{6}\square K_{q})\geq 2q+s-1$ for a pair
$(q,s)$ with $q\in[7,\infty)$ and $s\in[1,\infty)$, and we want to prove that
$\mathrm{achr}(K_{6}\square K_{q})=2q+s-1$; clearly, because of Corollary 8 it
is sufficient to work with $s\leq 7$. Proceeding by the way of contradiction
let $s^{\prime}\in[s,7]$ satisfy $\mathrm{achr}(K_{6}\square
K_{q})=2q+s^{\prime}$. By Theorem 1 and Proposition 2 there is a
$(2q+s)$-element set $C$ and a matrix $M\in\mathcal{M}(6,q,C)$. Our task will
be accomplished by showing that the existence of $M$ leads to a contradiction.
For that purpose we shall need properties of $M$. So in all claims of the
present section we suppose that the notation corresponds to a matrix
$M\in\mathcal{M}(6,q,C)$ with $q\in[7,\infty)$ and $|C|=2q+s\leq 2q+7$. We
associate with $M$ an auxiliary graph $G$ with $V(G)=[1,6]$, in which
$\\{i,k\\}\in E(G)$ if and only if $r(i,k)\geq 1$.

######  Claim 1.

The following statements are true:

$1.$ $c_{1}=0$;

$2.$ $c_{l}=0$ for $l\in[7,\infty)$;

$3.$ $c_{2}\geq 3s$;

$4.$ $c_{3+}\leq 2q-2s$;

$5.$ $\sum_{i=3}^{6}ic_{i}\leq 6q-6s$;

$6.$ $\mathrm{frq}(M)=2$;

$7.$ $\mathrm{exc}(M)=7-s$;

$8.$ $c_{4+}\leq c_{2}-3s$;

$9.$ if $\\{i,k\\}\in\binom{[1,6]}{2}$, then $r(i,k)\leq 8-s$.

###### Proof.

1\. If $c_{1}>0$, a 1-colour $\gamma\in C$ satisfies
$\mathrm{exc}(\gamma)=q+4-(2q+s-1)=5-q-s<0$ in contradiction to Lemma 5.2.

2\. Use Lemma 5.1.

3\. By Claims 1.1 and 1.2, counting the number of vertices of $K_{6}\square
K_{q}$ we get $6q=\sum_{i=2}^{6}ic_{i}$. Therefore,
$3(2q+s)=3|C|=3(c_{2}+c_{3+})\leq c_{2}+\sum_{i=2}^{6}ic_{i}=c_{2}+6q$, which
yields $c_{2}\geq 3s$.

4\. From
$2(2q+s)+c_{3+}=2|C|+c_{3+}=2c_{2}+3c_{3+}\leq\sum_{i=2}^{6}ic_{i}=6q$ we
obtain $c_{3+}\leq 2q-2s$.

5\. The assertion of Claim 1.4 leads to
$\sum_{i=3}^{6}ic_{i}=\sum_{i=2}^{6}ic_{i}-2c_{2}=6q-2c_{2}\leq 6q-6s$.

6\. A consequence of Claims 1.1, 1.3 and the assumption $s\in[1,7]$.

7\. Since $\mathrm{frq}(M)=2$ (Claim 1.6), by Lemma 6 we get
$\mathrm{exc}(M)=2q+6-(2q+s-1)=7-s$.

8\. We have
$3(2q+s)-c_{2}+c_{4+}=3(c_{2}+c_{3}+c_{4+})-c_{2}+c_{4+}\leq\sum_{i=2}^{6}ic_{i}=6q$
and $c_{4+}\leq c_{2}-3s$.

9\. The inequality is trivial if $r(i,k)=0$. If $\gamma\in\mathbb{R}(i,k)$,
then each colour of $\mathbb{R}(i,k)\setminus\\{\gamma\\}$ contributes one to
the excess of $\gamma$, hence, by Claims 1.6 and 1.7,
$r(i,k)-1\leq\mathrm{exc}(\gamma)=\mathrm{exc}(M)=7-s$ and $r(i,k)\leq 8-s$. ∎

######  Claim 2.

If $\\{i,k\\}\in\binom{[1,6]}{2}$ and $r(i,k)\geq 1$, then
$r(i,k)+r_{3+}(i,k)\leq 8-s$.

Proof. With $\gamma\in\mathbb{R}(i,k)$ each colour of
$(\mathbb{R}(i,k)\setminus\\{\gamma\\})\cup\mathbb{R}_{3+}(i,k)$ makes a
contribution of one to the excess of $\gamma$, hence
$r(i,k)-1+r_{3+}(i,k)\leq\mathrm{exc}(\gamma)=\mathrm{exc}(M)\leq 7-s$, and
the claim follows. $\blacksquare$

######  Claim 3.

If $\\{i,k\\}\in\binom{[1,6]}{2}$, $r(i,k)\geq 1$, $B\subseteq[1,6]$,
$3\leq|B|\leq 4$ and $B\cap\\{i,k\\}=\emptyset$, then $r(B)\leq r^{*}(B)\leq
2|B|$.

Proof. Consider a colour $\gamma\in\mathbb{R}(i,k)$ with
$(M)_{i,j}=(M)_{k,l}=\gamma$ (where, of course, $j\neq l$). If
$\beta\in\mathbb{R}^{*}(B)$, there is $A\subseteq B$ with $|A|\geq 2$ and
$\beta\in\mathbb{R}(A)$. The colour $\beta$ appears in none of the rows $i,k$,
hence the pair $\\{\beta,\gamma\\}$ is good in $M$ only if $\beta$ occupies a
position in the set $\bigcup_{m\in A}\\{(m,j),$
$(m,l)\\}\subseteq\bigcup_{m\in B}\\{(m,j),(m,l)\\}$. As a consequence,
$r^{*}(B)=|\mathbb{R}^{*}(B)|\leq|\bigcup_{m\in B}\\{(m,j),(m,l)\\}|=2|B|$,
and the inequality $r(B)\leq r^{*}(B)$ follows from the fact that
$\mathbb{R}(B)\subseteq\mathbb{R}^{*}(B)$. $\blacksquare$

######  Claim 4.

If $\\{i,j,k,l,m,n\\}=[1,6]$ and $r(i,j,k)\geq 1$, then $r(l,m,n)\leq 9$.

Proof. There is nothing to prove if $\mathbb{R}(l,m,n)=\emptyset$. Further,
with $\alpha\in\mathbb{R}(i,j,k)$ and $\beta\in\mathbb{R}(l,m,n)$ the pair
$\\{\alpha,\beta\\}$ is good in $M$ only if the colour $\beta$ occupies a
position in the 9-element set $\\{l,m,n\\}\times\mathrm{Cov}(\alpha)$.
$\blacksquare$

######  Claim 5.

If $\Delta(G)\geq 4$, then $q\leq 40-5s$.

Proof. Suppose (w) $\Delta(G)=\deg_{G}(1)\geq 4$, and, moreover, let (w) the
sequence $(r(1,k))_{k=2}^{6}$ be nondecreasing. Then $r(1,3)\geq 1$, and there
is $p\in[2,3]$ such that $r(1,p)\geq 1$ and $r(1,k)=0$ for $k\in[2,p-1]$.
Clearly, we have $\mathbb{R}_{3+}(1)=\bigcup_{k=p}^{6}\mathbb{R}_{3+}(1,k)$.
Realise that, by Claim 1.1, $q=|\mathbb{R}(1)|=r_{2}(1)+r_{3+}(1)$. The
inequality $r(1,k)\geq 1$ for $k\in[p,6]$ yields, by Claim 2, $r_{3+}(1,k)\leq
8-s-r(1,k)$; therefore,

$\displaystyle q-r_{2}(1)$
$\displaystyle=r_{3+}(1)=\left|\bigcup_{k=p}^{6}\mathbb{R}_{3+}(1,k)\right|\leq\sum_{k=p}^{6}r_{3+}(1,k)$
$\displaystyle\leq\sum_{k=p}^{6}[8-s-r(1,k)]=(7-p)(8-s)-\sum_{k=p}^{6}r(1,k),$

and then, since $r_{2}(1)=\sum_{k=p}^{6}r(1,k)$, we finish with
$q\leq(7-p)(8-s)\leq 40-5s$. $\blacksquare$

######  Claim 6.

If $\Delta(G)=3$, $\\{i,j,k,l,m,n\\}=[1,6]$, $r(i,l)\geq 1$, $r(j,l)\geq 1$
and $r(k,l)\geq 1$, then $r(l,m,n)\geq q+3s-24$.

Proof. We have $\Delta(G)=\deg_{G}(l)$,
$\mathbb{R}(l,m)=\mathbb{R}(l,n)=\emptyset$,
$\mathbb{R}(l)=\mathbb{R}_{2}(l)\cup\mathbb{R}_{3+}(l)$,
$\mathbb{R}_{2}(l)=\mathbb{R}(i,l)\cup\mathbb{R}(j,l)\cup\mathbb{R}(k,l)$ and
$\mathbb{R}_{3+}(l)=\mathbb{R}(l,m,n)\cup\mathbb{R}_{3+}(i,l)\cup\mathbb{R}_{3+}(j,l)\cup\mathbb{R}_{3+}(k,l)$.
Proceeding similarly as in the proof of Claim 5 leads to
$q-r_{2}(l)=r_{3+}(l)\leq
r(l,m,n)+[8-s-r(i,l)]+[8-s-r(j,l)]+[8-s-r(k,l)]=r(l,m,n)+3(8-s)-r_{2}(l)$,
which yields the desired result. $\blacksquare$

##  5 Main theorem

######  Theorem 9.

If $q\in[41,\infty)$ and $q\equiv 1\pmod{2}$, then $\mathrm{achr}(K_{6}\square
K_{q})=2q+3$.

###### Proof.

We proceed by the way of contradiction. As mentioned in the beginning of
Section 4, we have to show that the existence of a matrix
$M\in\mathcal{M}(6,q,C)$, where $C$ is a $(2q+4)$-element set of colours,
leads to a contradiction. First notice that, by Claim 1, all colours of $C$
are of frequency $l\in[2,6]$, $c_{2}\geq 12$, $c_{3+}\leq 2q-8$,
$\sum_{i=3}^{6}ic_{i}\leq 6q-24$, $\mathrm{frq}(M)=2$, $\mathrm{exc}(M)=3$,
and $\\{i,k\\}\in\binom{[1,6]}{2}$ implies $r(i,k)\leq 4$.

Since $q\geq 41$, from Claim 5 we know that $\Delta(G)\leq 3$ for the
auxiliary graph $G$. Besides that, $\deg_{G}(i)=d$ implies $r_{2}(i)\leq 4d$
for $i\in[1,6]$.

######  Claim 7.

$\Delta(G)\leq 2$.

Proof. If $\Delta(G)=3$, (w) $\deg_{G}(1)=3$, $r(1,4)\geq 1$, $r(1,5)\geq 1$
and $r(1,6)\geq 1$. By Claim 6 we have $r(1,2,3)\geq q-12\geq 29$, and so
Claim 3 yields $r(4,5)=r(4,6)=r(5,6)=0$ (if $r(i,k)\geq 1$ for
$\\{i,k\\}\in\binom{[4,6]}{2}$, then $29\leq r(1,2,3)\leq r^{*}([1,3])\leq
2|[1,3]|=6$, a contradiction). Moreover, $r(4,5,6)=0$, for otherwise, by Claim
4, $30\leq r(1,2,3)+r(4,5,6)\leq 18$, a contradiction.

There is no $i\in[4,6]$ with $\deg_{G}(i)=3$, because then, again by Claim 6,
$r(4,5,6)\geq q-12\geq 29$ in contradiction to Claim 4. So, $\deg_{G}(i)\leq
2$, $i=4,5,6$, $2c_{2}=\sum_{i=1}^{6}r_{2}(i)\leq 3\cdot 12+3\cdot 8=60$ and
$c_{2}\leq 30$. Since $r(1,i)\geq 1$, Claim 3 yields
$r^{*}([2,6]\setminus\\{i\\})\leq 2|2,6]\setminus\\{i\\}|=8$, $i=4,5,6$, and
then $\rho^{*}=\sum_{i=4}^{6}r^{*}([2,6]\setminus\\{i\\})\leq 24$.

It is easy to see that among summands of type $r(A)$ with $A\subseteq[2,6]$,
$2\leq|A|\leq 3$, that appear when counting $\rho^{*}$, each of $r(A)$ with
$A\in\binom{[2,6]}{2}\setminus\\{\\{4,5\\},\\{4,6\\},\\{5,6\\}\\}$ appears at
least twice, and each of $r(A)$ with
$A\in\binom{[2,6]}{3}\setminus\\{\\{4,5,6\\}\\}$ (which is a set belonging to
$C_{3}\setminus\mathbb{R}_{3}(1)$) appears at least once. Because of
$r(4,5)=r(4,6)=r(5,6)=r(4,5,6)=0$ this leads to
$2\sum_{\\{i,k\\}\in\binom{[2,6]}{2}}r(i,k)+c_{3}-r_{3}(1)\leq\rho^{*}\leq
24$, which, having in mind that
$2\sum_{\\{i,k\\}\in\binom{[2,6]}{2}}r(i,k)=2c_{2}-2r_{2}(1)$, yields
$2c_{2}-2r_{2}(1)+c_{3}-r_{3}(1)\leq 24$. Together with the inequality
$r_{2}(1)+r_{3}(1)\leq q$ then $c_{2}+c_{3}\leq q+24+r_{2}(1)-c_{2}\leq q+24$,
$2q+4=|C|=c_{2}+c_{3}+c_{4+}\leq q+24+c_{4+}$, and so $c_{4+}\geq q-20\geq 21$
in contradiction to $c_{4+}\leq c_{2}-12\leq 18$. $\blacksquare$

By Claim 7 each component of $G$ is either a path or a cycle.

######  Claim 8.

No component of the graph $G$ is $K_{2}$.

Proof. Let (w) $G$ have a component $K_{2}$ with vertex set $[1,2]$. Then
$r(1,2)\in[1,4]$ and $r(i,k)=0$ for $(i,k)\in[1,2]\times[3,6]$. Further, (w)
$\mathrm{Cov}(\mathbb{R}(1,2))=[1,n]$ with $n\in[2,8]$.

If $r(1,2)\in[1,3]$, Claim 3 yields
$\rho=\sum_{\\{i,k\\}\in\binom{[3,6]}{2}}r(i,k)\leq r^{*}([3,6])\leq 8$; then
$c_{2}=r(1,2)+\rho\leq 11$, a contradiction.

If $r(1,2)=4$, then $n\geq 4$ and $\rho=|C_{2}\setminus\mathbb{R}(1,2)|=8$. In
the case $n\in[5,8]$ there is $j\in[1,n]$ such that $\mathbb{C}(j)$ contains
at most $\lfloor\frac{2\cdot 8}{n}\rfloor\leq 3$ colours of
$C_{2}\setminus\mathbb{R}(1,2)$. Then, however, for a colour
$\gamma\in\mathbb{R}(1,2)\cap\mathbb{C}(j)$ the number of colours $\delta\in
C_{2}\setminus\mathbb{R}(1,2)$, for which the pair $\\{\gamma,\delta\\}$ is
good in $M$, is at most seven, a contradiction.

Therefore $n=4$, 2-colours occupy all positions in $[1,6]\times[1,4]$,
$c_{2}=12$, $c_{4+}=0$, and all positions in the set $[1,6]\times[5,q]$ are
occupied by 3-colours. Among other things this means that

$c_{3}=\frac{6(q-4)}{3}=2q-8\geq q+(41-8)=q+33,$ (1)

$r_{2}(i)=4$, $r_{3}(i)=q-4$ for $i\in[1,6]$ and $r_{2}(k)\in[1,3]$ for
$k\in[3,6]$.

First, it is clear that $\Delta(G)\leq 2$. Indeed, if (w) $r(3,4)\geq 1$,
$r(3,5)\geq 1$ and $r(3,6)\geq 1$, then each 3-colour occupies a position in
$[1,2]\times[5,q]$ and in $\\{3\\}\times[5,q]$ as well so that $c_{3}\leq
q-4<2q-8$, a contradiction.

Further, if $r(i,k)=4$ for $\\{i,k\\}\in\binom{[3,6]}{2}$, then
$\deg_{G}(m)=1$, $m=3,4,5,6$. Consequently, the subgraph of $G$ induced by the
vertex set $[3,6]$ is $d$-regular for some $d\in[1,2]$.

If $d=1$, then $G$ is isomorphic to $3K_{2}$ and (w) $r(i,i+1)=4$, $i=3,5$.
Clearly, a set $\mathbb{R}(i,j,k)$ with $\\{i,j,k\\}\in\binom{[1,6]}{3}$ can
be nonempty only if $\\{i,j,k\\}\cap\\{l,l+1\\}\neq\emptyset$, $l=1,3,5$. As a
consequence the assumption $\mathbb{R}(i,j,k)\neq\emptyset$ with $i<j<k$
implies $(i,j,k)\in\\{(1,3,5),(1,3,6),(1,4,5),(1,4,6),(2,3,5),$
$(2,3,6),(2,4,5),(2,4,6)\\})$.

Suppose that
$\\{(i_{m},j_{m}):m\in[1,4]\\}=\\{(3,5),(3,6),(4,5),(4,6)\\}=\\{(k_{m},l_{m}):m\in[1,4]\\}$
and $\\{i_{m},j_{m},k_{m},l_{m}\\}=[3,6]$ for $m\in[1,4]$. Then

$c_{3}=\sum_{m=1}^{4}[r(1,i_{m},j_{m})+r(2,k_{m},l_{m})].$ (2)

Further, for $m,n\in[1,4]$ the sets $\\{i_{m},j_{m}\\}$ and
$\\{k_{n},l_{n}\\}$ are disjoint if and only if $m=n$. Put

$\displaystyle T(1)$ $\displaystyle=\\{m\in[1,4]:r(1,i_{m},j_{m})\geq
1\\},\qquad$ $\displaystyle t(1)$ $\displaystyle=|T(1)|,$ $\displaystyle T(2)$
$\displaystyle=\\{m\in[1,4]:r(2,k_{m},l_{m})\geq 1\\},$ $\displaystyle t(2)$
$\displaystyle=|T(2)|$

and $T=T(1)\cap T(2)$. Let

$\sigma(P)=\sum_{p\in P}[r(1,i_{p},j_{p})+r(2,k_{p},l_{p})]$

for $P\subseteq[1,4]$. Using Claim 4 we see that $m\in T(1)$ implies
$r(2,k_{m},l_{m})\leq 9$, while $m\in T(2)$ means that $r(1,i_{m},j_{m})\leq
9$. Therefore, with $m\in T$ we have $r(1,i_{m},j_{m})+r(2,k_{m},l_{m})\leq
9+9=18$, and so $\sigma(T)\leq 18|T|$.

If there is $i\in[1,2]$ with $t(i)=4$, then $q-4=r_{3}(3-i)\leq 4\cdot 9$ and
$q\leq 40$, a contradiction.

If there is $i\in[1,2]$ with $t(i)=1$ and $r(i,i_{m},j_{m})\geq 1$, then
$r_{3}(i)=r(i,i_{m},j_{m})=r_{3}(i_{m})=r_{3}(j_{m})=q-4\geq 37$, hence
$r(3-i,k_{m},l_{m})=r_{3}(3-i)=r_{3}(k_{m})=r_{3}(l_{m})=q-4\geq 37$, which
contradicts Claim 4.

We are left with the situation $t(1),t(2)\in[2,3]$ (and
$|T|\leq\min(t(1),t(2))$). Suppose (w) $t(1)\geq t(2)$.

If $|T|=3$, then $T(1)=T=T(2)$, $[1,4]\setminus T=\\{p\\}$ and
$r(1,i_{p},j_{p})=r(2,k_{p},l_{p})=0$, hence
$2q-8=c_{3}=\sigma([1,4])=\sigma(T)\leq 18\cdot 3=54$ and $q\leq 31$, a
contradiction.

If $|T|=2$, then $n$ out of four summands that sum up to
$\sigma([1,4]\setminus T)$ are positive, $n\leq 2$. Moreover,
$\sigma([1,4]\setminus T)\leq q-4$. The inequality is obvious provided that
$n\leq 1$, while if $n=2$, $a\in T(1)\setminus T(2)$ and $b\in T(2)\setminus
T(1)$, then with $e\in\\{i_{a},j_{a}\\}\cap\\{k_{b},l_{b}\\}$ we have
$\sigma([1,4]\setminus T)=r(1,i_{a},j_{a})+r(2,k_{b},l_{b})\leq r_{3}(e)=q-4$.
Thus $c_{3}=\sigma(T)+\sigma([1,4]\setminus T)\leq 18\cdot 2+(q-4)=q+32$ in
contradiction to (1).

For $|T|=1$ we get $t(2)=2$. With $t(1)=2$ we obtain, similarly as in the case
$|T|=2$, $c_{3}\leq 18+(q-4)=q+14$. So, assume that $t(1)=3$, $T=\\{t\\}$ and
$T(2)\setminus T(1)=\\{p\\}$ (note that $p\neq t$).

Suppose first that $\\{k_{p},l_{p}\\}\neq\\{i_{t},j_{t}\\}$. In such a case
$|\\{k_{p},l_{p}\\}\cap\\{i_{t},j_{t}\\}|=1$; moreover, since
$\\{k_{p},l_{p}\\}\subseteq[3,6]=\\{i_{t},j_{t},k_{t},l_{t}\\}$, we have
$|\\{k_{p},l_{p}\\}\cap\\{k_{t},l_{t}\\}|=1$, and there is $g\in\\{k,l\\}$
such that $\\{k_{p},l_{p}\\}\cap\\{k_{t},l_{t}\\}=\\{g_{t}\\}$. Then five from
among eight summands in (2) are positive, namely $r(1,i_{t},j_{t})$,
$r(2,k_{t},l_{t})$, $r(2,k_{p},l_{p})$ and $r(1,i_{m},j_{m})$ with
$m\in[1,4]\setminus\\{t,p\\}$. Having in mind that
$g_{t}\notin\\{i_{t},j_{t}\\}$, $g_{t}\notin\\{i_{p},j_{p}\\}$, and each
element of $[3,6]$ is involved in exactly two of the ordered pairs
$(3,5),(3,6),(4,5)$, $(4,6)$, we see that except for $r(1,i_{t},j_{t})$ all
mentioned positive summands correspond to colours of $\mathbb{R}_{3}(g_{t})$.
That is why $c_{3}\leq r(1,i_{t},j_{t})+r_{3}(g_{t})\leq 9+(q-4)=q+5$, a
contradiction to (1) again.

On the other hand, if $\\{k_{p},l_{p}\\}=\\{i_{t},j_{t}\\}$, then
$|\\{i_{p},j_{p}\\}\cap\\{i_{t},j_{t}\\}|=|\\{i_{p},j_{p}\\}\cap\\{k_{p},l_{p}\\}|=0$,
hence for $m\in[1,4]\setminus\\{t,p\\}$ we have
$|\\{i_{m},j_{m}\\}\cap\\{i_{t},j_{t}\\}|=1$, and so positive summands in (2)
are $r(1,i_{t},j_{t})$, $r(2,k_{t},l_{t})$,
$r(2,k_{p},l_{p})=r(2,i_{t},j_{t})$, $r(1,g_{t},k_{t})$ and
$r(1,h_{t},l_{t})$, where $\\{g,h\\}=\\{i,j\\}$. Then

$\displaystyle q-4$
$\displaystyle=r_{3}(2)=r(2,k_{t},l_{t})+r(2,i_{t},j_{t}),$ $\displaystyle
q-4$ $\displaystyle=r_{3}(k_{t})=r(2,k_{t},l_{t})+r(1,g_{t},k_{t}),$

which yields

$r(2,i_{t},j_{t})=r(1,g_{t},k_{t})=q-4-r(2,k_{t},l_{t})\geq(q-4)-9=q-13$

so that

$q-4=r_{3}(g_{t})=r(1,i_{t},j_{t})+r(1,g_{t},k_{t})+r(2,i_{t},j_{t})\geq
1+2(q-13)$

and $q\leq 21$, a contradiction.

If $|T|=0$, then $t(1)=t(2)=2$, and, by symmetry, $T(1)=[1,2]$, $T(2)=[3,4]$.
We have $\\{i_{1},j_{1}\\}\cup\\{i_{2},j_{2}\\}=[3,6]$, for otherwise there is
$e\in[3,6]\setminus(\\{i_{1},j_{1}\\}\cup\\{i_{2},j_{2}\\})$, hence
$e\in\\{i_{3},j_{3}\\}\cap\\{i_{4},j_{4}\\}$,
$e\notin\\{k_{3},l_{3}\\}\cup\\{k_{4},l_{4}\\}$ and $r_{3}(e)=0\neq q-4$, a
contradiction. Thus, by symmetry we may assume that $i_{1}=3<i_{2}=4$.

Therefore, (w) $(i_{1},j_{1})=(3,5)$ and $(i_{2},j_{2})=(4,6)$, which means
that $r(m,n,p)$ with $\\{m,n,p\\}\in\binom{[1,6]}{3}$ and $m<n<p$ is positive
if and only if $(m,n,p)\in\\{(1,3,5),(1,4,6),(2,3,6),(2,4,5)\\}$. We have
$r_{3}(6)=r(1,4,6)+r(2,3,6)=q-4\equiv 1\pmod{2}$, hence

$r(1,4,6)\not\equiv r(2,3,6)\pmod{2}.$ (3)

Similarly, from $r_{3}(1)=q-4=r_{3}(3)$ it follows that $r(1,3,5)\not\equiv
r(1,4,6)\pmod{2}$ and $r(1,3,5)\not\equiv r(2,3,6)\pmod{2}$ so that
$r(1,4,6)\equiv r(2,3,6)\pmod{2}$, which contradicts (3).

If $d=2$, $G$ has a 4-cycle component, (w)
$\\{\\{3,4\\},\\{4,5\\},\\{5,6\\},\\{6,3\\}\\}\subseteq E(G)$. The
completeness of $f_{M}$ implies
$C_{3}\subseteq\mathbb{R}(1,3,5)\cup\mathbb{R}(1,4,6)\cup\mathbb{R}(2,3,5)\cup\mathbb{R}(2,4,6)$.
So,

$c_{3}=[r(1,3,5)+r(2,4,6)]+[r(1,4,6)+r(2,3,5)].$

Let $\bar{\mathcal{T}}=\\{(1,3,5),(1,4,6),(2,3,5),(2,4,6)\\}$,

$\mathcal{T}=\\{(i,j,k)\in\bar{\mathcal{T}}:r(i,j,k)\geq 1\\}$

and $t=|\mathcal{T}|$. From $r_{3}(i)=q-4>0$ for $i\in[1,6]$ it follows that
$t\geq 2$. If $(i,j,k),(l,m,n)\in\mathcal{T}$, $(i,j,k)\neq(l,m,n)$, then
either $r(i,j,k)+r(l,m,n)\leq 9+9=18$ (by Claim 4, if
$\\{i,j,k\\}\cap\\{l,m,n\\}=\emptyset$) or $r(i,j,k)+r(l,m,n)\leq
r_{3}(p)=q-4$ (if $p\in\\{i,j,k\\}\cap\\{l,m,n\\}$). As a consequence then
$c_{3}\leq b_{t}$, where $b_{2}=q-4$, $b_{3}=18+(q-4)=q+14$ and
$b_{4}=18+18=36$. Thus $c_{3}\leq\max(b_{2},b_{3},b_{4})=q+14$, which
contradicts (1). $\blacksquare$

######  Claim 9.

No component of the graph $G$ is $K_{3}$.

Proof. Let (w) $G$ have the component $K_{3}$ with the vertex set $[1,3]$.

If $G=K_{3}\cup 3K_{1}$, then $r(1,2)=r(1,3)=r(2,3)=4$, $c_{2}=12$ and
$c_{4+}=0$. From Claim 2 it follows that $r_{3+}(1,3)=0=r_{3+}(2,3)$, hence
$r(3,i,k)\geq 1$ with $\\{i,k\\}\in\binom{[1,6]\setminus\\{3\\}}{2}$ implies
$\\{i,k\\}\in\\{\\{4,5\\},\\{4,6\\},\\{5,6\\}\\}$. By Claim 3 then
$r_{3}(3)=r(3,4,5)+r(3,4,6)+r(3,5,6)\leq r^{*}([3,6])\leq 8$, hence
$q=r_{2}(3)+r_{3}(3)\leq(4+4)+8=16$, a contradiction.

If $G$ has besides the above $K_{3}$ another nontrivial component (of order at
least 2) and $r(i,k)\geq 1$ with $\\{i,k\\}\in\binom{[4,6]}{2}$, then, by
Claim 3, $r(1,2)+r(1,3)+r(2,3)\leq r^{*}([1,3])\leq 6$ and
$r(4,5)+r(4,6)+r(5,6)\leq r^{*}([4,6])\leq 6$, hence $12\leq c_{2}\leq 6+6$,
$c_{2}=12$, $r(1,2)+r(1,3)+r(2,3)=r(4,5)+r(4,6)+r(5,6)=6$, $c_{4+}=0$ and
$c_{3}=2q-8$. It is easy to see that in such a case 2-colours fill in four
columns of $M$ and $G=2K_{3}$. Consequently, $\mathbb{R}(i,j,k)$ can be
nonempty only if $\\{i,j,k\\}\in\\{[1,3],[4,6]\\}$. Since $41\leq
q=r_{2}(i)+r_{3}(i)=4+r_{3}(i)$ for $i\in[1,6]$, we have $r(1,2,3)\geq 37$ and
$r(4,5,6)\geq 37$, which contradicts Claim 4. $\blacksquare$

######  Claim 10.

No component of the graph $G$ is a path of order at least $3$.

Proof. Suppose that $G$ has a path component $P$ of order at least $3$.

If $G$ has besides $P$ another nontrivial component (of order at least $2$),
then $G=P\cup P^{\prime}$, where, by Claims 8 and 9, both $P$ and $P^{\prime}$
are paths of order 3, (w) $V(P)=[1,3]$, $V(P^{\prime})=[4,6]$ and
$r(i,i+1)\geq 1$ for $i=1,2,4,5$. Similarly as in the proof of Claim 9 it is
easy to see that $r(1,2)+r(2,3)=r(4,5)+r(5,6)=6$. Since $r_{2}(2)=6$, there
are colours $\alpha,\beta\in\mathbb{R}(1,2)\cup\mathbb{R}(2,3)$ such that
$\mathrm{Cov}(\alpha)\cap\mathrm{Cov}(\beta)=\emptyset$. Then each colour of
$\mathbb{R}(4,5)\cup\mathbb{R}(5,6)$ occupies a position in
$[4,6]\times\mathrm{Cov}(\alpha)$ and a position in
$[4,6]\times\mathrm{Cov}(\beta)$ as well so that
$\mathrm{Cov}(\mathbb{R}(4,5)\cup\mathbb{R}(5,6))\subseteq\mathrm{Cov}(\alpha,\beta)$;
this leads to a contradiction since
$\mathrm{cov}(\mathbb{R}(4,5)\cup\mathbb{R}(5,6))\geq r_{2}(5)=6$ and
$\mathrm{cov}(\alpha,\beta)=4$.

So, $P$ is the unique nontrivial component of $G$, (w) $V(P)=[1,p]$ and
$E(P)=\\{\\{i,i+1\\}:i\in[1,p-1]\\}$. Since $12\leq
c_{2}=\sum_{i=1}^{p-1}r(i,i+1)\leq 4(p-1)$, we have $p\in[4,6]$.

If $p=4$, then $r(i,i+1)=4$, $i=1,2,3$, $c_{2}=12$, $c_{4+}=0$ and

$i\in[1,6]\Rightarrow r_{3}(i)=q-r_{2}(i)\geq q-8\geq 33.$ (4)

It is easy to see that $\mathrm{cov}(\mathbb{R}(1,2)\cup\mathbb{R}(3,4))=4$,
(w) $\mathrm{Cov}(\mathbb{R}(1,2)\cup\mathbb{R}(3,4))=[1,4]$. Further, colours
of $\mathbb{R}(1,2)\cup\mathbb{R}(3,4)$ occupy all positions in
$[1,4]\times[1,4]$, hence (w) $\mathrm{Cov}(\mathbb{R}(2,3))=[5,n]$, where
$n\in[8,12]$.

By Claim 2 we know that $r(i,j,k)=0$ if there is $l\in[1,3]$ such that
$\\{l,l+1\\}\subseteq\\{i,j,k\\}$.

Suppose that $\gamma\in\mathbb{R}(1,5,6)$. Since all pairs
$\\{\gamma,\delta\\}$ with $\delta\in\mathbb{R}(3,4)$ are good in $M$, two
positions in $[5,6]\times[1,4]$ must be occupied by $\gamma$. Then, however,
the number of pairs $\\{\gamma,\varepsilon\\}$ with
$\varepsilon\in\mathbb{R}(2,3)$ that are good in $M$ is at most two, a
contradiction. So, $r(1,5,6)=0$, and an analogous reasoning shows that
$r(4,5,6)=0$.

Claim 3 yields $r(1,4,5)+r(1,4,6)\leq r^{*}(\\{1,4,5,6\\})\leq 8$. A colour
$\gamma\in\mathbb{R}(2,5,6)$ as well as a colour $\delta\in\mathbb{R}(3,5,6)$
occupies two positions in $[5,6]\times[1,4]$ (each pair
$\\{\gamma,\varepsilon\\}$ with $\varepsilon\in\mathbb{R}(3,4)$ and each pair
$\\{\delta,\zeta\\}$ with $\zeta\in\mathbb{R}(1,2)$ is good in $M$). Thus
$r(2,5,6)+r(3,5,6)\leq 4$ and

$r(1,4,5)+r(1,4,6)+r(2,5,6)+r(3,5,6)\leq 12.$ (5)

The set of remaining triples $(i,j,k)\in[1,6]^{3}$ with $i<j<k$ such that
$r(i,j,k)$ can be positive is
$\mathcal{T}=\\{(1,3,5),(1,3,6),(2,4,5),(2,4,6)\\}$. Suppose that
$r(i,j,k)\geq 1$ with $(i,j,k)\in\mathcal{T}$ if and only if
$(i,j,k)\in\\{(i_{l},j_{l},k_{l}):l\in[1,t]\\}$. We show that there is
$m\in[1,6]$ with $r_{3}(m)\leq 30$ in contradiction to (4).

If $t=4$, then, by Claim 4, $r(i_{l},j_{l},k_{l})\leq 9$, $l=1,2,3,4$, and so,
using (5), $r_{3}(m)\leq 12+2\cdot 9=30$ for (any) $m\in[1,6]$. If $t=3$ and
$r(i,j,k)=0$ for $(i,j,k)\in\mathcal{T}$, then $r_{3}(m)\leq 12+9=21$ for
$m\in\\{i,j,k\\}$. The same upper bound applies for $m\in[1,6]$ if $t=2$ and
$\\{i_{1},j_{1},k_{1}\\}\cap\\{i_{2},j_{2},k_{2}\\}=\emptyset$.

If $t=2$ and
$\\{i_{1},j_{1},k_{1}\\}\cap\\{i_{2},j_{2},k_{2}\\}\neq\emptyset$, for
$m\in[1,6]\setminus(\\{i_{1},j_{1},k_{1}\\}\cup\\{i_{2},j_{2},k_{2}\\})$ we
obtain $r_{3}(m)\leq 12$. The same inequality is available for
$m\in[1,6]\setminus\\{i_{1},j_{1},k_{1}\\}$ if $t=1$ and for $m\in[1,6]$ if
$t=0$.

If $p=5$, then, by Claim 3, from $r(4,5)\geq 1$ it follows that
$r(1,2)+r(2,3)\leq r^{*}([1,3])\leq 6$; similarly, $r(1,2)\geq 1$ yields
$r(3,4)+r(4,5)\leq r^{*}([3,5])\leq 6$. Then $12\leq
c_{2}=\sum_{i=1}^{4}r(i,i+1)\leq 6+6$, $c_{2}=12$ and
$r(1,2)+r(2,3)=6=r(3,4)+r(4,5)$. If $(M)_{1,j}=\gamma\in\mathbb{R}(1,2)$, then
all positions in $[3,5]\times\mathrm{Cov}(\gamma)$ are occupied by six
distinct colours of $\mathbb{R}(3,4)\cup\mathbb{R}(4,5)$, hence
$(M)_{3,j}\in\mathbb{R}(3,4)$ and $\delta=(M)_{5,j}\in\mathbb{R}(4,5)$.
Analogously, all positions in $[1,3]\times\mathrm{Cov}(\delta)$ are occupied
by six distinct colours of $\mathbb{R}(1,2)\cup\mathbb{R}(2,3)$, which implies
$(M)_{3,j}\in\mathbb{R}(2,3)$, a contradiction.

If $p=6$, then, by Claim 3, $r^{*}([1,6]\setminus[l,l+1])\leq 8$ for
$l\in[1,5]$, hence

$\rho^{*}=\sum_{l=1}^{5}r^{*}([1,6]\setminus[l,l+1])\leq 40.$ (6)

It is easy to see that in the sum $\rho^{*}$ each of the summands $r(i,i+1)$
with $i\in[1,5]$ appears in the expression of $r^{*}([1,6]\setminus[l,l+1])$
for at least two $l$’s, while each of the summands $r(i,j,k)$ satisfying
$\\{i,j,k\\}\in\binom{[1,6]}{3}\setminus\\{\\{1,3,5\\},\\{2,3,5\\},$
$\\{2,4,5\\},\\{2,4,6\\}\\}$ and $i<j<k$ appears for at least one $l$. Since
$c_{2}=\sum_{l=1}^{5}r(l,l+1)$, with

$\rho=r(1,3,5)+r(2,3,5)+r(2,4,5)+r(2,4,6)$

the inequality (6) leads to

$2c_{2}+c_{3}-\rho\leq\rho^{*}\leq 40.$ (7)

Moreover, $r_{2}(l)+r_{3}(l)\leq q$ implies

$r_{3}(l)\leq q-r_{2}(l)=q-[r(l-1,l)+r(l,l+1)]\leq q-2,\ l=2,5,$

and so, having in mind that, by Claim 4, $\min(r(1,3,5),r(2,4,6))\leq 9$,

$\displaystyle\rho$
$\displaystyle\leq\min(r_{3}(2)+r(1,3,5),r_{3}(5)+r(2,4,6))$
$\displaystyle\leq q-2+\min(r(1,3,5),r(2,4,6))\leq q+7.$ (8)

Since, by Claim 1.8, $c_{4+}-c_{2}\leq-12$, using (7)–(5) we obtain

$2q+4=c_{2}+c_{3}+c_{4+}\leq 40+\rho+c_{4+}-c_{2}\leq 40+(q+7)-12=q+35,$

and, finally, $q\leq 31$, a contradiction. $\blacksquare$

With $l\in\mathbb{Z}$ and $m\in[2,\infty)$ we use $(l)_{m}$ to denote
$n\in[1,m]$ satisfying $n\equiv l\pmod{m}$.

######  Claim 11.

No component of the graph $G$ is a $4$-cycle.

Proof. If $G$ has a 4-cycle component, (w) $r(i,(i+1)_{4})\geq 1$ for
$i\in[1,4$]. Note that, by Claim 8, $r(5,6)=0=r_{2}(5)=r_{2}(6)$. Let
$i\in[1,4]$ and

$P_{i}=\\{((i+2)_{4},5),((i+2)_{4},6),(5,6)\\}.$

Since evidently

$\mathbb{R}_{3+}(i)=\mathbb{R}(i,(i+2)_{4},5,6)\cup\bigcup_{j\in\\{(i-1)_{4},i\\}}\mathbb{R}_{3+}(j,(j+1)_{4})\cup\bigcup_{(j,k)\in
P_{i}}\mathbb{R}(i,j,k),$

by Claim 2 we have

$\displaystyle r_{3+}(i)$ $\displaystyle\leq
r(i,(i+2)_{4},5,6)+\sum_{j\in\\{(i-1)_{4},i\\}}r_{3+}(j,(j+1)_{4})+\sum_{(j,k)\in
P_{i}}r(i,j,k)$ $\displaystyle\leq
r(i,(i+2)_{4},5,6)+\sum_{j\in\\{(i-1)_{4},i\\}}[4-r(j,(j+1)_{4})]+\sum_{(j,k)\in
P_{i}}r(i,j,k).$

Therefore, realising that

$\sum_{i=1}^{4}\sum_{j\in\\{(i-1)_{4},i\\}}r(j,(j+1)_{4})=\sum_{i=1}^{4}r_{2}(i),$

we obtain

$\sum_{i=1}^{4}r_{3+}(i)\leq
32+\sum_{i=1}^{4}\left[r(i,(i+2)_{4},5,6)+\sum_{(j,k)\in
P_{i}}r(i,j,k)\right]-\sum_{i=1}^{4}r_{2}(i).$ (9)

On the right-hand side of the inequality (9) there are among others (partial)
summands $r(A)$ with $A\in\binom{[1,6]}{3}\cup\binom{[1,6]}{4}$, each such
summand appears there with the frequency 0, 1 or 2, and the frequency is 2 if
and only if
$A\in\\{\\{1,3,5\\},\\{1,3,6\\},\\{2,4,5\\},\\{2,4,6\\},\\{1,3,5,6\\},\\{2,4,5,6\\}\\}$.
Thus, with

$\displaystyle\rho_{3}$ $\displaystyle=r(1,3,5)+r(1,3,6)+r(2,4,5)+r(2,4,6),$
$\displaystyle\rho_{4}$ $\displaystyle=r(1,3,5,6)+r(2,4,5,6)$

the inequality (9) leads to

$4q=\sum_{i=1}^{4}[r_{2}(i)+r_{3+}(i)]\leq 32+\rho_{3}+\rho_{4}+c_{3}+c_{4}.$
(10)

Let us show that

$\rho_{3}\leq q+10.$ (11)

To see it let $a$ be the number of sets $A$ belonging to

$\mathcal{A}=\\{\\{1,3,5\\},\\{1,3,6\\},\\{2,4,5\\},\\{2,4,6\\}\\}$

with $r(A)\geq 1$.

If $a=4$, by Claim 4 we have $\rho_{3}\leq 4\cdot 9=36\leq q+10$.

In the case $a=3$ there is $i\in[1,4]$ such that $\rho_{3}\leq 2\cdot
9+r_{3}(i)$. Evidently, $r_{3}(i)\leq
q-r_{2}(i)=q-[r((i-1)_{4},i)+r(i,(i+1)_{4})]\leq q-(4+4)=q-8$, hence
$\rho_{3}\leq q+10$.

If $a=2$, let the positive summands of $\rho_{3}$ be $r(i,j,k)$ and
$r(l,m,n)$, $\\{i,j,k\\}\neq\\{l,m,n\\}$. If
$\\{i,j,k\\}\cap\\{l,m,n\\}=\emptyset$, then $\rho_{3}\leq 2\cdot 9\leq q+10$,
and otherwise, with $p\in\\{i,j,k\\}\cap\\{l,m,n\\}$, we have $\rho_{3}\leq
r_{3}(p)\leq q$.

If $a\in[0,1]$, then $\rho_{3}\leq q-2$, since $r(i,j,k)\geq 1$ with
$\\{i,j,k\\}\in\mathcal{A}$ and $i<j<k$ implies $i\in[1,2]$, while
$r_{2}(i)\geq 1+1$.

Now realise that, by Claim 1.8, $\rho_{4}+c_{3}+c_{4}\leq
c_{3}+2c_{4+}=|C|+(c_{4+}-c_{2})\leq(2q+4)-12=2q-8$, and so, using (10) and
(11), $4q\leq 32+(q+10)+(2q-8)=3q+34$ and $q\leq 34$, a contradiction.
$\blacksquare$

######  Claim 12.

No component of the graph $G$ is a $5$-cycle.

Proof. If $G$ has a 5-cycle component, (w) $r(i,(i+1)_{5})\geq 1$ for
$i\in[1,5]$. Similarly as in the proof of Claim 11 for $i\in[1,5]$ we get

$r_{3+}(i)\leq
r((i-2)_{5},i,(i+2)_{5},6)+\sum_{j\in\\{(i-1)_{5},i\\}}r_{3+}(j,(j+1)_{5})+\sum_{(j,k)\in
P_{i}}r(i,j,k),$

this time with

$P_{i}=\\{((i-2)_{5},6),((i+2)_{5},6),((i-2)_{5},(i+2)_{5})\\},$

which yields

$5q=\sum_{i=1}^{5}[r_{2}(i)+r_{3+}(i)]\leq 40+\rho_{3}+c_{3}+c_{4},$ (12)

where

$\rho_{3}=r(1,3,6)+r(1,4,6)+r(2,4,6)+r(2,5,6)+r(3,5,6)\leq r_{3}(6)\leq q.$
(13)

Moreover, $c_{3}+c_{4}\leq 2q+4-c_{2}\leq 2q-8$, and so, using (12) and (13),
$5q\leq 40+q+(2q-8)=3q+32$ and $q\leq 16$, a contradiction. $\blacksquare$

######  Claim 13.

The graph $G$ is not a $6$-cycle.

Proof. If $G$ is a 6-cycle, (w) $r(i,(i+1)_{6})\geq 1$ for $i\in[1,6]$. In
this case $r_{3+}(i)$ is upper bounded by

$r((i-2)_{6},i,(i+2)_{6},(i+3)_{6})+\sum_{j\in\\{(i-1)_{6},i\\}}[4-r(j,(j+1)_{6})]+\sum_{(j,k)\in
P_{i}}r(i,j,k)$

with

$P_{i}=\\{((i-2)_{6},(i+2)_{6}),((i-2)_{6},(i+3)_{6}),((i+2)_{6},(i+3)_{6})\\},$

and one can see that

$6q\leq 48+\rho_{3}+c_{3}+c_{4},$ (14)

where $\rho_{3}=2r(1,3,5)+2r(2,4,6)$. We can bound $\rho_{3}$ from above by
$2q-4$. Indeed, if both $r(1,3,5)$ and $r(2,4,6)$ are positive, then Claim 4
yields $\rho_{3}\leq 18+18=36\leq 2q-4$. On the other hand, if $r(i,j,k)=0$
with $(i,j,k)\in\\{(1,3,5),(2,4,6)\\}$, then $\rho_{3}\leq 2r_{3}(i+1)\leq
2[q-r_{2}(i+1)]=2q-2[r_{2}(i,i+1)+r_{2}(i+1,i+2)]\leq 2q-4$. Therefore,
similarly as in the proof of Claim 12, from (14) we obtain $6q\leq
48+(2q-4)+(2q-8)=4q+36$ and $q\leq 18$, a contradiction. $\blacksquare$

Thus, by Claims 7–13, we conclude that $G=6K_{1}$ and $c_{2}=0$, which
contradicts Claim 1.3. Therefore, Theorem 9 is proved. ∎

Acknowledgements

This work was supported by the Slovak Research and Development Agency under
the contract APVV-19-0153.

## References

  * [1] A. Bouchet, Indice achromatique des graphes multiparti complets et réguliers, Cahiers du Centre d’Études de Recherche Opérationelle 20 (1978) 331–340.
  * [2] N. Cairnie, K.J. Edwards, The achromatic number of bounded degree trees, Discrete Math. 188 (1998) 87–97.
  * [3] G. Chartrand, P. Zhang, Chromatic Graph Theory, CRC Press, Boca Raton, 2009.
  * [4] N.P. Chiang, H.L. Fu, On the achromatic number of the cartesian product $G_{1}\times G_{2}$, Australas. J. Combin. 6 (1992) 111–117.
  * [5] N.P. Chiang, H.L. Fu, The achromatic indices of the regular complete multipartite graphs, Discrete Math. 141 (1995) 61–66.
  * [6] K.J. Edwards, The harmonious chromatic number and the achromatic number, in: R.A. Bailey (Ed.), Surveys in Combinatorics (Invited papers for 16th British Combinatorial Conference), Cambridge University Press, Cambridge, 1997, pp. 13–47.
  * [7] K.J. Edwards, A Bibliography of Harmonious Colourings and Achromatic Number, staff.computing.dundee.ac.uk/kedwards/biblio.html.
  * [8] F. Harary, S. Hedetniemi, G. Prins, An interpolation theorem for graphical homomorphisms, Portug. Math. 26 (1967) 454–462.
  * [9] P. Hell, D.J. Miller, Achromatic numbers and graph operations, Discrete Math. 108 (1992) 297–305.
  * [10] F. Hughes, G. MacGillivray, The achromatic number of graphs: a survey and some new results, Bull. Inst. Combin. Appl. 19 (1997) 27–56.
  * [11] M. Horňák, Š. Pčola, Achromatic number of $K_{5}\times K_{n}$ for large $n$, Discrete Math. 234 (2001) 159–169.
  * [12] M. Horňák, Š. Pčola, Achromatic number of $K_{5}\times K_{n}$ for small $n$, Czechoslovak Math. J. 53 (2003) 963–988.
  * [13] M. Horňák, J. Puntigán, On the achromatic number of $K_{m}\times K_{n}$, in: M. Fiedler (Ed.), Graphs and Other Combinatorial Topics, Teubner, Leipzig, 1983, pp. 118–123.
  * [14] W. Imrich, S. Klavžar, Product Graphs, Wiley-Interscience, New York, 2000.