figure table

# Instrument Signature Removal and Calibration Products for the Rubin Legacy
Survey of Space and Time

Andrés A. Plazas Malagón  SLAC National Accelerator Laboratory, Menlo Park,
CA, USA  Kavli Institute for Particle Astrophysics and Cosmology, Stanford
University, Stanford, CA, USA  Chris Waters  Department of Astrophysical
Sciences, Princeton University, Princeton, NJ, USA  Alex Broughton  Department
of Physics and Astronomy, University of California-Irvine, Irvine, California,
USA 92617  Eli Rykoff  SLAC National Accelerator Laboratory, Menlo Park, CA,
USA  Kavli Institute for Particle Astrophysics and Cosmology, Stanford
University, Stanford, CA, USA  Agnès Ferté  SLAC National Accelerator
Laboratory, Menlo Park, CA, USA  Kavli Institute for Particle Astrophysics and
Cosmology, Stanford University, Stanford, CA, USA  Merlin Fisher-Levine  Rubin
Observatory Project Office, 950 N. Cherry Ave., Tucson, AZ, USA  Robert Lupton
Department of Astrophysical Sciences, Princeton University, Princeton, NJ, USA

###### Abstract

The Vera C. Rubin Legacy Survey of Space and Time (LSST) will conduct an
unprecedented optical survey of the southern sky, imaging the entire available
sky every few nights for 10 years. To achieve its ambitious science goals of
probing dark energy and dark matter, mapping the Milky Way, and exploring the
transient optical sky, the systematic errors in the LSST data must be
exquisitely controlled. Instrument signature removal (ISR) is a critical early
step in LSST data processing to remove inherent camera effects from the raw
images and produce accurate representations of the incoming light. This paper
describes the current state of the ISR pipelines implemented in the LSST
Science Pipelines software. The key steps in ISR are outlined and the process
of generating and verifying the necessary calibration products to carry out
ISR is also discussed. Finally, an overview is given of how the Rubin data
management system utilizes a data Butler and calibration collections to
organize datasets and match images to appropriate calibrations during
processing. Precise ISR will be essential to realize the potential of LSST to
revolutionize astrophysics.

###### keywords:

CCDs, algorithms, software, calibration, galaxy surveys

*Andrés A. Plazas Malagón<EMAIL_ADDRESS>
##  1 Introduction

The Vera C. Rubin Observatory, currently under construction on Cerro Pachón in
Chile, will undertake the Legacy Survey of Space and Time (LSST) using the
state-of-the-art Simonyi Survey Telescope. With an 8.4-meter primary mirror
and a 3.2-gigapixel camera (LSSTCam), the LSST aims to conduct an
unprecedented survey of over 18,000 square degrees of the southern sky using
six different filters spanning the optical and near-infrared spectrum. The
LSST has four main science goals: probing dark energy and dark matter,
creating an inventory of the solar system, exploring the transient optical
sky, and inferring the structure and evolution of the Milky Way galaxy[1]. To
achieve these goals, the LSST area will be observed more than 800 in 10 years.

To attain the precision necessary for these ambitious science goals, the
systematic errors in the LSST data must be exquisitely controlled. The raw
data from the camera contain inherent instrument signatures from effects like
bias levels, dark current, and amplifier noise. Instrument signature removal
(ISR) is a critical early step in LSST data processing, aimed at removing
these camera-induced effects to produce accurate representations of the
incoming light. This process includes using specific calibration images and
corrections to eliminate the instrument’s effects from the raw data.

The focal plane of the LSSTCam consists of 189 thick (100 microns), fully-
depleted, back-illuminated science Charge-Coupled Devices (CCDs) [2, 3, 4], in
addition to 8 CCDs for guiding and 4 split CCDs for wavefront measurements [5,
6]. The science CCDs are arranged in 21 rafts, each powering and controlling
nine CCDs. Each CCD is divided into sixteen segments, each with a separate
readout register and amplifier, for low-noise, fast parallel readout,
resulting in 3024 image segments for the science detectors. The LSSTCam focal
plane contains CCDs fabricated by two vendors, the ITL STA3800C from the
University of Arizona Imaging Technology Laboratory (ITL), [7]
111https://www.itl.arizona.edu/ and the E2V CCD250 from Teledyne E2V.
222https://www.teledyneimaging.com/en/aerospace-and-defense/products/sensors-
overview/ccd/ccd250-82/ With 201 CCDs in the camera, ISR for LSST is a
challenging task.

This paper is structured as follows: Section 2 describes the steps in ISR
currently implemented in the LSST Science Pipelines [8, 9] codebase, including
steps planned for future development . Section 3 describes the generation,
construction, and verification process of the necessary calibrations for ISR
in the LSST. Section 4 concludes with a general description of the Rubin data
management paradigm and how the pipelines are constructed and executed.

Figure 1: Example of an image before and after partial Instrument Signature
Removal (bias, dark, and flat applied).

##  2 Instrument Signature Removal for the LSST

Figure 1 shows an example of an image before and after partial ISR processing,
with applied bias, dark, and flat-field images. The full sequence of ISR steps
to go from a raw image in Analog-to-Digital Units (ADU) to a post-ISR image in
e- is displayed in Figure 2 and presented in the following subsections,
including steps not yet implemented in our pipelines (in red and dashed in
Figure 2 and signaled with an asterisk in the subsection title). This is the
status of the current ISR algorithms as of version w_2024_13 of the LSST
Science Pipelines.333The ISR code can be found at
https://github.com/lsst/ip_isr.

Figure 2: ISR steps and necessary calibration products. Units are displayed in
each box, and the steps in red and enclosed in dashed lines are in the process
of being implemented. Flowchart based on discussions at Rubin Calibration
Workshop at SLAC, October 2023.

###  2.1 Input validation

The ISR task receives as input _raw_ , unassembled images in Analog-to-Digital
(ADU) units. The task then validates that it has the necessary input
calibration files to perform the requested ISR steps in the task configuration
file.

###  2.2 Differential non-linearity correction*

Differential non-linearity (DNL) in the CCD analog-to-digital converter (ADC)
occurs when there is a bias toward the digital output values (0 or 1).
Ideally, no ADC levels should be “narrow” or “wide”. To incorporate DNL
correction into the ISR pipelines, correction algorithms can be defined to
generate look-up tables for each potential signal level in ADU.

###  2.3 Correction of the serial overscan

The ISR task performs a serial overscan correction (the overscan being extra
readouts of the serial register after a row has been read out) to remove
amplifier bias levels, which may be unstable with time. For LSSTCam, the
routine is set to define the overscan correction as the population median per
row (MEDIAN_PER_ROW), but other correction options are available (e.g., via
the mean of the overscan region or spline fits). The first three columns of
the overscan are skipped to mitigate the impact of deferred charges (the
number of columns to skip is configurable).

As with other ISR steps, future versions of the code will allow this process
to be configured per detector and amplifier.

###  2.4 Bad amplifier and SATURATED/SUSPECT pixel masking

After serial overscan correction, pixels flagged as SATURATED and SUSPECT are
masked. The appropriate definition of saturation is still under consideration.
Potential definitions include the mean pixel full-well, the Photon-Transfer
Curve (PTC[10]) turnoff, the level at which serial or parallel Charge Transfer
Inefficiency (CTI) exceeds requirements, the maximum observed level in a given
pixel, and the level at which detectors exhibit significant persistence[11].

###  2.5 Correction of the crosstalk from the image to the parallel overscan
region and parallel overscan correction

For certain amplifiers, parallel overscan subtraction (the overscan being
extra readouts of the serial register after the last row of the image has been
read out ) is necessary. However, columns affected by hot pixels and saturated
sources may bleed into the parallel overscan region, requiring them to be
masked and interpolated along the columns. Additionally, these high signals
induce electronic crosstalk (see section 2.7 below) into overscan regions of
other amplifiers, necessitating crosstalk correction of the overscan region.
Following these corrections, the ISR task performs the column-by-column
parallel overscan correction.

###  2.6 Linearity correction

Signal-chain non-linearity in the LSSTCam detectors[12] is corrected per
amplifier, and the correction is derived from a dataset used to calculate the
PTC: a set of flat-field images (flat pairs) at different flux levels,
monitored by a photodiode. All non-linearity corrections are defined in terms
of an additive correction, such that:

$\textrm{corrected value}=\textrm{uncorrected value}+f(\text{uncorrected
value})$

There are currently multiple options for the correction function $f$,
including a lookup table, a polynomial function in which a polynomial is used
to approximate the inverse of the response function[13], and a spline fit. The
current configuration file for LSSTCam employs a multi-node spline 444As
proposed by P. Astier (LPNH, (IN2P3/CNRS)).

###  2.7 Correction of the crosstalk between amplifiers

Crosstalk in LSSTCam detectors refers to the phenomenon where a signal from
one amplifier “leaks” into another. This is a significant concern due to the
highly parallelized readout of LSST’s focal plane, which is designed to read
out 3.2 Gpixels in 2 seconds, resulting in a total of 3024 synchronously read-
out video channels (16 channels or amplifiers per detector). The unique
combination of high speed, high-resistivity silicon, low power, and close
channel spacing makes the LSST readout more prone to electronic crosstalk than
previous mosaic cameras. The primary source of crosstalk is capacitive
coupling between single-ended video outputs from the CCD, which can occur both
within a single CCD and between CCDs in the focal plane. This interference can
also originate from the readout electronics themselves. [14]. To correct this,
a comprehensive matrix for each detector is required, detailing the effect of
each source amplifier on every target amplifier. It’s anticipated that
crosstalk between CCDs will be less than intra-CCD crosstalk, with inter-raft
crosstalk being negligible. Interestingly, the LSSTCam also shows a unique
form of crosstalk between CCD amplifier segments that does not linearly scale
with intensity, differing from what would be expected from capacitive coupling
alone [15].

###  2.8 Bias subtraction, using a combined bias frame

A 2D combined bias frame (commonly referred to in the LSST Science Pipelines
as simply a “bias” frame) must be subtracted during ISR. This frame represents
the signal recorded by the CCD when no light is present and with no
integration time, including the inherent electronic noise of the CCD and the
readout system, as well as any other systematic effects present even when no
light is hitting the detector. To construct a combined bias frame, a series of
individual biases (typically $\approx$ 20 to minimize the noise in the
combined bias frame[16]) or exposures at zero integration time are taken as
input. The overscan, crosstalk, and assembly steps previously discussed are
applied to the input zero-second exposure time images, which are then combined
using a clipped per-pixel mean (i.e., an iteratively sigma-clipped mean is
computed on the set of individual bias images) to construct the output bias
correction. Crosstalk correction must be performed before bias frame creation
to ensure that the crosstalk signal from hot columns is corrected. Otherwise,
these signals will imprint on all of the amplifier segments in subsequent
detrending steps.

###  2.9 Gain scaling*

The process of converting the units of each amplifier from ADU to $e^{-}$
using the gain measurement involves two steps[11]. Initially, the image is
corrected to account for the slight dependence of the gain on the temperature
of the readout electronics board (REB) controlling it (approximately
0.06%/°C). This correction is necessary to accommodate any minor temperature
shifts and ensure all images can use equivalent calibrations. In the second
step, the gains ($e^{-}$/ADU) are used to convert each amplifier from ADU
units to $e^{-}$ units. After the temperature shifts have been corrected, the
PTC analysis is used to measure the gain from each amplifier. The current PTC
pipeline in the LSST Science Pipelines takes as input a series of raw flat
pairs at different fluxes and has 3 main steps: “ISR”, where instrument-
signature removal is applied; “extract”, where the covariances from flats up
to a certain lag (with a default value of 8) using the Fast Fourier Transform
algorithm from Appendix A in Astier et al. (2019)[17] are measured; and
“Solve”, where the measured covariances are fitted to models described in
Astier et al. (2019)[17] (the models in Equations 16 and 20 of that paper).

###  2.10 Charge-Transfer Inefficiency (CTI) correction

CTI is the phenomenon where the voltage changes that serve to shift the
photoelectrons toward the readout amplifiers do so incompletely, resulting in
charge that becomes trapped in the silicon. When this charge is released
later, it manifests visually as spurious trails behind every source object.
This trailing caused by CTI is particularly problematic as the amount of flux
trailed has a nonlinear relationship with the flux and size of the source and
the recent illumination history of the detector. CTI differs between the
serial and parallel transfer readout directions due to their distinct charge
transfer methods and spacings of wells. [18] The LSST Science Pipelines
implement a detector and segment-dependent CTI correction algorithm described
by Snyder et al. (2020)[19] to correct for serial CTI in ITL devices. This
algorithm aims to accurately model and account for the position- and flux-
dependent nature of CTI trailing seen in LSST images.

###  2.11 Amplifier assembly and trimming

The overscan regions of the images are trimmed, and the 16 amplifiers per
detector are assembled into a single CCD image.

###  2.12 Variance calculation (variance image construction)

A weight map is calculated from assembled and trimmed images based on the
measured variance per pixel. This is constructed by first dividing each image
segment by the gain ($e^{-}$/ADU) of that segment to derive the Poisson
variance, and then adding the square of the read noise to derive a map of the
empirical uncertainty across an image (the “Variance Plane Image”). The read
noise can be measured empirically from the overscan region of the detector and
can also be calculated as a parameter from the fit to the PTC.

###  2.13 Defect mask interpolation

Defects are determined as the outliers of the pixel value distributions from
dark and flat-field images and are set to the BAD flag. Individual or combined
darks and flats can be used. The thresholds in darks and flats can be
specified in terms of values or standard deviations from the mean.

###  2.14 Dark subtraction, using a combined dark frame

A combined dark image, to be subtracted from science images, is constructed by
taking a clipped per-pixel mean from a set of individual dark images, similar
to the bias image described in section 2.8. Individual dark images of the
entire LSSTCam focal plane are captured with the camera shutter closed,
including contributions from dark current and light leakages. Dark images are
also used to create defect maps and are taken at different integration times
to study dynamic defects or bad columns.

###  2.15 Brighter-fatter effect correction

The brighter-fatter effect (BFE) refers to the observed growth in the sizes of
stars with signal level, resulting from the deflection of in-falling charges
by transverse electric fields produced by already accumulated charges in the
potential wells of pixels.[20, 21, 22, 23] The BFE leads to correlations
between pixels and is calibrated from measured pixel correlations in flat
fields, as it smooths out Poisson noise fluctuations at high signal levels.
The strength of the BFE can differ along the channel stops or barrier clock
gates in a sensor, it can vary mildly with color, and its impact on pixel
correlations does not necessarily scale linearly with signal level.

The effect is calibrated from the empirical correlations in the limit of zero
signal, at a user-specified signal level, or an average of correlations across
a range of signal levels. The pixel correlations are derived from the flat-
field image covariances measured out to a lag of 8 pixels, as mentioned in
section 2.9. Fully capturing the range of the effect is important for the
correction to conserve charge. To verify this, the sum of the pixel
correlations out to this distance is checked for consistency with zero. A PTC
with at least 1000 points from near zero signal up to saturation is necessary
to constrain the anisotropy, magnitude, and range of the effect, as well as
the evolution of the strength of the BFE with signal level. When the
measurement of correlations at large distances is limited by statistical
fluctuations, an empirically measured power law is used to project the pixel
correlations out to larger distances.

The BFE is corrected under the assumption that the derived pixel correlations
are proportional to the Laplacian of a constant, unitless, 2-dimensional,
scalar kernel, which is assumed to represent the displacement field due to a
single accumulated charge [24, 12]. This kernel is then convolved with the
measured image to recover a template representing the amount of displaced
charge due to the BFE. This template is subsequently added to the measured
image to recover the true image. The kernel is applied recursively until the
amount of shifted charge at each iteration falls below a threshold of 1000
electrons across the whole image. If the kernel accurately models the effect,
no more than 2–3 iterations should be required to converge to a solution.

The BFE can empirically vary from amplifier to amplifier or sensor to sensor
and mildly from wavelength to wavelength. Therefore, calibrations are derived
for each sensor, amplifier, and filter band. However, to avoid discontinuities
along amplifier boundaries, the 16 kernels for each channel of a given sensor
are averaged to create a single detector-level kernel that is ultimately used
to remove the effect from images taken by that sensor. Ultimately, we apply
one calibrated kernel per sensor per filter band.

The BFE is small, and the calibration of the BFE can be sensitive to gain
estimation as well as the calibration of other artifacts that affect the
measured pixel correlations, such as charge transfer inefficiency (CTI),
signal-chain non-linearity, overscan subtraction, as well as other sensor-
specific calibrations. Since the BFE is one of the first instrument signatures
to impact an exposure, the correction must be applied near the end of the ISR
pipeline. Extreme care must therefore be taken to remove these other effects
and validate these other ISR steps before deriving calibrations for the BFE
from flat fields and applying the correction to an image.

The kernel is initially validated by backward-correcting flat images to
linearize the PTC, as a good-quality kernel should be able to recover the
Poisson noise in the flat field images. In general, the sub-pixel electric
fields inside a flat image do not approximate the sub-pixel electric fields
inside a typical science image, and the slope of the second moment vs.
magnitude of stellar sources is also checked to be consistent with zero.[25,
23, 12]

###  2.16 Flat-field corrections to convert image to units of fluence*

After the previous correction steps have been applied, an unflattened, gain-
scaled post-ISR image in e- with instrument signatures removed is obtained.
Flat fielding is incorporated into the subsequent photometric calibration
process, which aims to estimate the surface brightnesses of celestial sources
uniformly across the sky as would be measured at the top of the Earth’s
atmosphere.[26, 27, 11] This process involves constructing a “background flat”
per filter for image background subtraction using monochromatic dome flats and
sky data (including background template estimation via, _e.g.,_ Principal
Component Analysis[26]), along with a “reference flux flat” per filter and as
described in Bernstein et al. (2017)[26]. The reference flux flat measures the
response to focused light and differs from a dome flat in several respects,
including accounting for pixel size variations by removing the effects of
transverse electric fields (e.g., tree rings[28, 29, 30] and edge distortions
or “picture frames”[31, 32]), and accounting for differences in focused and
scattered light patterns from flat-field screens and sky sources, and
contamination by scattered light[11].

After this flat-fielding process (including fringe555Fringing arises from
interference effects as light passes through and reflects within the layers of
the CCD and its coatings/filters. correction for redder bands[33]), a fluence
image in e- is obtained, as depicted in the lower right steps of the flow
chart in Figure 2. The subsequent process of turning this fluence image into a
Processed Visit Image in physical units (nJy) involves the construction of a
point-spread function model, morphological cosmic-ray finding and masking, and
the construction of astrometric[34] and photometric solutions[27] (see, e.g.,
Bosch et al. 2018[8] for a description of this process in the context of the
Hyper Supreme-Cam survey using a previous version of the LSST Science
Pipelines).

Figure 3: Calibration flow chart. Credit: Chris Waters, Data Management
Technical Note 222[35]

##  3 Calibration Products Production for ISR

Calibration products are required to carry out the ISR steps. To validate a
new combined calibration for use, metrics are measured on a residual image
that results after applying a given calibration (e.g., a bias-subtracted
individual bias) and compared to expectations and limits (using a series of
tests and metrics defined in the Data Management Technical Note 101[16], see
Table 1). This is accomplished via the cp_verify
package.666https://github.com/lsst/cp_verify If all metrics are within limits,
the calibration is certified for a date range during which it will be used,
though the end date may be unknown.

Calibration products |  Verification criteria
---|---
Bias and Dark |  • Mean consistent with zero. • Clipped standard deviation consistent with read noise. • Cosmic rays rejected standard deviation consistent with read noise.
Brighter-fatter correction |  • Slope of source second-moment size as a function of source magnitude small ($\lessapprox$ 1%).
Table 1: Examples of cp_verify tests for calibration verification. Bias: using
bias-corrected individual bias exposures. Dark: using bias- and dark-corrected
individual dark exposures. Brighter-fatter correction: using full ISR-
processed science exposures.

These validations are also used with daily calibrations to monitor the
stability of the camera and telescope by confirming that existing combined
calibrations remain suitable. Figure 3 shows the relationship between
construction, validation, and usage of combined calibrations. It can be
summarized as:

  * •

A proposed calibration is constructed,

  * •

cp_verify tasks check that it meets verification metrics,

  * •

If the tests pass, the calibration can be certified by a Calibration
Acceptance Board, assigned a validity range, and deployed as a standard
calibration.

Figure 4: cp_verify identifying a defective combined bias from a particular
detector due to an acquisition problem, as indicated in the “failure table” in
the right, using the tests of Table 1: NOISE corresponds to “Clipped standard
deviation consistent with read noise” and MEAN corresponds to “Mean consistent
with zero”.

Figure 4 shows an example of a defective bias failing the tests defined in
cp_verify.

##  4 The LSST Data Butler, Calibration Collections, and Calibration Pipelines

The Rubin data management system uses a “data Butler” to organize and locate
datasets[36]. This Butler groups data into “collections,” with a special
“calibration collection” that associates calibration datasets with a validity
time range. When image processing is started, the Butler uses these validity
time ranges to match the supplied calibration data to the images to be
processed. Calibrations that are not calculated from available data (like
quantum efficiency curves) or are relatively static (like defect masks) are
called “curated calibrations.” These are stored in text files in GitHub
repositories with a directory structure that encodes their validity
ranges777For example, https://github.com/lsst/obs_lsst_data/tree/main/lsstCam
stores transmission curves for LSSTCam. Processing is done via PipelineTasks.
Each PipelineTask provides one processing step, ands everal can be combined
into a full pipeline defined in a YAML file. Figure 5 shows a diagram
depicting the PipelineTasks involved in the creation of a combined bias using
the bias pipeline. The _dimensions_ are the key variables or parameters that
define the characteristics of a Butler dataset, such as its observation time,
instrument configuration, target coordinates, filter, etc., that allow it to
be uniquely identified and located within the data archive system.[36] The ISR
PipelineTasks for LSSTCam provide the functionality to remove systematic
errors from the raw instrument data, using the calibration products discussed
above. Multiple ISR PipelineTasks with different configurations can be defined
to handle different instruments.

Figure 5: PipelineTasks in the bias pipeline to produce a combined bias.
Diagram credit: L. Kelvin and the LSST Science Pipelines.

### Disclosures

There are no conflicts of interest.

### Code, Data, and Materials Availability

The LSST Science Pipelines (pipelines.lsst.io) code described in this article
is open-source and available in the following repositories:
https://github.com/lsst/ip_isr, https://github.com/lsst/cp_pipe, and
https://github.com/lsst/cp_verify.

### Acknowledgments

The work of AAPM was supported by the U.S. Department of Energy under contract
number DE-AC02-76SF00515. This paper makes use of LSST Science Pipelines
software developed by the Vera C. Rubin Observatory. We thank the Rubin
Observatory for making their code available as free software at
https://pipelines.lsst.io. This material or work is supported in part by the
National Science Foundation through Cooperative Agreement AST-1258333 and
Cooperative Support Agreement AST1836783 managed by the Association of
Universities for Research in Astronomy (AURA), and the Department of Energy
under Contract No. DE-AC02-76SF00515 with the SLAC National Accelerator
Laboratory managed by Stanford University. AAPM thanks the Department of
Physics of Harvard University and the Laboratory of Particle Astrophysics and
Cosmology led by Prof. Chris Stubbs for their hospitality during the
preparation of this paper.We thank S. Digel (SLAC National Accelerator
Laboratory) for serving as Rubin’s internal reviewer and providing comments
that improved the manuscript. We thank T. Jenness (Rubin) and Z. Ivezic
(Rubin, University of Washington) for providing comments that improved the
manuscript.

## References

  * [1] . Ivezić, S. M. Kahn, J. A. Tyson, et al., “LSST: From science drivers to reference design and anticipated data products,” The Astrophysical Journal 873, 111 (2019).
  * [2] S. E. Holland, D. E. Groom, N. P. Palaio, et al., “Fully depleted, back-illuminated charge-coupled devices fabricated on high-resistivity silicon,” IEEE Transactions on Electron Devices 50, 225–238 (2003).
  * [3] S. E. Holland, W. F. Kolbe, and C. J. Bebek, “Device Design for a 12.3-Megapixel, Fully Depleted, Back-Illuminated, High-Voltage Compatible Charge-Coupled Device,” IEEE Transactions on Electron Devices 56, 2612–2622 (2009).
  * [4] S. E. Holland, C. J. Bebek, W. F. Kolbe, et al., “Physics of fully depleted CCDs,” Journal of Instrumentation 9, C03057 (2014).
  * [5] P. O’Connor, P. Antilogus, P. Doherty, et al., “Integrated system tests of the LSST raft tower modules,” in High Energy, Optical, and Infrared Detectors for Astronomy VII, A. D. Holland and J. Beletic, Eds., Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 9915, 99150X (2016).
  * [6] K. Arndt, V. Riot, E. Alagoz, et al., “The LSST camera corner raft conceptual design: a front-end for guiding and wavefront sensing,” in Adaptive Optics Systems II, B. L. Ellerbroek, M. Hart, N. Hubin, et al., Eds., Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 7736, 773662 (2010).
  * [7] M. Lesser and D. Ouellette, “Results from STA/ITL fully depleted CCDs for LSST,” Journal of Instrumentation 12, C03080 (2017).
  * [8] J. Bosch, R. Armstrong, S. Bickerton, et al., “The Hyper Suprime-Cam software pipeline,” Publications of the Astronomical Society of Japan 70, S5 (2018).
  * [9] J. Bosch, Y. AlSayyad, R. Armstrong, et al., “An Overview of the LSST Image Processing Pipelines,” in Astronomical Data Analysis Software and Systems XXVII, P. J. Teuben, M. W. Pound, B. A. Thomas, et al., Eds., Astronomical Society of the Pacific Conference Series 523, 521 (2019).
  * [10] J. R. Janesick, Scientific charge-coupled devices, SPIE, Bellingham (2001).
  * [11] P. Fagrelius and E. Rykoff, “Rubin Baseline Calibration Plan,” (2023).  Vera C. Rubin Observatory Commissioning Technical Note SITCOMTN-086.
  * [12] C. Lage, “Linearity and correction of the BF effect in LSST sensors,” arXiv e-prints , arXiv:1911.09567 (2019).
  * [13] J. K. C. Freudenburg, J. J. Givans, A. Choi, et al., “Brighter-fatter Effect in Near-infrared Detectors—III. Fourier-domain Treatment of Flat Field Correlations and Application to WFIRST,” PASP 132, 074504 (2020).
  * [14] P. O’Connor, “Crosstalk in multi-output CCDs for LSST,” Journal of Instrumentation 10, C05010 (2015).
  * [15] A. Snyder, A. Barrau, A. Bradshaw, et al., “Laboratory Measurements of Instrumental Signatures of the LSST Camera Focal Plane,” arXiv e-prints , arXiv:2101.01281 (2021).
  * [16] Lupton, R. and Plazas Malagón, A., “Verifying LSST Calibration Data Products,” (2018).  Vera C. Rubin Observatory Data Management Technical Note DMTN-101.
  * [17] P. Astier, P. Antilogus, C. Juramy, et al., “The shape of the photon transfer curve of CCD sensors,” AAP 629, A36 (2019).
  * [18] R. Massey, T. Schrabback, O. Cordes, et al., “An improved model of charge transfer inefficiency and correction algorithm for the Hubble Space Telescope,” Monthly Notices of the Royal Astronomical Society 439, 887–907 (2014).
  * [19] A. Snyder and A. Roodman, “Investigation of Deferred Charge Effects in LSST ITL Sensors,” arXiv e-prints , arXiv:2001.03223 (2020).
  * [20] P. Antilogus, P. Astier, P. Doherty, et al., “The brighter-fatter effect and pixel correlations in ccd sensors,” Journal of Instrumentation 9, C03048–C03048 (2014).
  * [21] A. Guyonnet, P. Astier, P. Antilogus, et al., “Evidence for self-interaction of charge distribution in charge-coupled devices,” AAP 575, A41 (2015).
  * [22] D. Gruen, G. M. Bernstein, M. Jarvis, et al., “Characterization and correction of charge-induced pixel shifts in DECam,” Journal of Instrumentation 10, C05032 (2015).
  * [23] A. Broughton, Y. Utsumi, A. Plazas Malagón, et al., “Mitigation of the Brighter-Fatter Effect in the LSST Camera,” arXiv e-prints , arXiv:2312.03115 (2023).
  * [24] W. R. Coulton, R. Armstrong, K. M. Smith, et al., “Exploring the Brighter-fatter Effect with the Hyper Suprime-Cam,” Astronomical Journal 155, 258 (2018).
  * [25] P. Astier and N. Regnault, “Correction of the brighter-fatter effect on the CCDs of Hyper Suprime-Cam,” Astronomy and Astrophysics 670, A118 (2023).
  * [26] G. M. Bernstein, T. M. C. Abbott, S. Desai, et al., “Instrumental response model and detrending for the Dark Energy Camera,” Publications of the Astronomical Society of the Pacific 129, 114502 (2017).
  * [27] G. M. Bernstein, T. M. C. Abbott, R. Armstrong, et al., “Photometric Characterization of the Dark Energy Camera,” Publications of the Astronomical Society of the Pacific 130, 054501 (2018).
  * [28] A. A. Plazas, G. M. Bernstein, and E. S. Sheldon, “On-Sky Measurements of the Transverse Electric Fields’ Effects in the Dark Energy Camera CCDs,” Publications of the Astronomical Society of the Pacific 126, 750–760 (2014).
  * [29] H. Y. Park, A. Nomerotski, and D. Tsybychev, “Properties of tree rings in LSST sensors,” Journal of Instrumentation 12, C05015 (2017).
  * [30] J. H. Esteves, Y. Utsumi, A. Snyder, et al., “Photometry, Centroid and Point-spread Function Measurements in the LSST Camera Focal Plane Using Artificial Stars,” Publications of the Astronomical Society of the Pacific 135, 115003 (2023).
  * [31] A. A. Plazas, G. M. Bernstein, and E. S. Sheldon, “Transverse electric fields’ effects in the Dark Energy Camera CCDs,” Journal of Instrumentation 9, C04001 (2014).
  * [32] A. A. Plazas Malagón, “Transverse electric fields effects in decam devices: tree rings and glowing edges,” Precision Astronomy with Fully-Depleted CCDs (PACCDs), Brookhaven National Laboratory, November, 2013, Zenodo, DOI: 10.5281/zenodo.10064122 (2013).
  * [33] Z. Guo, C. W. Walter, C. Lage, et al., “Fringing Analysis and Simulation for the Vera C. Rubin Observatory’s Legacy Survey of Space and Time,” Publications of the Astronomical Society of the Pacific 135, 034503 (2023).
  * [34] G. M. Bernstein, R. Armstrong, A. A. Plazas, et al., “Astrometric Calibration and Performance of the Dark Energy Camera,” Publications of the Astronomical Society of the Pacific 129, 074503 (2017).
  * [35] C. Waters, “Calibration Generation, Verification, Acceptance, and Certification.,” (2023).  Vera C. Rubin Observatory Data Management Technical Note DMTN-222.
  * [36] T. Jenness, J. F. Bosch, A. Salnikov, et al., “The Vera C. Rubin Observatory Data Butler and pipeline execution system,” in Software and Cyberinfrastructure for Astronomy VII, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 12189, 1218911 (2022).

###### List of Figures

  1. 1 Example of an image before and after partial Instrument Signature Removal (bias, dark, and flat applied).
  2. 2 ISR steps and necessary calibration products. Units are displayed in each box, and the steps in red and enclosed in dashed lines are in the process of being implemented. Flowchart based on discussions at Rubin Calibration Workshop at SLAC, October 2023.
  3. 3 Calibration flow chart. Credit: Chris Waters, Data Management Technical Note 222[35]
  4. 4 cp_verify identifying a defective combined bias from a particular detector due to an acquisition problem, as indicated in the “failure table” in the right, using the tests of Table 1: NOISE corresponds to “Clipped standard deviation consistent with read noise” and MEAN corresponds to “Mean consistent with zero”.
  5. 5 PipelineTasks in the bias pipeline to produce a combined bias. Diagram credit: L. Kelvin and the LSST Science Pipelines.

###### List of Tables

  1. 1 Examples of cp_verify tests for calibration verification. Bias: using bias-corrected individual bias exposures. Dark: using bias- and dark-corrected individual dark exposures. Brighter-fatter correction: using full ISR-processed science exposures.


# Defective acyclic colorings of planar graphs

On-Hei Solomon Lo Faculty of Environment and Information Sciences, Yokohama
National University, Yokohama 240-8501, Japan Ben Seamone Mathematics
Department, Dawson College, Montreal, QC, CanadaDépartement d’informatique et
de recherche opérationnelle, Université de Montréal, Montreal, QC, Canada
Xuding Zhu
Department of Mathematics, Zhejiang Normal University, Jinhua 321004, China

###### Abstract

This paper studies two variants of defective acyclic coloring of planar
graphs. For a graph $G$ and a coloring $\varphi$ of $G$, a 2CC transversal is
a subset $E^{\prime}$ of $E(G)$ that intersects every 2-colored cycle. Let $k$
be a positive integer. We denote by $m_{k}(G)$ the minimum integer $m$ such
that $G$ has a proper $k$-coloring which has a 2CC transerval of size $m$, and
by $m^{\prime}_{k}(G)$ the minimum size of a subset $E^{\prime}$ of $E(G)$
such that $G-E^{\prime}$ is acyclic $k$-colorable. We prove that for any
$n$-vertex $3$-colorable planar graph $G$, $m_{3}(G)\leq n-3$ and for any
planar graph $G$, $m_{4}(G)\leq n-5$ provided that $n\geq 5$. We show that
these upper bounds are sharp: there are infinitely many planar graphs
attaining these upper bounds. Moreover, the minimum 2CC transversal
$E^{\prime}$ can be chosen in such a way that $E^{\prime}$ induces a forest.
We also prove that for any planar graph $G$,
$m^{\prime}_{3}(G)\leq(13n-42)/10$ and $m^{\prime}_{4}(G)\leq(3n-12)/5$.

##  1 Introduction

An acyclic $k$-coloring of a graph $G$ is a proper $k$-coloring of $G$ with no
2-colored cycles. Confirming a conjecture of Grünbaum [3], Borodin [1] proved
that every planar graph has an acyclic 5-coloring. This celebrated result is
best possible as there are planar graphs that are not acyclic 4-colorable
(e.g. the octahedron). Acyclic coloring has been studied extensively for
several decades and applied to solve other problems on graph coloring and
partitioning. We refer to [2] for a comprehensive survey on this subject.

This paper studies defective acyclic $k$-coloring of planar graphs mainly for
$k=3,4$. In other words, we study $k$-colorings of planar graphs for which the
condition of being an acyclic coloring is not completely satisfied, however,
we want to limit the violation of the acyclicity rules. We consider two
variants of defective acyclic coloring.

######  Definition 1.

Given a graph $G$ and a proper coloring $\varphi$ of $G$, a $2$-colored cycle
transversal ($2$CC transversal) with respect to $\varphi$ is a subset
$E^{\prime}$ of $E(G)$ that intersects all 2-colored cycles. In other words,
$G-E^{\prime}$ contains no 2-colored cycles.

######  Definition 2.

Let $G$ be a graph and $k$ be a positive integer. We define two parameters
$m_{k}(G)$ and $m^{\prime}_{k}(G)$ as follows:

  * •

$m_{k}(G):=\min_{E^{\prime}\subseteq E(G)}\\{|E^{\prime}|:\text{$E^{\prime}$
is a 2CC transversal with respect to a proper $k$-coloring}\\}.$

  * •

$m^{\prime}_{k}(G):=\min_{E^{\prime}\subseteq
E(G)}\\{|E^{\prime}|:\text{$G-E^{\prime}$ has an acyclic $k$-coloring}\\}.$

Note that $m_{k}(G)=m^{\prime}_{k}(G)=0$ if and only if $G$ is acyclic
$k$-colorable. If $G$ has no proper $k$-coloring, then $m_{k}(G)$ is not
defined. In this case, we let $m_{k}(G):=\infty$. It follows from the
definition that for any graph $G$ and integer $k$, $m_{k}(G)\geq
m^{\prime}_{k}(G)$.

We are interested in the case that $G$ is a planar graph and $k=3,4$ as
Borodin’s theorem asserts that $m_{5}(G)=0$. To obtain an upper bound for
$m_{k}(G)$, we need to construct a proper $k$-coloring $\varphi$ of $G$ and
find a 2CC transerval $E^{\prime}$. One immediate difficulty is that, for
$k=4$, the existence of a proper $4$-coloring of a planar graph follows from
the Four Color Theorem. For $k=3$, it is NP-complete to decide whether a
planar graph $G$ is 3-colorable, and hence there is no easy way to construct a
proper 3-coloring of $G$. Fortunately, it turns out that tight upper bounds
for $m_{4}(G)$ and $m_{3}(G)$ for the whole family of planar graphs and the
whole family of 3-colorable planar graphs do not depend on a particular proper
coloring of $G$.

For any proper coloring $\varphi$ of a graph $G$, define

$\displaystyle m(G,\varphi):=\min_{E^{\prime}\subseteq
E(G)}\\{|E^{\prime}|:\text{$E^{\prime}$ is a 2CC transerval with respect to
$\varphi$}\\}.$

We prove in Section 3 that for any planar graph $G$ on $n$ vertices and any
proper coloring $\varphi$ of $G$, $m(G,\varphi)\leq n-|\varphi(V(G))|$, where
$|\varphi(V(G))|$ denotes the number of colors used in $\varphi$. To this end,
we study the case when $G$ is a plane triangulation in Section 2. Moreover, we
show that if $n\geq 5$, then there is a 4-coloring $\varphi$ of $G$ with
$m(G,\varphi)\leq n-5$. We apply these results to prove that for every planar
graph $G$, $m_{4}(G)\leq n-5$ provided that $n\geq 5$, and $m_{3}(G)\leq n-3$
provided that $G$ is 3-colorable. These two bounds are tight as there are
infinitely many 3-colorable planar graphs $G$ with $m_{3}(G)=n-3$ and
infinitely many planar graphs $G$ with $m_{4}(G)=n-5$. Besides, we show in
Section 3 that for any proper coloring $\varphi$ of a planar graph $G$, we can
find a 2CC transerval $E^{\prime}$ with $|E^{\prime}|=m(G,\varphi)$ that
induces a forest. In Section 4 we study the parameter $m^{\prime}_{k}(G)$. We
show that $m^{\prime}_{3}(G)\leq(13n-42)/10$ and
$m^{\prime}_{4}(G)\leq(3n-12)/5$.

We shall mention an application of our results on acyclic colorings of
subdivisions. For a graph $G$ and a positive integer $k$, define
$m^{\prime\prime}_{k}(G)$ to be the minimum size of an edge set
$E^{\prime}\subseteq E(G)$ such that the graph obtained from $G$ by
subdividing each edge in $E^{\prime}$ by one vertex is acyclically
$k$-colorable. It is easy to observe that $m_{k}(G)\geq
m^{\prime\prime}_{k}(G)\geq m^{\prime}_{k}(G)$. It was shown in [4] that for
any $n$-vertex planar graph $G$, $m^{\prime\prime}_{4}(G)\leq n-3$. Our upper
bound for $m_{4}(G)$ immediately improves it to $m^{\prime\prime}_{4}(G)\leq
n-5$ for $n\geq 5$.

All graphs considered in this paper are finite and simple. We denote by $V(G)$
and $E(G)$ the vertex set and the edge set of $G$, respectively. For $v\in
V(G)$, denote by $N_{G}(v)$ the set of vertices adjacent to $v$ and by
$d_{G}(v)$ the degree of $v$. For a positive integer $k$, denote
$[k]:=\\{1,\dots,k\\}$. A _$k$ -coloring_ $\varphi$ of $G$ is a function which
assigns a color $\varphi(v)\in[k]$ to each vertex $v\in V(G)$. We say a
coloring $\varphi$ is _proper_ if $\varphi(u)\neq\varphi(v)$ for any $uv\in
E(G)$. In fact, we always consider proper colorings unless specified
otherwise. Given a $k$-coloring $\varphi$ of $G$, we define the color classes
by $\varphi^{-1}(i):=\\{v\in V(G):\varphi(v)=i\\}$ for any $i\in[k]$. For any
distinct $i,j\in[k]$, define $G_{ij}$ to be the subgraph of $G$ induced by
$\varphi^{-1}(i)\cup\varphi^{-1}(j)$.

##  2 Upper bounds for $m(G,\varphi)$

In this section we prove upper bounds on the parameter $m(G,\varphi)$ for
planar graphs. We first present several lemmas for plane triangulations.

######  Definition 3.

Let $G$ be a plane triangulation on at least 4 vertices. Denote by
$\mathcal{E}_{G}$ the set of separating triangles of $G$, and by
$\mathcal{V}_{G}$ the set of maximal connected subgraphs of $G$ without
separating triangles. The graph $\mathcal{T}_{G}$ is defined to be the graph
on $\mathcal{V}_{G}$ with edge set $\mathcal{E}_{G}$ such that
$G_{1},G_{2}\in\mathcal{V}_{G}$ are joined by $T\in\mathcal{E}_{G}$ if and
only if both $G_{1}$ and $G_{2}$ contain $T$.

It is easy to see that $\mathcal{V}_{G}$ is a family of 4-connected plane
triangulations and $\mathcal{T}_{G}$ is a tree. Let
$\mathcal{V}_{G}:=\\{G_{1},\dots,G_{t}\\}$ and
$\mathcal{E}_{G}:=\\{T_{1},\dots,T_{t-1}\\}$. The graph $G$ can be retrieved
from the vertex-disjoint union of $G_{1},\dots,G_{t}$ by identifying the
copies of triangle $T$ in $G_{i},G_{j}$ for each
$T=G_{i}G_{j}\in\mathcal{E}_{G}$. Hence
$\sum_{i\in[t]}|V(G_{i})|=|V(G)|+3(t-1)$.

######  Lemma 4.

Let $G$ be a graph and $\varphi$ be a proper coloring of $G$. If $A$ is an
edge set of $G$ such that $A\cap E(G_{ij})$ is an acyclic edge set for any
distinct $i,j\in[k]$, then there exists $E^{\prime}\subseteq E(G)\setminus A$
satisfying that $|E^{\prime}|=m(G,\varphi)$ and $\varphi$ is an acyclic
coloring of $G-E^{\prime}$.

###### Proof.

Let $E^{\prime}\subseteq E(G)$ be such that $|E^{\prime}|=m(G,\varphi)$,
$\varphi$ is an acyclic coloring of $G-E^{\prime}$ and, subject to this,
$|E^{\prime}\cap A|$ is minimum. Suppose there exists $uv\in E^{\prime}\cap
A$. There is precisely one cycle $C$ in
$G_{\varphi(u)\varphi(v)}-(E^{\prime}-uv)$. As $A\cap
E(G_{\varphi(u)\varphi(v)})$ is acyclic, there exists $e^{\prime}\in
E(C)\setminus A$. Then $G_{\varphi(u)\varphi(v)}-(E^{\prime}-uv+e^{\prime})$
is acyclic, $|E^{\prime}-uv+e^{\prime}|=|E^{\prime}|=m(G,\varphi)$ and
$|(E^{\prime}-uv+e^{\prime})\cap A|<|E^{\prime}\cap A|$, contradicting our
choice of $E^{\prime}$. Hence $E^{\prime}\subseteq E(G)\setminus A$ as
desired. ∎

######  Lemma 5.

Let $G$ be a plane graph, $T$ be a separating triangle of $G$ and $\varphi$ be
a proper coloring of $G$. Let $A_{1}$ and $A_{2}$ be the components of $G-T$,
and for $i\in[2]$, $G^{i}$ be the subgraph of $G$ induced by $V(A_{i})\cup
V(T)$. Then $m(G,\varphi)=m(G^{1},\varphi^{1})+m(G^{2},\varphi^{2})$, where
$\varphi^{i}$ denotes the restriction of $\varphi$ on $V(G^{i})$.

###### Proof.

Without loss of generality, we let $V(T)=\\{v_{1},v_{2},v_{3}\\}$ with
$\varphi(v_{i})=i$ for $i\in[3]$. By Lemma 4, there exists
$E^{\prime}\subseteq E(G)\setminus E(T)$ such that $|E^{\prime}|=m(G,\varphi)$
and $\varphi$ is an acyclic coloring of $G-E^{\prime}$. As
$G^{i}-(E^{\prime}\cap E(G^{i}))$ is acyclically colored by $\varphi^{i}$
($i\in[2]$), we have $m(G,\varphi)=|E^{\prime}|=|E^{\prime}\cap
E(G^{1})|+|E^{\prime}\cap E(G^{2})|\geq
m(G^{1},\varphi^{1})+m(G^{2},\varphi^{2})$.

Similarly, by Lemma 4, let $E_{i}^{\prime}\subseteq E(G^{i})\setminus E(T)$ be
such that $|E_{i}^{\prime}|=m(G^{i},\varphi^{i})$ and $G^{i}-E_{i}^{\prime}$
is acyclically colored by $\varphi_{i}$. Let $E^{\prime}:=E_{1}^{\prime}\cup
E_{2}^{\prime}$. Observe that if there is a cycle $C$ which is colored by only
two colors in $G-E^{\prime}$, then $C$ must contain two vertices of $T$, say
$v_{1},v_{2}$, and $C+v_{1}v_{2}$ contains some cycle in
$G^{1}-E_{1}^{\prime}$ or $G^{2}-E_{2}^{\prime}$ which uses only two colors as
well, a contradiction. Hence $G-E^{\prime}$ is acyclically colored and
$m(G,\varphi)\leq|E^{\prime}|=|E_{1}^{\prime}|+|E_{2}^{\prime}|=m(G^{1},\varphi^{1})+m(G^{2},\varphi^{2})$.
∎

######  Lemma 6.

Let $G$ be a plane triangulaion on at least $4$ vertices and $\varphi$ be a
proper coloring of $G$. Let $\mathcal{V}_{G}:=\\{G_{1},\dots,G_{t}\\}$. We
have $m(G,\varphi)=\sum_{i\in[t]}m(G_{i},\varphi_{i})$, where $\varphi_{i}$
denotes the restriction of $\varphi$ on $V(G_{i})$.

###### Proof.

We prove by induction on $|\mathcal{V}_{G}|$. It trivially holds when
$|\mathcal{V}_{G}|=1$.

Suppose $|\mathcal{V}_{G}|>1$. Let $T\in\mathcal{E}_{G}$, $A_{1}$ and $A_{2}$
be the components of $G-T$, and for $i\in[2]$, $G^{i}$ be the subgraph of $G$
induced by $V(A_{i})\cup V(T)$. We may assume
$G_{1},\dots,G_{t^{\prime}}\subseteq G^{1}$ and
$G_{t^{\prime}+1},\dots,G_{t}\subseteq G^{2}$ for some $1\leq t^{\prime}<t$.
Then, by Lemma 5 and the induction hypothesis,
$m(G,\varphi)=m(G^{1},\varphi^{1})+m(G^{2},\varphi^{2})=\sum_{i\in[t^{\prime}]}m(G_{i},\varphi_{i})+\sum_{i\in[t]\setminus[t^{\prime}]}m(G_{i},\varphi_{i})=\sum_{i\in[t]}m(G_{i},\varphi_{i})$.
∎

######  Lemma 7.

Let $G$ be a $3$-colorable plane triangulation on $n$ vertices and $\varphi$
be the unique proper $3$-coloring of $G$. For any distinct $i,j\in[3]$,
$G_{ij}$ is connected. Moreover, if $n>3$, $G_{ij}$ is $2$-connected.

###### Proof.

We prove by induction on $n$. The triangulations of order at most 6 are listed
in Figure 1. Among these graphs, only the triangle and the octahedron are
3-colorable. It is not hard to verify that the claims hold for these two
graphs. From now on we assume that $n>6$.

As $G$ is a 3-colorable triangulation, every vertex of $G$ has an even degree,
and hence there exists $v\in V(G)$ with $d_{G}(v)=4$. Let
$v_{1}v_{2}v_{3}v_{4}v_{1}$ be the cycle induced by $N_{G}(v)$. We have
$\varphi(v_{i})=\varphi(v_{i+2})$ for each $i\in[2]$. Suppose there exists
$i\in[2]$ such that $v_{i}$ and $v_{i+2}$ have no common neighbor other than
$v,v_{i+1},v_{i+3}$, where $v_{5}:=v_{1}$. We contract $v_{i}vv_{i+2}$ to
obtain $G^{\prime}$ and call the new vertex $v^{\prime}$. Let
$\varphi^{\prime}:V(G^{\prime})\rightarrow[3]$ be such that
$\varphi^{\prime}(v^{\prime})=\varphi(v_{i})$ and
$\varphi^{\prime}(u)=\varphi(u)$ for $u\in
V(G^{\prime})\setminus\\{v^{\prime}\\}$. It is clear that $\varphi^{\prime}$
is the unique proper 3-coloring of the triangulation $G^{\prime}$. By the
induction hypothesis, $G_{ij}^{\prime}$ is 2-connected for any distinct
$i,j\in[3]$. Then, one can easily prove by the construction that $G_{ij}$ is
2-connected for any distinct $i,j\in[3]$.

Suppose for every $i\in[2]$, $v_{i}$ and $v_{i+2}$ have some common neighbor
other than $v,v_{i+1},v_{i+3}$. Since $G$ is not the octahedron, it has some
separating triangle $T$. Let $A_{1},A_{2}$ be the components of $G-T$. We
consider the subgraphs $G^{i}$ of $G$ induced by $V(A_{i})\cup V(T)$
($i\in[2]$). Let $\varphi_{i}$ be restriction of $\varphi$ on $V(G^{i})$. As
$|V(G^{i})|>3$, it follows from the induction hypothesis that $G_{jk}^{i}$ is
2-connected for any distinct $j,k\in[3]$ ($i\in[2]$), from which it
immediately follows that $G_{jk}$ is 2-connected for any distinct $j,k\in[3]$.
∎

Figure 1: The triangulations of order at most 6.

Let $G$ be a graph with a proper $k$-coloring $\varphi$. Denote by $c_{ij}$
the number of connected components of $G_{ij}$. The number of edges we need to
remove from $G_{ij}$ to make $\varphi$ acyclic is
$|E(G_{ij})|-|V(G_{ij})|+c_{ij}$. As $E(G_{ij})$ are edge-disjoint for
distinct $i,j$, and each vertex $v$ of $G$ is contained in $k-1$ subgraphs
$G_{ij}$, we know that

$\displaystyle m(G,\phi)=\sum_{1\leq i<j\leq
k}(|E(G_{ij})|-|V(G_{ij})|+c_{ij})=|E(G)|-(k-1)|V(G)|+\sum_{1\leq i<j\leq
k}c_{ij}.$

We obtain the following result by this observation.

######  Theorem 8.

Assume $G$ is a $3$-colorable plane triangulation on $n$ vertices and
$\varphi$ is the unique proper $3$-coloring of $G$. Then $m(G,\varphi)=n-3$.
For $v\in V(G)$, let $\varphi_{v}$ be the $4$-coloring of $G$ defined as
$\varphi_{v}(v)=4$ and $\varphi_{v}(u)=\varphi(u)$ for all $u\in
V(G)\setminus\\{v\\}$. If $n>3$, we have $m(G,\varphi_{v})\leq n-5$.

###### Proof.

By Lemma 7, $G_{ij}$ is connected for any distinct $i,j\in[3]$. Hence

$\displaystyle m(G,\varphi)$ $\displaystyle=\sum_{1\leq i<j\leq
3}(|E(G_{ij})|-|V(G_{ij})|+1)=|E(G)|-2|V(G)|+3=n-3.$

For the second statement, we fix $v\in V(G)$ and focus on the coloring
$\varphi_{v}$. Without loss of generality, assume $\varphi(v)=3$. By Lemma 7,
$G_{12}$ (with respect to the coloring $\varphi_{v}$) is 2-connected.
Moreover, for $i\in[2]$, the subgraph induced by
$\varphi_{v}^{-1}(i)\cup\varphi_{v}^{-1}(3)\cup\\{v\\}=\varphi^{-1}(i)\cup\varphi^{-1}(3)$
is 2-connected and hence $G_{i3}$ (with respect to the coloring $\varphi_{v}$)
is connected. It is also obvious that $G_{i4}$ is a forest for every
$i\in[3]$. As $d_{G}(v)\geq 4$, we have that

$\displaystyle m(G,\varphi)$ $\displaystyle=\sum_{1\leq i<j\leq
3}(|E(G_{ij})|-|V(G_{ij})|+1)=(|E(G)|-d_{G}(v))-2(|V(G)|-1)+3\leq n-5.\qed$

We are now ready to prove the main result of this section.

######  Theorem 9.

Assume $G$ is a plane triangulation on $n$ vertices and $\varphi$ is a proper
coloring of $G$. Let $k:=|\varphi(V(G))|$. Then $m(G,\varphi)\leq n-k$. If, in
addition, $k=4$, $n\geq 5$ and $G$ is $4$-connected, then $m(G,\varphi)\leq
n-5$.

###### Proof.

We prove both statements by induction on $n$. It is easy to check that they
hold for $n\leq\max\\{6,k\\}$, thus we assume $n>\max\\{6,k\\}$.

We first consider, for the first statement, that $G$ is not 4-connected, i.e.
$G$ has some separating triangle $T$. Let $A_{1},A_{2}$ be the components of
$G-T$. Let $G_{i}$ be the subgraphs of $G$ induced by $V(A_{i})\cup V(T)$
($i\in[2]$). Denote by $\varphi_{i}$ the restriction of $\varphi$ on
$V(G_{i})$. Write $n_{i}:=|V(G_{i})|$ and $k_{i}:=|\varphi_{i}(G_{i})|$. Note
that $n_{1}+n_{2}=n+3$ and $k_{1}+k_{2}\geq k+3$. By the induction hypothesis
and Lemma 4, for each $i\in[2]$, there exists $E_{i}^{\prime}\subseteq
E(G_{i})\setminus E(T)$ such that $|E_{i}^{\prime}|\leq n_{i}-k_{i}$ and
$G_{i}-E_{i}^{\prime}$ is acyclically colored by $\varphi_{i}$. Let
$E^{\prime}:=E_{1}^{\prime}\cup E_{2}^{\prime}$. It is easy to prove that
$G-E^{\prime}$ is acyclically colored by $\varphi$ and
$|E^{\prime}|=|E_{1}^{\prime}|+|E_{2}^{\prime}|\leq(n_{1}-k_{1})+(n_{2}-k_{2})\leq
n-k$.

Henceforth, we assume that $G$ has no separating triangle and thus
$\delta(G)=4,5$. Fix $v\in V(G)$ such that $d_{G}(v)=\delta(G)$. Depending on
the value of $\delta(G)$, we consider two cases.

Case 1: $d_{G}(v)=\delta(G)=4$.

Let $v_{1}v_{2}v_{3}v_{4}v_{1}$ be the cycle induced by $N_{G}(v)$. Since
$n>6$ and $G$ has no separating triangle, we can assume that $v_{1},v_{3}$
have no common neighbor other than $v,v_{2},v_{4}$.

If $\varphi(v_{1})\neq\varphi(v_{3})$, we obtain $G^{\prime}$ from $G$ by
deleting $v$ and adding the edge $v_{1}v_{3}$. Let $\varphi^{\prime}$ be the
restriction of $\varphi$ on $V(G^{\prime})$. Denote
$n^{\prime}:=|V(G^{\prime})|$ and
$k^{\prime}:=|\varphi^{\prime}(V(G^{\prime}))|$. Note that $G^{\prime}$ is
4-connected, $n^{\prime}=n-1\geq 6$ and $k^{\prime}=k$ or $k-1$. Moreover, if
$k^{\prime}=k-1$, then $v$ is the only vertex that is colored by $\varphi(v)$
and hence no 2-colored cycle in $G$ contains $v$. By the induction hypothesis,
there exists $E^{\prime\prime}\subseteq E(G^{\prime})$ such that
$G^{\prime}-E^{\prime\prime}$ is acyclically colored by $\varphi^{\prime}$ and
$|E^{\prime\prime}|=m(G^{\prime},\varphi^{\prime})\leq n^{\prime}-k^{\prime}$.
Define $S:=\\{vv_{2}\\}$ if $k^{\prime}=k$, and $S:=\emptyset$ if
$k^{\prime}=k-1$. Set
$E^{\prime}:=(E^{\prime\prime}\setminus\\{v_{1}v_{3}\\})\cup S$. One can
readily show that $G-E^{\prime}$ is acyclically colored by $\varphi$ and
$|E^{\prime}|\leq n-k$. If $k=k^{\prime}=4$, we additionally require from the
induction hypothesis that $|E^{\prime\prime}|\leq n^{\prime}-5$, which yields
in this case that $|E^{\prime}|\leq n-5$. If $k=4$ and $k^{\prime}=k-1$, then,
suppose $\varphi(V(G))=[4]$ and $\varphi(v)=4$, one can deduce from Lemma 7
that $G_{ij}$ are connected for all distinct $i,j\in[3]$ and hence prove in a
similar way as in the proof of Theorem 8 that $m(G,\varphi)=n-5$.

Assume $\varphi(v_{1})=\varphi(v_{3})$. First we prove that $m(G,\varphi)\leq
n-|\varphi(V(G))|$. Let $G^{\prime}$ be from $G$ by contracting $v_{1}vv_{3}$
to a new vertex $v^{\prime}$ and denote the coloring induced from $\varphi$ by
$\varphi^{\prime}$ so that $\varphi(v^{\prime})=\varphi(v_{1})$. Denote
$n^{\prime}:=|V(G^{\prime})|$ and
$k^{\prime}:=|\varphi^{\prime}(V(G^{\prime}))|$. We have $n^{\prime}=n-2\geq
5$ and $k^{\prime}=k$ or $k-1$. By the induction hypothesis and Lemma 4, there
exists $E^{\prime\prime}\subseteq
E(G^{\prime})\setminus\\{v^{\prime}v_{2},v^{\prime}v_{4}\\}$ such that
$G^{\prime}-E^{\prime\prime}$ is acyclically colored by $\varphi^{\prime}$ and
$|E^{\prime\prime}|=m(G^{\prime},\varphi^{\prime})\leq n^{\prime}-k^{\prime}$.
Note that any path joining $v_{1},v_{3}$ in $G-\\{v,v_{2},v_{4}\\}$
corresponds to a cycle containing $v^{\prime}$ in $G^{\prime}$ as
$v_{1},v_{3}$ have no common neighbor other than $v,v_{2},v_{4}$. Define
$S:=\\{vv_{2}\\}$ if $k^{\prime}=k$, and $S:=\emptyset$ if $k^{\prime}=k-1$.
Let $E^{\prime}:=E^{\prime\prime}\cup\\{v_{1}v_{2}\\}\cup S$. It is clear that
$|E^{\prime}|\leq n-k$ and $G-E^{\prime}$ is acyclically colored by $\varphi$
as $v_{1}v_{2}v_{3}v_{4}v_{1}$ is the only cycle that is possibly 2-colored in
$G-E^{\prime\prime}-v$.

It remains to show that if $k=4$, then $m(G,\varphi)\leq n-5$. If
$\varphi(v_{2})\neq\varphi(v_{4})$, we take $E^{\prime}:=E^{\prime\prime}$
with $|E^{\prime}|\leq n^{\prime}-4=n-6$ and it is easy to show that
$G-E^{\prime}$ is acyclically colored by $\varphi$. So we assume that
$\varphi(v_{2})=\varphi(v_{4})$. If $k^{\prime}=3$, then it follows from
Theorem 8 that $m(G,\varphi)\leq n-5$. So we assume $k^{\prime}=4$; in
particular, $|E^{\prime\prime}|\leq n^{\prime}-4$. If
$|E^{\prime\prime}|=m(G^{\prime},\varphi^{\prime})\leq n^{\prime}-5$, we take
$E^{\prime}:=E^{\prime\prime}\cup\\{vv_{2},v_{1}v_{2}\\}$, so
$|E^{\prime}|=|E^{\prime\prime}|+2\leq n-5$ and $G-E^{\prime}$ is acyclically
colored by $\varphi$. This yields that $m(G,\varphi)\leq|E^{\prime}|\leq n-5$.

Assume $m(G^{\prime},\varphi^{\prime})=|V(G^{\prime})|-4$. As
$|V(G^{\prime})|>4$, by the induction hypothesis, $G^{\prime}$ is not
4-connected, and hence contains separating triangles. As $G$ is 4-connected,
it follows that each separating triangle of $G^{\prime}$ contains $v^{\prime}$
and separates $v_{2}$ and $v_{4}$; an example is given in Figure 2. This
implies that $\mathcal{T}_{G^{\prime}}$ is a path $G_{1}^{\prime}\dots
G_{t}^{\prime}$ ($t\geq 2$), with end-vertex $G^{\prime}_{1}$ containing
$v_{2}$, and the other end-vertex $G^{\prime}_{t}$ containing $v_{4}$.

Denote by $\varphi^{\prime}_{i}$ the restriction of $\varphi^{\prime}$ on
$V(G_{i}^{\prime})$. By Lemma 6 and Theorem 8, precisely one graph
$G_{i}^{\prime}$ from $\mathcal{V}_{G^{\prime}}$ has
$|\varphi^{\prime}_{i}(V(G^{\prime}_{i}))|=4$,
$m(G^{\prime}_{i},\varphi_{i})=|V(G^{\prime}_{i})|-4$ and
$|\varphi^{\prime}_{j}(V(G_{j}))|=3$ for all $j\in[t]\setminus\\{i\\}$. By the
induction hypothesis, we know that $|V(G^{\prime}_{i})|\leq 4$ and hence
$G^{\prime}_{i}$ is isomorphic to $K_{4}$.

Note that $G_{i}^{\prime}$ is not a leaf of $\mathcal{T}_{G^{\prime}}$, for
otherwise, say $i=1$, then
$|\varphi^{\prime}(V(G^{\prime})\setminus\\{v_{2}\\}|=3$. This implies that
$\varphi(v_{2})\neq\varphi(v_{4})$, contradicting the above assumption.

Thus $|\varphi^{\prime}(V(G_{j}^{\prime}))|=3$ and
$\\{\varphi^{\prime}(v^{\prime}),\varphi^{\prime}(v_{2})\\}\subset\varphi^{\prime}(V(G_{j}^{\prime}))$
for $j\in\\{1,t\\}$. As $G_{i}^{\prime}$ is an internal vertex of
$\mathcal{T}_{G^{\prime}}$, we have
$\varphi^{\prime}(V(G_{1}^{\prime}))\neq\varphi^{\prime}(V(G_{t}^{\prime}))$.
Without loss of generality, we may assume that
$\varphi^{\prime}(V(G_{1}^{\prime}))=[4]\setminus\varphi(v)$ and
$\varphi^{\prime}(V(G_{t}^{\prime}))=\\{\varphi(v),\varphi^{\prime}(v^{\prime}),\varphi^{\prime}(v_{2})\\}$.
Let $T$ be the separating triangle of $G^{\prime}$ that is contained in
$G_{1}^{\prime}$. Write $V(T):=\\{v^{\prime},u,w\\}$ such that
$\varphi^{\prime}(u)=\varphi^{\prime}(v_{2})$. Note that
$\varphi^{\prime}(w)\neq\varphi(v)$. Let $C$ be the cycle induced by the
neighbors of $u$ in $G_{1}^{\prime}$ (see Figure 2(b) for an example) and
$e_{C}$ be an arbitrary edge of $C$. By Lemma 4, we may require
$E^{\prime\prime}\subseteq
E(G^{\prime})\setminus(\\{v^{\prime}v_{2},v^{\prime}v_{4}\\}\cup(E(C)\setminus\\{e_{C}\\}))$
as
$\varphi^{\prime}(v_{2})=\varphi^{\prime}(v_{4})=\varphi^{\prime}(u)\notin\varphi^{\prime}(V(C))$,
and hence $e_{C}\in E^{\prime\prime}$. Let
$E^{\prime}:=(E^{\prime\prime}\setminus\\{e_{C}\\})\cup\\{vv_{2},v_{1}v_{2}\\}$.
We have $|E^{\prime}|=|E^{\prime\prime}|+1\leq n-5$. It remains to show that
$G-E^{\prime}$ is acyclically colored by $\varphi$. Again, it is easy to show
that $G-E^{\prime}-e_{C}$ is acyclically colored by $\varphi$. Hence, any
cycle $K$ which uses only two colors in $G-E^{\prime}$ contains $e_{C}$ and
the two colors used in $K$ are
$\varphi^{\prime}(w),\varphi^{\prime}(v^{\prime})$. So $K$ does not contain
$v,v_{2},v_{4}$. If $\\{v_{1},v_{3}\\}\subset V(K)$, then after contracting
the path $v_{1}vv_{3}$, $K$ becomes the union of two edge-disjoint cycles in
$(G^{\prime}_{\varphi^{\prime}(v^{\prime})\varphi^{\prime}(w)}-E^{\prime\prime})+e_{C}$
(as $v_{1},v_{3}$ have no other common neighbors than $v,v_{2},v_{4}$), a
contradiction. If $|\\{v_{1},v_{3}\\}\cap V(K)|\leq 1$, then $K$ corresponds
to $C$. Since $C$ is a cycle separating $v_{2}$ and $v_{4}$ in $G^{\prime}$,
$K$ is a cycle separating $v_{2}$ and $v_{4}$ in $G$, which is however
impossible since $v_{2}vv_{4}$ is a path in $G$ not intersecting $K$.

Case 2: $d_{G}(v)=\delta(G)=5$.

Let $v_{1}v_{2}v_{3}v_{4}v_{5}v_{1}$ be the induced cycle on $N_{G}(v)$.

If $|\varphi(N_{G}(v))|=3$, we may assume that $\varphi(v_{1})=\varphi(v_{3})$
and $\varphi(v_{2})=\varphi(v_{4})$. As $G$ is 4-connected and $\delta(G)=5$,
we may assume that $v_{1},v_{3}$ have no common neighbor other than $v,v_{2}$.
Let $G^{\prime}$ be obtained from $G$ by contracting $v_{1}vv_{3}$ to a new
vertex $v^{\prime}$. We do not distinguish edges from
$E(G^{\prime})\setminus\\{v^{\prime}v_{2}\\}$ from their corresponding edges
in $G$. Set $\varphi^{\prime}(v^{\prime}):=\varphi(v_{1})$ and
$\varphi^{\prime}(u):=\varphi(u)$ for all $u\in
V(G^{\prime})\setminus\\{v^{\prime}\\}$. Denote $n^{\prime}:=|V(G^{\prime})|$
and $k^{\prime}:=|\varphi^{\prime}(V(G^{\prime}))|$. We have $n^{\prime}=n-2$
and $k^{\prime}=k$ or $k-1$. By Lemma 4 and the induction hypothesis, there
exists $E^{\prime\prime}\subseteq E(G^{\prime})\setminus\\{v^{\prime}v_{2}\\}$
such that $\varphi^{\prime}$ is an acyclic coloring of
$G^{\prime}-E^{\prime\prime}$ and
$|E^{\prime\prime}|=m(G^{\prime},\varphi^{\prime})\leq n^{\prime}-k^{\prime}$.
Set $S:=\\{vv_{2}\\}$ if $k^{\prime}=k$ and $S:=\emptyset$ if
$k^{\prime}=k-1$. Define $E^{\prime}:=E^{\prime\prime}\cup S$. It is easy to
show that $|E^{\prime}|\leq n-k-1$ and $\varphi$ is an acyclic coloring of
$G-E^{\prime}$.

If $|\varphi(N_{G}(v))|\geq 4$, we may assume that $\varphi(v_{i})=i$ for each
$i\in[4]$. Obtain $G^{\prime}$ from $G$ by deleting $v$ and adding edges
$v_{1}v_{3},v_{1}v_{4}$. Let $\varphi^{\prime}$ be the restriction of
$\varphi$ on $V(G)\setminus\\{v\\}$. Denote $n^{\prime}:=|V(G^{\prime})|$ and
$k^{\prime}:=|\varphi^{\prime}(V(G^{\prime}))|$. We have $n^{\prime}=n-1$ and
$k^{\prime}=k$ or $k-1$. By Lemma 4 and the induction hypothesis, there exists
$E^{\prime\prime}\subseteq
E(G^{\prime})\setminus\\{v^{\prime}v_{3},v^{\prime}v_{4}\\}$ such that
$\varphi^{\prime}$ is an acyclic coloring of $G^{\prime}-E^{\prime\prime}$ and
$|E^{\prime\prime}|=m(G^{\prime},\varphi^{\prime})\leq n^{\prime}-k^{\prime}$.
Set $S:=\\{vv_{5}\\}$ if $k^{\prime}=k$ and $S:=\emptyset$ if
$k^{\prime}=k-1$. Define $E^{\prime}:=E^{\prime\prime}\cup S$. It is easy to
show that $|E^{\prime}|\leq n-k$ and $\varphi$ is an acyclic coloring of
$G-E^{\prime}$. We remark that in this case we have $k>4$, thus we do not need
to consider the second statement. ∎

Figure 2: (a) A 4-colored plane triangulation $G$. (b) The plane triangulation
$G^{\prime}$ obtained from $G$ by contracting the path $v_{1}vv_{3}$. The
cycle $C$ consists of the thick edges.

The following corollary characterizes plane triangulations $G$ and colorings
$\varphi$ that satisfy the eqaulities $m(G,\varphi)=n-3$ and
$m(G,\varphi)=n-4$, respectively.

######  Corollary 10.

Let $G$ be a plane triangulation on $n$ vertices and $\varphi$ be a coloring
of $G$. Let $\mathcal{V}_{G}:=\\{G_{1},\dots,G_{t}\\}$ and $\varphi_{i}$ be
the restriction of $\varphi$ on $V(G_{i})$ for $i\in[t]$. We have that
$m(G,\varphi)=n-3$ if and only if $|\varphi(V(G))|=3$; and $m(G,\varphi)=n-4$
if and only if there exists $i\in[t]$ such that $G_{i}$ is isomorphic to
$K_{4}$ and $|\varphi_{j}(V(G_{j}))|=3$ for all $j\in[t]\setminus\\{i\\}$.

##  3 Acyclic 2CC transerval and upper bounds for $m_{k}(G)$

Let $G$ be a graph and $\varphi$ a coloring of $G$. We have shown upper bounds
on $m(G,\varphi)$ when $G$ is a plane triangulation. In this section, we show
that we can choose the 2CC transversal $E^{\prime}$ so that it induces a
forest as well as extend the results to general planar graphs.

######  Definition 11.

Let $G$ be a graph and $U\subseteq V(G)$. An edge set $E^{\prime}\subseteq
E(G)$ is _$U$ -acyclic_ if the graph induced by $E^{\prime}$ is a forest and
contains no path joining two distinct vertices of $U$. With abuse of notation,
we say an edge set is $H$-acyclic instead of $V(H)$-acyclic for any subgraph
$H$ of $G$, and if $H$ is a graph induced by a single edge $e$, we write
$e$-acyclic instead of $H$-acyclic.

######  Proposition 12.

Let $G$ be a plane triangulation and $\varphi$ be a proper coloring of $G$.
For any facial cycle $F$ of $G$, there exists an $F$-acyclic $2$CC transversal
$E_{F}$ with respect to $\varphi$.

###### Proof.

We prove by induction on $|V(G)|$. We shall assume
$|V(G)|>\max\\{6,|\varphi(V(G))|\\}$ as the small cases can be readily
verified.

Suppose $G$ has some separating triangle $T$. Let $A_{1}$ and $A_{2}$ be the
components of $G-T$, and for $i\in[2]$, $G_{i}$ be the subgraph of $G$ induced
by $V(A_{i})\cup V(T)$. Without loss of generality, assume that $F$ is a
facial cycle of $G_{1}$. By the induction hypothesis, we have an $F$-acyclic
2CC transversal $E_{F}^{1}\subseteq E(G_{1})$ of $G_{1}$ and a $T$-acyclic 2CC
transversal $E_{T}^{2}\subseteq E(G_{2})$ of $G_{2}$. It is easy to see that
the edge set $E_{F}:=E_{F}^{1}\cup E_{T}^{2}$ is an $F$-acyclic 2CC
transversal of $G$.

Henceforth, we assume that $G$ has no separating triangle and thus
$\delta(G)\geq 4$. Fix $v\in V(G)\setminus V(F)$ such that
$d_{G}(v)=\delta(G)\leq 5$. We consider two cases, depending on $d_{G}(v)=4$
or $5$.

Case 1: $d_{G}(v)=4$.

Let $v_{1}v_{2}v_{3}v_{4}v_{1}$ be the cycle induced by $N_{G}(v)$. Since
$|V(G)|>6$ and $G$ has no separating triangle, we can assume that
$v_{1},v_{3}$ have no common neighbor other than $v,v_{2},v_{4}$. If
$\varphi(v_{1})\neq\varphi(v_{3})$, we obtain $G^{\prime}$ from $G$ by
deleting $v$ and adding the edge $v_{1}v_{3}$, and color it with the coloring
$\varphi^{\prime}$ induced from $\varphi$. Clearly, $F$ remains a facial cycle
of $G^{\prime}$. By the induction hypothesis, there exists an $F$-acyclic 2CC
transversal $E_{F}^{\prime}\subseteq E(G^{\prime})$ of $G^{\prime}$. Set
$E_{F}:=(E_{F}^{\prime}\setminus\\{v_{1}v_{3}\\})\cup\\{vv_{2}\\}$. One can
readily check that $E_{F}$ is an $F$-acyclic 2CC transversal of $G$.

If $\varphi(v_{1})=\varphi(v_{3})$, obtain $G^{\prime}$ from $G$ by
contracting $v_{1}vv_{3}$ to a new vertex $v^{\prime}$ and denote the coloring
induced from $\varphi$ by $\varphi^{\prime}$ so that
$\varphi(v^{\prime})=\varphi(v_{1})$. Let $E_{F}^{\prime}\subseteq
E(G^{\prime})$ be an $F$-acyclic 2CC transversal of $G^{\prime}$. Recall that
$v_{1},v_{3}$ have no common neighbor other than $v,v_{2},v_{4}$, and hence
any path joining $v_{1},v_{3}$ in $G-\\{v,v_{2},v_{4}\\}$ corresponds to a
cycle containing $v^{\prime}$ in $G^{\prime}$. We construct $E_{F}$ as
follows.

  * •

If $E_{F}^{\prime}\cap\\{v^{\prime}v_{2},v^{\prime}v_{4}\\}=\emptyset$, then
$v_{1}v_{2}v_{3}v_{4}v_{1}$ is the only cycle in
$G-(E_{F}^{\prime}\cup\\{vv_{2}\\})$ that possibly uses only two colors. We
claim that there exists $j\in\\{1,3\\}$ such that
$E_{F}:=E_{F}^{\prime}\cup\\{vv_{2},v_{j}v_{2}\\}$ induces a forest not
connecting any distinct vertices from $V(F)$. Suppose it does not hold, then
for each $j\in\\{1,3\\}$, the graph induced by $E_{F}^{\prime}$ in $G$
contains some path joining $v_{j}$ and $v_{2}$, or contains two disjoint paths
each joining one vertex from $V(F)$ and one vertex of $v_{j},v_{2}$. In any
case, the graph induced by $E_{F}^{\prime}$ in $G^{\prime}$ contains some path
joining two vertices from $V(F)$ or some cycle, a contradiction. As $G-E_{F}$
is acyclically colored by $\varphi$, $E_{F}$ is the desired edge set.

  * •

If
$E_{F}^{\prime}\cap\\{v^{\prime}v_{2},v^{\prime}v_{4}\\}=\\{v^{\prime}v_{i}\\}$
for some $i\in\\{2,4\\}$, set
$E_{F}:=(E_{F}^{\prime}\setminus\\{v^{\prime}v_{i}\\})\cup\\{vv_{2},v_{1}v_{i},v_{3}v_{i}\\}$.
Similarly to the previous case, it can be shown that $G-E_{F}$ is acyclically
colored by $\varphi$ and the subgraph induced by $E_{F}$ has no cycle and no
path joining distinct vertices from $V(F)$.

  * •

If $\\{v^{\prime}v_{2},v^{\prime}v_{4}\\}\subseteq E_{F}^{\prime}$, then there
is a unique path $P$ in $G^{\prime}-E_{F}^{\prime}$ joining $v^{\prime}$ and
$v_{2}$ using only colors $\varphi(v_{1})$ and $\varphi(v_{2})$. Therefore $P$
can be viewed as a path in
$G-((E_{F}^{\prime}\setminus\\{v^{\prime}v_{2},v^{\prime}v_{4}\\})\cup
E(v_{1}v_{2}v_{3}v_{4}v_{1}))$ connecting $v_{2}$ and $v_{j}$ for some
$j\in\\{1,3\\}$. Since $v_{1},v_{3}$ have no common neighbor other than
$v,v_{2},v_{4}$ and the neighbor of $v^{\prime}$ in $P$ is not $v_{4}$, the
index $j$ is unique. Set
$E_{F}:=(E_{F}^{\prime}\setminus\\{v^{\prime}v_{2},v^{\prime}v_{4}\\})\cup\\{vv_{2},v_{j}v_{2},v_{1}v_{4},v_{3}v_{4}\\}$.
Similarly to the previous cases, it is easy to show that $E_{F}$ is
$F$-acyclic. It is left to show that $\varphi$ is an acyclic coloring of
$G-E_{F}$. Suppose to the contrary that there is some 2-colored cycle $C$ in
$G-E^{\prime}$. It is not hard to see that $C$ contains $v_{4-j}v_{2}$ but not
$v_{j}$. Then $C-v_{4-j}v_{2}$ is a path in $G^{\prime}-E_{F}^{\prime}$
connecting $v^{\prime}$ and $v_{2}$ yet different from $P$, a contradiction.

Case 2: $d_{G}(v)=5$.

Let $v_{1}v_{2}v_{3}v_{4}v_{5}v_{1}$ be the induced cycle on $N_{G}(v)$. If
$|\varphi(N_{G}(v))|=3$, we may assume that $\varphi(v_{1})=\varphi(v_{3})$
and $\varphi(v_{2})=\varphi(v_{4})$. Suppose $v_{1},v_{3}$ have a common
neighbor $u$ other than $v,v_{2}$ and $v_{2},v_{4}$ have a common neighbor
$u^{\prime}$ other than $v,v_{3}$. Since $G$ has no separating triangle,
$u=u^{\prime}$ and $d_{G}(v_{2})=d_{G}(v_{3})=4$. If $v_{2}$ or $v_{3}$ is not
incident to $F$, we may revise our choice of $v$ so that $d_{G}(v)=4$.
Otherwise, $F$ is the cycle $uv_{2}v_{3}u$ and since $d_{G}(v)=5$, there
exists some vertex $w\in V(G)\setminus\\{v,v_{1},v_{2},v_{3},v_{4},u\\}$ such
that $d_{G}(w)\leq 5$; we may replace $v$ by $w$. Therefore, without loss of
generality, we may assume that $v_{1},v_{3}$ have no common neighbor other
than $v,v_{2}$.

Obtain $G^{\prime}$ from $G$ by contracting $v_{1}vv_{3}$ to a new vertex
$v^{\prime}$ and denote the coloring induced from $\varphi$ by
$\varphi^{\prime}$ so that $\varphi(v^{\prime})=\varphi(v_{1})$. It is clear
that $F$ remains a facial cycle of $G^{\prime}$. Let $E_{F}^{\prime}\subseteq
E(G^{\prime})$ be an $F$-acyclic 2CC transversal of $G^{\prime}$. We construct
$E_{F}$ as follows.

  * •

If $v^{\prime}v_{2}\in E_{F}^{\prime}$, set
$E_{F}:=(E_{F}^{\prime}\setminus\\{v^{\prime}v_{2}\\})\cup\\{vv_{2},v_{1}v_{2},v_{2}v_{3}\\}$.

  * •

If $v^{\prime}v_{2}\notin E_{F}^{\prime}$, set
$E_{F}:=E_{F}^{\prime}\cup\\{vv_{2}\\}$.

In both cases it is easy to show that $E_{F}$ is an $F$-acyclic 2CC
transversal of $G$.

If $|\varphi(N_{G}(v))|>3$, we may assume that $\varphi(v_{i})=i$ for each
$i\in[4]$. Let $G^{\prime}$ be the graph obtained from $G$ by deleting $v$ and
adding edges $v_{1}v_{3},v_{1}v_{4}$. Let $\varphi^{\prime}$ be the
restriction of $\varphi$ on $V(G)\setminus\\{v\\}$. Let $E_{F}^{\prime}$ be an
$F$-acyclic 2CC transversal of $G$. One can easily show that
$E_{F}:=(E_{F}^{\prime}\setminus\\{v_{1}v_{3},v_{1}v_{4}\\})\cup\\{vv_{5}\\}$
is an $F$-acyclic 2CC transversal of $G$. ∎

We remark that the $F$-acyclic 2CC transversal $E_{F}$ found in Proposition 12
induces a forest of at least $|V(F)|=3$ components and hence has size at most
$|V(G)|-3$. In fact, an $F$-acyclic 2CC transversal of the optimal size
$m(G,\varphi)$ does exist due to the following observation. Note that for any
edge set $E^{\prime}\subseteq E(G)$, $G-E^{\prime}$ is acyclically colored by
a proper $k$-coloring $\varphi$ of $G$ if and only if $E(G)\setminus
E^{\prime}$ is an independent set of the direct sum of the graphic matroids of
$G_{ij}$ ($i,j\in[k]$). This yields the following corollary.

######  Corollary 13.

Let $G$ be a plane triangluation, $\varphi$ be a proper coloring of $G$ and
$F$ be a facial cycle of $G$. There exists an $F$-acyclic $2$CC transversal
$E^{\prime}\subseteq E(G)$ with $|E^{\prime}|=m(G,\varphi)$.

Next, we generalize the results to planar graphs.

######  Theorem 14.

Assume $G$ is a planar graph on $n$ vertices and $\varphi$ is a proper
coloring of $G$ with $|\varphi(V(G))|=k$. Let $U\subseteq V(G)$ that induces a
clique of size $|U|\leq 3$. There exists a $U$-acyclic $2$CC transversal
$E_{U}\subseteq E(G)$ with $|E_{U}|=m(G,\varphi)\leq n-k$.

###### Proof.

We prove by induction on $n$. It clearly holds when $n\leq k$. From now on we
consider $n>k$.

If $G$ has some separator $W\subset V(G)$ such that $|W|\leq 3$ and $W$
induces a clique, let $A_{1}$ be a component of $G-W$ and $A_{2}$ the union of
all other components. Denote by $G_{i}$ the subgraph of $G$ induced by
$V(A_{i})\cup W$ and by $\varphi_{i}$ the restriction of $\varphi$ on
$V(G_{i})$ ($i\in[2]$). Write $n_{i}:=|V(G_{i})|$ and
$k_{i}:=|\varphi_{i}(V(G_{i})|$. We have $n_{1}+n_{2}=n-|W|$ and
$k_{1}+k_{2}\geq k-|W|$. Without loss of generality, we require that
$U\subseteq V(G_{1})$. By the induction hypothesis, there exist a $U$-acyclic
2CC transversal $E_{U}^{\prime}$ of $G_{1}$ with $|E_{U}^{\prime}|\leq
n_{1}-k_{1}$ and a $W$-acyclic 2CC transversal $E_{W}^{\prime}$ of $G_{2}$
with $|E_{W}^{\prime}|\leq n_{2}-k_{2}$. It is easy to show that
$E_{U}:=E_{U}^{\prime}\cup E_{W}^{\prime}$ is a $U$-acyclic 2CC transversal
with $|E_{U}|\leq n-k$.

We assume that $G$ has no separator $W\subset V(G)$ such that $|W|\leq 3$ and
$W$ induces a clique. In particular, $G$ is 2-connected and every facial
boundary of $G$ is a cycle. We add to $G$ as many edges as possible such that
$\varphi$ remains as a proper coloring and $G$ remains as a plane graph. With
abuse of notation, we call the new graph $G$. It suffices to prove the
statement for the new graph $G$.

If $G$ is a triangulation, we apply Theorem 9 and Corollary 13 to conclude
that $G$ has some $U$-acyclic 2CC transversal $E_{U}$ with
$|E_{U}|=m(G,\varphi)\leq n-k$.

If any facial cycle of $G$ has a chord, then the end-vertices of the chord
form a separator of $G$, contradicting our assumption.

Assume $G$ is not a plane triangulation. As each facial cycle is an induced
cycle, and any two non-adjacent vertices of a face are colored by the same
color, there exists a facial cycle $v_{1}v_{2}v_{3}v_{4}v_{1}$ in $G$ such
that $\varphi(v_{1})=\varphi(v_{3})$ and $\varphi(v_{2})=\varphi(v_{4})$. If
$v_{1},v_{3}$ have 3 common neighbors and $v_{2},v_{4}$ have 3 common
neighbors, then $G$ must be isomorphic to the plane graph obtained from the
octahedron by deleting one vertex since we assume that $G$ has no separating
triangle. One can easily verify that the statement holds for this graph. Thus,
without loss of generality, we assume that $v_{1},v_{3}$ have no common
neighbor other than $v_{2},v_{4}$. Let $G^{\prime}$ be obtained from $G$ by
identifying $v_{1}$ and $v_{3}$ as a new vertex $v^{\prime}$ and
$\varphi^{\prime}$ be the coloring of $G^{\prime}$ induced from $\varphi$.
Denote $n^{\prime}:=|V(G^{\prime})|$ and
$k^{\prime}:=|\varphi^{\prime}(V(G^{\prime}))|$. We have $n^{\prime}=n-1$ and
$k^{\prime}=k$. Moreover, we can view $U$ as a vertex set of $G^{\prime}$
since $U$ contains at most one of $v_{1},v_{3}$. By the induction hypothesis,
we have a $U$-acyclic 2CC transversal $E_{U}^{\prime}$ of $G^{\prime}$ with
$|E_{U}^{\prime}|=m(G^{\prime},\varphi^{\prime})\leq n^{\prime}-k^{\prime}$.
We construct $E_{U}$ as follows. Since the approach is similar to that in the
proof of Proposition 12, some details will be omitted.

  * •

If $E_{U}^{\prime}\cap\\{v^{\prime}v_{2},v^{\prime}v_{4}\\}=\emptyset$, then
there exists $j\in\\{1,3\\}$ such that
$E_{U}:=E_{U}^{\prime}\cup\\{v_{j}v_{2}\\}$ is $U$-acyclic.

  * •

If
$E_{U}^{\prime}\cap\\{v^{\prime}v_{2},v^{\prime}v_{4}\\}=\\{v^{\prime}v_{i}\\}$
for some $i\in\\{2,4\\}$, set
$E_{U}:=(E_{U}^{\prime}\setminus\\{v^{\prime}v_{i}\\})\cup\\{v_{1}v_{i},v_{3}v_{i}\\}$.

  * •

If $\\{v^{\prime}v_{2},v^{\prime}v_{4}\\}\subseteq E_{U}^{\prime}$, then there
is a unique path $P$ in $G^{\prime}-E_{U}^{\prime}$ joining $v^{\prime}$ and
$v_{2}$ using only colors $\varphi(v_{1})$ and $\varphi(v_{2})$. We can view
$P$ as a path in
$G-((E_{F}^{\prime}\setminus\\{v^{\prime}v_{2},v^{\prime}v_{4}\\})\cup
E(v_{1}v_{2}v_{3}v_{4}v_{1}))$ connecting $v_{2}$ and $v_{j}$ for some unique
$j\in\\{1,3\\}$. Set
$E_{U}:=(E_{U}^{\prime}\setminus\\{v^{\prime}v_{2},v^{\prime}v_{4}\\})\cup\\{v_{j}v_{2},v_{1}v_{4},v_{3}v_{4}\\}$.

It is not hard to verify that the edge set $E_{U}$ constructed above is a
$U$-acyclic 2CC transversal with $|E_{U}|\leq n-k$. This completes the proof.
∎

######  Corollary 15.

Let $G$ be a planar graph on $n$ vertices. If $n\geq 5$, then $m_{4}(G)\leq
n-5$. If $G$ is $3$-colorable, then $m_{3}(G)\leq n-3$.

######  Theorem 16.

There are infinitely many $4$-connected planar graphs $G$ with
$m_{4}(G)=|V(G)|-5$, and infinitely many $3$-colorable planar graphs with
$m_{3}(G)=|V(G)|-3$.

###### Proof.

It follows from Corollary 10 that for any 3-colorable plane triangulation $G$,
$m_{3}(G)=|V(G)|-3$.

Let $G$ be the 4-connected plane triangulation obtained by joining two
independent vertices $u,v$ to every vertex of a cycle $C$ on $n-2$ vertices
with $n\geq 7$ odd. It is obvious that $G$ is not 3-colorable. Let $\varphi$
be any 4-coloring of $G$. Then, without loss of generality,
$\varphi(V(C))=[3]$ and $\varphi(u)=\varphi(v)=4$. For any $i\in[3]$, $G_{i4}$
is a connected plane graph with $|\varphi^{-1}(i)|$ faces, and for
$i,j\in[3]$, $G_{ij}$ is acyclic. Therefore
$m(G,\varphi)=\sum_{i\in[3]}(|\varphi^{-1}(i)|-1)=n-5$. ∎

##  4 Upper bounds for $m^{\prime}_{k}(G)$

In this section we study the problem of how many edges we need to remove from
a planar graph in order to make it acyclic $k$-colorable for $k=3,4$.

######  Theorem 17.

Let $G$ be a planar graph on $n$ vertices. We have $m_{3}(G)\leq(13n-42)/10$
and $m_{4}(G)\leq(3n-12)/5$.

###### Proof.

We first prove that $m_{4}(G)\leq(3n-12)/5$. As every plane graph is a
spanning subgraph of some plane triangulation, we may assume that $G$ is a
plane triangulation on $n$ vertices. Let $\varphi:V(G)\rightarrow[5]$ be an
acyclic 5-coloring of $G$. Without loss of generality, assume that

$\displaystyle\sum_{v\in\varphi^{-1}(5)}(d_{G}(v)-3)\leq\frac{1}{5}\sum_{v\in
V(G)}(d_{G}(v)-3)=\frac{3n-12}{5}.$

Let $v$ be any vertex in $\varphi^{-1}(5)$. Since the neighbors of $v$ span
some cycle and $\varphi$ is acyclic, there exist $v_{1},v_{2},v_{3}\in
N_{G}(v)$ whose colors are pairwise distinct. Define $E_{v}$ to be the set of
edges incident to $v$ other than $vv_{1},vv_{2}$ and $vv_{3}$, and set
$\varphi^{\prime}(v)$ to be the color from $[4]$ other than
$\varphi(v_{1}),\varphi(v_{2}),\varphi(v_{3})$. To complete the construction,
we set $E^{\prime}:=\bigcup_{v\in\varphi^{-1}(5)}E_{v}$ and set
$\varphi^{\prime}(u):=\varphi(u)$ for all
$u\in\bigcup_{i\in[4]}\varphi^{-1}(i)$. It is readily to verify that
$\varphi^{\prime}$ is a proper 4-coloring of $G^{\prime}:=G-E^{\prime}$ and
$|E^{\prime}|=\sum_{v\in\varphi^{-1}(5)}(d_{G}(v)-3)\leq\frac{3n-12}{5}$.
Suppose $\varphi^{\prime}$ is not an acyclic coloring of $G^{\prime}$, then
there is a cycle $C$ contained in
$\varphi^{\prime-1}(i)\cup\varphi^{\prime-1}(j)$ for some distinct
$i,j\in[4]$. Note that $C$ cannot contain any $v\in\varphi^{-1}(5)$ since $v$
has precisely three neighbors of three different colors in $G^{\prime}$.
Therefore $C$ is contained in
$G^{\prime}[(\varphi^{\prime-1}(i)\cup\varphi^{\prime-1}(j))\setminus\varphi^{-1}(5)]=G[\varphi^{-1}(i)\cup\varphi^{-1}(j)]$,
a contradiction.

This approach can be repeated to show that $m_{3}(G)\leq(13n-42)/10$. More
precisely, we may assume that

$\displaystyle\sum_{v\in\varphi^{\prime-1}(4)}(d_{G^{\prime}}(v)-2)\leq\frac{1}{4}\sum_{v\in
V(G^{\prime})}(d_{G^{\prime}}(v)-2)=\frac{4n-12-2|E^{\prime}|}{4}.$

It is not hard to see that for any $v\in V(G^{\prime})$,
$|\varphi^{\prime}(N_{G^{\prime}}(v))|\geq 2$. Let $v\in\varphi^{\prime-1}(4)$
and $v_{1},v_{2}\in N_{G^{\prime}}(v)$ be of different colors. Define
$E_{v}^{\prime}$ to be the set of edges incident to $v$ other than $vv_{1}$
and $vv_{2}$, and set $\varphi^{\prime\prime}(v)$ to be the color from $[3]$
other than $\varphi(v_{1}),\varphi(v_{2})$. Set
$E^{\prime\prime}:=E^{\prime}\cup\bigcup_{v\in\varphi^{\prime-1}(4)}E_{v}^{\prime}$
and set $\varphi^{\prime\prime}(u):=\varphi^{\prime}(u)$ for all
$u\in\bigcup_{i\in[3]}\varphi^{\prime-1}(i)$. Again, it is readily to verify
that $\varphi^{\prime\prime}$ is a proper 3-coloring of
$G^{\prime\prime}:=G-E^{\prime\prime}$ and

$\displaystyle|E^{\prime\prime}|=|E^{\prime}|+\sum_{v\in\varphi^{\prime-1}(4)}(d_{G^{\prime}}(v)-2)\leq\frac{13n-42}{10}.$

Similarly as before, one can show that $\varphi^{\prime\prime}$ is an acyclic
3-coloring of $G^{\prime\prime}$ and hence the result follows. ∎

We remark that there exist infinitely many planar graphs $G$ on $n$ vertices
so that $G-E^{\prime}$ is not acyclically $4$-colorable for any
$E^{\prime}\subseteq E(G)$ with $|E^{\prime}|<(n-2)/4$. Let $H$ be a 2-face-
colorable triangulation and $\mathcal{T}$ be a family of $|E(H)|/3$ edge-
disjoint facial triangles of $H$. Let $G$ be obtained from $H$ by replacing
each triangle from $\mathcal{T}$ by an octahedron. Therefore $E(G)$ is
partitioned into $|E(H)|/3$ octahedra, and $n=|V(H)|+|E(H)|=4|V(H)|-6$. As the
octahedron is not acyclically 4-colorable, any $E^{\prime}\subseteq E(G)$
satisfying that $G-E^{\prime}$ is acyclically 4-colorable has size at least
$|E(H)|/3=\frac{n-2}{4}$.

## Acknowledgments

The research of On-Hei Solomon Lo was supported by a Postdoctoral Fellowship
of Japan Society for the Promotion of Science and by Natural Sciences and
Engineering Research Council of Canada. The research of Ben Seamone was
supported by Natural Sciences and Engineering Research Council of Canada. The
research of Xuding Zhu was supported by National Natural Science Foundation of
China grant NSFC 11971438 and U20A2068.

## References

  * [1] O. V. Borodin.  On acyclic colorings of planar graphs.  Discrete Math., 25(3):211–236, 1979.
  * [2] O. V. Borodin.  Colorings of plane graphs: A survey.  Discrete Math., 313(4):517–539, 2013.
  * [3] B. Grünbaum.  Acyclic colorings of planar graphs.  Israel J. Math., 14:390–408, 1973.
  * [4] D. Mondal, R. I. Nishat, Md. S. Rahman, and S. Whitesides.  Acyclic coloring with few division vertices.  J. Discrete Algorithms, 23:42–53, 2013.


On Realization and Isomorphism Problems
for Formal Matrix Rings

Piotr Krylov,

Tomsk National Recearch

State University<EMAIL_ADDRESS>
Askar Tuganbaev

National Recearch University <<MPEI>>,

Lomonosov Moscow State University

<EMAIL_ADDRESS>
Abstract. We consider realization and isomorphism problems for formal matrix
rings over a given ring. Principal multiplier matrices of such rings play an
important role in this case.
The work of A.A.Tuganbaev is supported by Russian Scientific Foundation,
project 22-11-00052.

Key words: formal matrix ring, principal multiplier matrix

MSC Classification. 16R99; 16D10

##  1 Introduction

Formal matrix rings (or generalized matrix rings) over a given ring attract a
lot of attention from specialists. This is natural, since such rings regularly
appear in the theory of rings and modules. In particular, they play an
important role in the study of a number of classes of Artinian rings and
algebras (see [3], [4]). They also provide a variety of examples for the
general theory of rings and modules. A number of aspects of the theory of
formal matrix rings are presented in the book [8].

There is one interesting form of formal matrix rings. In the case of $2\times
2$ matrices, they appeared in [6]; in the case of $n\times n$ matrices, they
appeared in [11]. We mean formal matrix rings over a given ring $R$ (or one
says <<with values ??in $R$>>). This means that a particular formal matrix
ring contains the same ring $R$ in all positions. The class of such rings is a
direct extension of the usual ring of $n\times n$ matrices $M(n,R)$. However,
the properties of formal matrix rings over the ring $R$ may be very different
from the properties of the ring $M(n,R)$. Chapter 3 of the book [8] contains
an exposition of some questions about formal matrix rings over $R$, and at the
beginning of this chapter three problems about formal matrix rings are
formulated. In chapters 18-20, these problems are solved for some types of
formal matrix rings over $R$. This paper is devoted to two of the three
indicated tasks. Namely, the realization problem I and the isomorphism problem
III. These problems are considered in[1], [2], [5], [12], [13].

In this paper, we consider only associative rings with non-zero identity
element. If $R$ is a ring, then $M(n,R)$ is the ordinary ring of all $n\times
n$ matrices with values in the ring $R$. For an arbitrary ring $S$, the prime
radical of $S$ is denoted by $P(S)$.

##  2 Formal Matrix Rings over a Given Ring

Let us briefly recall the definition of a formal matrix ring. We fix a
positive integer $n\geq 2$. Let $R_{1},\ldots,R_{n}$ be $n$ rings and let
$M_{ij}$ be $R_{i}$-$R_{j}$-bimodules such that $M_{ii}=R_{i}$,
$i,j=1,\ldots,n$. We assume that for any subscripts $i,j,k=1,\ldots,n$, we
have an $R_{i}$-$R_{k}$-bimodule homomorphism $M_{ij}\otimes_{R_{j}}M_{jk}\to
M_{ik}$. We denote by $K$ the set of all $n\times n$ matrices with values in
the bimodules $M_{ij}$. The set $K$ is a ring with respect to standard matrix
operations of addition and multiplication. Matrices are multiplied by applying
the bimodule homomorphisms mentioned above. The ring $K$ is called a formal
matrix ring (or a generalized matrix ring) of order $n$. It can be written in
the following form:

$K=\begin{pmatrix}R_{1}&M_{12}&\ldots&M_{1n}\\\ M_{21}&R_{2}&\ldots&M_{2n}\\\
\ldots&\ldots&\ldots&\ldots\\\ M_{n1}&M_{n2}&\ldots&R_{n}\end{pmatrix}.$

Let $R$ be a ring. If $K$ is a formal matrix ring such that $M_{ij}=R$ for all
$i$ and $j$, then it is called a formal matrix ring over the ring $R$ or
formal matrix ring with values in the ring $R$. Such rings can be defined
directly. Namely, let $\\{s_{ijk}\,|\,i,j,k=1,\ldots,n\\}$ be some set of
central elements of the ring $R$ such that

$s_{iik}=1=s_{ikk},\;s_{ijk}\cdot s_{ik\ell}=s_{ij\ell}\cdot s_{jk\ell}$
$None$

for all subscripts $i,j,k,\ell=1,\ldots,n$. For arbitrary $n\times n$ matrices
$A=(a_{ij})$ and $B=(b_{ij})$ with values in $R$, we define a new
multiplication by setting

$AB=C=(c_{ij}),\,\text{ where }c_{ij}=\sum_{k=1}^{n}s_{ikj}a_{ik}b_{kj}.$

As a result, we obtain a ring which is denoted by $K$ or $M(n,R,\Sigma)$,
where $\Sigma$ is the set of all $s_{ijk}$. The set $\Sigma$ is called the
multiplier system and the elements of $\Sigma$ are called multipliers of the
ring $K$. If all $s_{ijk}$ are equal to $1$, then we obtain the ordinary
matrix ring $M(n,R)$.

Let $\tau$ be a permutation of degree $n$. If $\Sigma=\\{s_{ijk}\\}$ is some
multiplier system, then we set $t_{ijk}=s_{\tau(i)\tau(j)\tau(k)}$. Then
$\\{t_{ijk}\\}$ also is a multiplier system, since it satisfies identities
$(1)$. We denote it by $\tau\Sigma$. Consequently, there exists a formal
matrix ring $M(n,R,\tau\Sigma)$. The rings $M(n,R,\Sigma)$ and
$M(n,R,\tau\Sigma)$ are isomorphic to each other under the correspondence
$A\to\tau A$, where $A=(a_{ij})$ and $\tau A=(a_{\tau(i)\tau(j)})$.

Several matrices can be associated with the ring $M(n,R,\Sigma)$. We set
$S=(s_{iji})$ and $S_{k}=(s_{ikj})$, for any $k=1,\ldots,n$. These matrices
are called multiplier matrices of the ring $M(n,R,\Sigma)$. The matrix $S$ is
symmetrical. Following [5], we call it a principal multiplier matrix. In [5],
the matrices $(s_{ijk})$ and $(s_{kij})$ are also used, $k=1,\ldots,n$. It is
clear that the matrices $\tau S$ and $\tau S_{k}$ are the corresponding
multiplier matrices of the ring $M(n,R,\tau\Sigma)$.

Until the end of the article, we assume that $K$ is a formal matrix ring over
a given ring $R$. In addition, with the exception of Theorem 4.3, every
multiplier $s_{ijk}$ is equal to $0$ or $1$. Therefore, all multiplier
matrices of such a ring are $(01)$-matrices. For brevity, we call the ring $K$
a $(01)$-formal matrix ring.

The following result can be easily obtained from identities $(1)$.

Lemma 2.1. For multipliers $s_{iji}$, $s_{jkj}$, and $s_{kik}$ of some
$(01)$-formal matrix ring, one of the following possibilities takes place
(where $i\neq j$, $j\neq k$, and $k\neq i$).

1) All three elements are equal to $1$.

2) Some two of these three elements are equal to $0$ and the third element is
$1$.

3) All three elements are equal to $0$.

It is useful to introduce the notion of an abstract multiplier matrix. Let
$T=(t_{ij})$ be a symmetrical $n\times n$ $(01)$-matrix over the ring $R$ such
that all elements of the main diagonal are equal to $1$ and one of assertions
1)–3) of Lemma 2.1 is true for any three elements $t_{ij}$, $t_{jk}$, $t_{ki}$
with pairwise distinct subscripts. We call such a matrix $T$ a principal
multiplier matrix.

Lemma 2.2 [7], [9, Chapter 12]. For any principal $n\times n$ multiplier
matrix $T$, there exists a permutation $\sigma$ of degree $n$ such that the
matrix $\sigma T$ is of canonical form.

By canonical form it is meant that the matrix $\sigma T$ can be represented in
such a block form that blocks of 1’s are on the main diagonal, and zeros are
in all other positions.

Under the conditions of Lemma 2.2, we say that the matrix $T$ is reduced to
the canonical form. It follows from Lemma 2.1 that the principal multiplier
matrix of any $(01)$-formal matrix ring can be reduced to the canonical form.

Remark 2.3. We clarify that the canonical form is determined up to permutation
of blocks on the main diagonal and up to the corresponding permutation of
remaining blocks.

##  3 Realization Problem for $(01)$-Formal Matrix Rings

Section 1 contains information on the realization problem. The problem is
related to description of multiplier matrices as abstract matrices.

Theorem 3.1. Let $T$ be some principal multiplier matrix. There exists a
$(01)$-formal matrix ring such that principal multiplier matrix coincides with
$T$.

Proof. Based on Lemma 2.2, we assume that the matrix $T$ is of canonical form.
For all subscripts $i,j,k\in\\{1,\ldots,n\\}$, we define an element $s_{ijk}$
of the ring $R$ such that $s_{ijk}=1$ if one of the pairs $(i,j)$ or $(j,k)$
takes a position in some block on the main diagonal of the matrix $T$.
Otherwise, we assume that $s_{ijk}=0$. The set $\Sigma$ of all such elements
$s_{ijk}$ satisfies identities $(1)$. Therefore, the ring $M(n,R,\Sigma)$
exists. The matrix $T$ is a principal multiplier matrix of the ring
$M(n,R,\Sigma)$. $\square$

Multipliers of the ring $M(n,R,\Sigma)$, constructed in the proof of Theorem
3.1, satisfy the following condition:

  * •

$s_{ijk}=0$ for any pairwise distinct subscripts $i,j,k$ such that
$s_{iji}=0=s_{jkj}$.

We say that some $(01)$-formal matrix ring is a ring of the form $K_{0}$ if
its multipliers satisfy the above condition $\bullet$. By the use of a
principal multiplier matrix of such a ring, all remaining multiplier matrices
can be restored.

We note that papers [7], [9] and [10] contain various material on automorphism
groups of $(01)$-formal matrix rings.

##  4 Isomorphism Problem for Formal Matrix Rings

In [8, Chapter 16], the following isomorphism problem III for formal matrix
rings is formulated:

  * •

When two multiplier systems define isomorphic formal matrix rings?

We consider this problem for $(01)$-formal matrix rings.

We say that a ring $R$ satisfies $(n,m)$-condition if for any positive
integers $n$ and $m$, we have $m=n$ provided the rings $M(n,R)$ and $M(m,R)$
are isomorphic. For example, the $(n,m)$-condition holds if the ring $R$ is
commutative, or local, or is a principal left (right) ideal domain.

A ring $S$ is said to be indecomposable if $0$ and $1$ are only central
idempotents of $S$.

Theorem 4.1. We assume that the factor ring $R/P(R)$ is indecomposable and
satisfies the $(n,m)$-condition and $K_{1}$, $K_{2}$ are $(01)$-formal matrix
rings with principal multiplier matrices $S$ and $T$, respectively. The
following assertions are true.

1. If the rings $K_{1}$ and $K_{2}$ are isomorphic to each other, then the matrices $S$ and $T$ have the same canonical forms.

2. If $K_{1}$ and $K_{2}$ are $(01)$-formal matrix rings of the form $K_{0}$ and the canonical forms of the matrices $S$ and $T$ coincide, then the rings $K_{1}$ and $K_{2}$ are isomorphic to each other.

Proof. 1. By Lemma 2.2, we can assume that the matrices $S$ and $T$ are given
in the canonical form. Let us assume that $K_{1}\cong K_{2}$. Then there
exists a ring isomorphism

$\gamma\colon K_{1}/P(K_{1})\to K_{2}/P(K_{2}).$

The structure of the prime radicals $P(K_{1})$ and $P(K_{2})$ is known (see
[8, Corollary 17.1] and the paragraph after the corollary). We also know the
block structure of matrices $S$ and $T$. With the use of this information, we
obtain the relations

$K_{1}/P(K_{1})=P_{1}\times\ldots\times P_{k}\,\text{ and
}\,K_{2}/P(K_{2})=Q_{1}\times\ldots\times Q_{\ell},$

where $k$ (resp., $\ell$) the number of blocks on the main diagonal of the
matrix $S$ (resp., $T$). In addition, all $P_{i}$ and $Q_{j}$ are full matrix
rings of some orders. Since the ring $R/P(R)$ is indecomposable, all the rings
$P_{i}/P(P_{i})$ and $Q_{j}/P(Q_{j})$ are indecomposable.

At this point, we note that there is an analogue of [9, Lemma 9.6] (or [10,
Lemma 6.1]) on automorphisms of direct products of indecomposable rings for
isomorphisms between direct products of indecomposable rings. Therefore,
$k=\ell$ and there exists a permutation $\tau$ of degree $k$ such that the
restriction $\gamma$ to $P_{i}$ is an isomorphism $P_{i}\to Q_{\tau(i)}$,
$i=1,\ldots,k$. Consequently, canonical forms matrices $S$ and $T$ coincide.

2. Let $\\{s_{ijk}\\}$ (resp., $\\{t_{ijk}\\}$) be the set of all multipliers of the ring $K_{1}$ (resp., $K_{2}$). As noted, multipliers of the form $s_{iji}$, i.e., elements of the principal multiplier matrix $S$, define all remaining multipliers $s_{ijk}$; the same is true for multipliers of the ring $K_{2}$. Therefore, $s_{ijk}=t_{ijk}$, for all $i,j,k$. Therefore, we have the relation $K_{1}=K_{2}$. $\square$

Corollary 4.2. The factor rings $K_{1}/P(K_{1})$ and $K_{2}/P(K_{2})$ are
isomorphic to each other if and only if the matrices $S$ and $T$ have the same
canonical form.

We introduce one more class of formal matrix rings over a given ring, we also
prove some theorem related to the isomorphism problem, for such rings.

We fix some central element $s$ of the ring $R$ such that $s^{2}\neq 1$ and
$s^{2}\neq s$. In addition, let $K$ be a formal matrix ring over $R$ such that
every multiplier of $K$ is equal to $1$ or $s$. We denote the defined ring by
$M(n,R,s)$ and call it a $(s1)$-formal matrix ring. The rings $M(n,R,s)$ are
studied in Chapters 18–19 of the book [8]. Relationships between the rings
$M(n,R,s)$ and crossed matrix ring are known (see [4]). In [5, Lemma 4.7], it
is proved that the principal multiplier of the matrix ring $M(n,R,s)$
determines all other multiplier matrices. For $(01)$-formal matrix rings, a
similar assertion does not appear to be true.

Let $S$ be the principal multiplier matrix of some ring $M(n,R,s)$. According
to [8, Lemma 18.2], there exists a permutation $\tau$ of degree $n$ such that
the matrix $\tau S$ is of canonical form. This means that the matrix $\tau S$
can be presented in a block form such that the main diagonal contains blocks
consisting of $1$s and the element $s$ is in all remaining positions.

Theorem 4.3. Let the factor ring $R/P(R)$ be indecomposable and satisfy the
$(n,m)$-condition. For $(s1)$-formal matrix rings $K_{1}$ and $K_{2}$ over
$R$, where $s\in P(R)$, the following assertion is true.
The rings $K_{1}$ and $K_{2}$ are isomorphic to each other if and only if for
the rings $K_{1}$ and $K_{2}$, the canonical forms of principal multiplier
matrices coincide.

Proof. We assume that principal multiplier matrices for the rings $K_{1}$ and
$K_{2}$ already are of canonical form.

Necessity. If consider that $s\in P(R)$, then, in fact, we can repeat the
proof of Theorem 4.1(1).

Sufficiency. Principal multiplier matrices for the rings $K_{1}$ and $K_{2}$
uniquely define all remaining multiplier matrices, see [5, Lemma 4.7].
Therefore, we can repeat the argument from the proof of Theorem 4.1(2).
$\square$

Remark 4.4. In [5, Theorem 4.12], a result, which is similar to Theorem 4.3,
is proved for a left Artinian ring $R$.

## References

  * [1] A. N. Abyzov and D. T. Tapkin. Formal matrix rings and their isomorphisms // Sib. Mat. Zh. – 2015. – Vol. 56, no. 6. P. 955–967.
  * [2] A. N. Abyzov and D. T. Tapkin. On certain classes of formal matrix rings // Russian Mathematics. – 2015. – Vol. 59, no. 3. – P. 1–12.
  * [3] Auslander M., Reiten I., Smalø S.O. Representation Theory of Artin Algebras. – Cambridge University Press, Cambridge, 1995.
  * [4] Baba Y., Oshiro K. Classical Artinian Rings and Related Topics. – World Scientific, New Jersey–London–Singapore, 2009.
  * [5] Chen W., Deng G., Su H. On the Binary System of Factors of Formal Matrix Rings // Czech. Math. J. – 2020. – Vol. 70. – P. 693–709.
  * [6] Krylov P.A. Isomorphisms of generalized matrix rings // Algebra and Logic. – 2008. – Vol. 47, no. 4. – P. 258–262.
  * [7] Krylov P.A., Norbosambuev T.D. Automorphisms of formal matrix algebras // Sib. Mat. Zh. – 2018. – Vol. 59, no. 5. – P. 1116–1127.
  * [8] Krylov P.A., Tuganbaev A.A. Formal Matrices, Springer-Verlag, Berlin, 2017.
  * [9] Krylov P.A., Tuganbaev A.A. Automorphism groups of formal matrix rings // Journal of Mathematical Sciences (Springer). – 2021. – Vol. 258, no. 2. – P. 222–249.
  * [10] Krylov P.A., Tuganbaev A.A. Automorphisms of Formal Matrix Rings // arXiv:2204.13332 [math.RA]. – 2022. https://doi.org/10.48550/arXiv.2204.13332
  * [11] Tang G., Zhou Y. A class of formal matrix rings // Linear Algebra Appl. – 2013. – Vol. 438, no. 12. – P. 4672–4688.
  * [12] D. T. Tapkin. Formal matrix rings and a generalization of an incidence algebra (Russian) // Chebyshev. Sb. – 2015. – Vol. 16, no. 3. – P. 442–449.
  * [13] D. T. Tapkin. Isomorphisms of formal matrix incidence rings // Russian Mathematics. – 2017. – Vol. 61. – P. 73–79.