11institutetext: University of Augsburg, Germany, 11email:
<EMAIL_ADDRESS>22institutetext: University of Bucharest,
Romania, 22email<EMAIL_ADDRESS>University of
Augsburg, Germany, 33email<EMAIL_ADDRESS>44institutetext:
University of Augsburg, Germany, 44email<EMAIL_ADDRESS>55institutetext: University of Augsburg, Germany, 55email:
<EMAIL_ADDRESS>
# Approximating Maximum Edge 2-Coloring
by Normalizing Graphs††thanks: A preliminary version of this paper was
presented at WAOA 2023. ††thanks: Partially supported by DFG Grant 439522729
(Heisenberg-Grant) and DFG Grant 439637648 (Sachbeihilfe). Partially supported
by a grant of the Ministry of Research, Innovation and Digitization, CNCS -
UEFISCDI, project number PN-III-P1-1.1-TE-2021-0253, within PNCDI III.

Tobias Mömke 11 0000-0002-2509-6972 Alexandru Popa 22 0000-0002-7123-1880 Aida
Roshany-Tabrizi 33 0009-0003-3607-9611 Michael Ruderer 44 0009-0009-1968-4821
Roland Vincze 55 0000-0002-5997-6564

###### Abstract

In a simple, undirected graph $G$, an edge $2$-coloring is a coloring of the
edges such that no vertex is incident to edges with more than 2 distinct
colors. The problem maximum edge $2$-coloring (ME2C) is to find an edge
$2$-coloring in a graph $G$ with the goal to _maximize_ the number of colors.
For a relevant graph class, ME2C models anti-Ramsey numbers and it was
considered in network applications. For the problem a $2$-approximation
algorithm is known, and if the input graph has a perfect matching, the same
algorithm has been shown to have a performance guarantee of $5/3\approx
1.667$. It is known that ME2C is -hard and that it is UG-hard to obtain an
approximation ratio better than $1.5$. We show that if the input graph has a
perfect matching, there is a polynomial time $1.625$-approximation and if the
graph is claw-free or if the maximum degree of the input graph is at most
three (i.e., the graph is subcubic), there is a polynomial time
$1.5$-approximation algorithm for ME2C.

###### Keywords:

Approximation Algorithms Edge 2-Coloring Matchings

##  1 Introduction

In a simple, undirected graph $G$, an edge $2$-coloring is a coloring of the
edges such that no vertex is incident to edges with more than 2 distinct
colors. The problem maximum edge $2$-coloring (ME2C) is to find an edge
$2$-coloring in $G$ that uses a _maximal_ number of colors. Formally, we aim
to compute a coloring $\chi\colon E(G)\rightarrow\mathbb{N}$ that maximizes
$|\\{c\in\mathbb{N}\mid\chi(e)=c\text{ for an $e\in E(G)$}\\}|$, such that for
each vertex $v\in V(G)$, $|\\{c\in\mathbb{N}\mid\chi(e)=c\text{ for an $e$
incident to $v$}\\}|\leq 2$ holds.

Maximum edge $2$-coloring is a particular case of anti-Ramsey numbers and has
been considered in combinatorics. For given graphs $G$ and $H$, the _anti-
Ramsey number_ $\textrm{ar}(G,H)$ is defined to be the maximum number of
colors in an edge-coloring that does not produce a rainbow copy of $H$ in $G$,
i.e., a copy of $H$ in $G$ with every edge of $H$ having a unique color.
Classically, the graph $G$ is a large complete graph and $H$ is from a
particular graph class. If $H$ is a star with three leaves and $G$ is an
arbitrary graph, the anti-Ramsey number is precisely the maximum number of
colors in an edge $2$-coloring.

The study of anti-Ramsey numbers was initiated by Erdős, Simonovits and Sós in
1975 [8]. Since then, there have been a large number of results on the topic
including the cases where $G=K_{n}$ and $H$ is a cycle [8, 19, 3], tree [15,
14], clique [12, 8, 4], matching [23, 7, 13] or a member of some other class
of graphs [8, 2].

The main application of ME2C comes from wireless mesh networks. Raniwala et
al. [22, 21] proposed a wireless architecture in which each computer uses two
network interface cards (NICs) compared to classical architectures that use
only one NIC. In this model, each computer can communicate with the other
computers in the network using two channels. Raniwala et al. [22, 21] showed
that using such an architecture can increase the throughput by a factor of
$6$. In order to minimize the interference, it is desirable to maximize the
number of distinct channels used in the network. In ME2C computers correspond
to nodes in the graph, while colors correspond to channels.

###  1.1 Previous Work

The problem of finding a maximum edge $2$-coloring of a given graph has been
first studied by Feng et al. [10, 9, 11]. They provided a $2$-approximation
algorithm for ME2C and show that ME2C is solvable in polynomial time for trees
and complete graphs, but they left the complexity for general graphs as an
open problem. The authors also studied a generalization of ME2C, the maximum
edge $q$-coloring, where each vertex is allowed to be incident to at most $q$
edges with distinct colors. For the maximum edge $q$-coloring they showed a
$(1+\frac{4q-2}{3q^{2}-5q+2})$-approximation for $q>2$.

Later, Adamaszek and Popa [1] showed that the problem is -hard and proved that
the algorithm above provides a $5/3$-approximation for graphs which have a
perfect matching. The -hardness is achieved via a reduction from the Maximum
Independent Set problem and states that maximum edge $2$-coloring problem is
UG-hard to approximate within a factor better than $1.5-\epsilon$, for some
$\epsilon>0$. Chandran et al. [6] showed that the matching-based algorithm of
[11] yields a $(1+\frac{2}{\delta})$-approximation for graphs with minimum
degree $\delta$ and a perfect matching. If additionally the graph is triangle-
free, the ratio improves to $(1+\frac{1}{\delta-1})$. Recently, Chandran et
al. [5] improved the analysis of the achieved approximation ratio for
triangle-free graphs with perfect matching to $8/5$. They also showed that the
algorithm cannot achieve a factor better than $58/37$ on triangle free graphs
that have a perfect matching.

Larjomaa and Popa [16] introduced and studied the min-max edge $2$-coloring
problem a variant of the ME2C problem, where the goal is to find an edge
$2$-coloring that minimizes the largest color class. Mincu and Popa [18]
introduced several heuristic algorithms for the min-max edge $2$-coloring
problem.

###  1.2 Our results

Our core algorithm, Algorithm 1, is the $2$-approximation algorithm for
general graphs of Feng et al. [11]. The algorithm simply finds a maximum
matching, colors each edge of the matching with a distinct color, removes the
edges of the matching and finally, colors each connected component of the
remaining graph with a distinct color.

Directly applying the algorithm, however, cannot provide an approximation
ratio better than $2$ in the general case [11] and not better than $5/3\approx
1.667$ for graphs with perfect matchings [1]. To overcome this difficulty, we
introduce a preprocessing phase which considerably simplifies the instance.
The simplifications both improve the quality of the solution provided by the
algorithm and lead to an improved upper bound on the size of an optimal
solution. A graph is called normalized if no more preprocessing steps can be
performed on it.

We first show that Algorithm 1 is a $1.5$-approximation algorithm if _after_
the normalization, the graph contains a perfect matching (Lemma 19). We can
ensure this property if we normalize a subcubic graph111Recall that a graph is
subcubic if no vertex has a degree larger than three., even if before applying
the normalization it did not have a perfect matching.

######  Theorem 1.1 ()

ME2C in subcubic graphs has a polynomial-time $1.5$-approximation algorithm.

It has been shown that claw-free graphs contain a perfect matching [24, 17].
Some preprocessing steps might introduce claws which worsen the quality of the
solution provided by Algorithm 1, therefore we do not immediately obtain a
$1.5$-approximation. However, we develop a bookkeeping technique to counteract
this effect.

######  Theorem 1.2 ()

There is a polynomial-time $1.5$-approximation for claw-free graphs.

In the more general case of graphs with perfect matchings, the effect of
introduced unmatched vertices is more severe. We use a sophisticated
accounting technique to quantify the effects of the appearing unmatched
vertices on the quality of both the optimal solution and the solution given by
Algorithm 1. As a result we obtain a weaker but improved approximation
algorithm for graphs containing a perfect matching:

######  Theorem 1.3 ()

There is a $1.625$-approximation for graphs that contain a perfect matching.

Let us now elaborate on the key ideas behind our results. After the
preprocessing phase we obtain a normalized graph via a series of
modifications. Intuitively, the modifications achieve the following: 1) _Avoid
leaves with equal neighborhoods;_ 2) _Avoid degree-2 vertices;_ 3) _Avoid a
specific class of triangular cacti._

A triangular cactus is a connected graph such that two cycles have at most one
vertex in common and each edge is contained in a $3$-cycle. For our purposes,
we additionally require that no vertex of the cactus is incident to more than
one edge not in the cactus.

While the three modifications are relatively simple, proving that they are
approximation-preserving is non-trivial. If none of these modifications can be
applied (anymore), we call the graph normalized. Our key insight is that the
number of colors in an optimal solution of a normalized graph can be bounded
from above, this is stated as Lemma 1 and shown in Section 3.

######  Lemma 1 ()

Let $G$ be a normalized connected graph with $n\geq 3$ vertices and $\ell$
leaves. Then there is no feasible coloring $\chi$ with more than $3n/4-\ell/4$
colors.

We note that without normalization, an optimal solution can have $n$ colors
(e.g., if $G$ is an $n$-cycle). In order to prove Lemma 1, we use the notion
of _character graphs_ introduced by Feng et al. [11]. A character graph of an
edge 2-coloring is a graph that contains exactly one edge from each color
class. We first show that for a normalized graph we can ensure the existence
of a _nice_ character graph, which is a character graph with several useful
properties. These properties allow for a counting argument with respect to the
number of components in the character graph, which allows us to prove the
bound in Lemma 1.

For general graphs, the best result is still the known $2$-approximation.
There is a family of bipartite triangle free $2$-connected graphs with minimum
degree $3$ which certifies this lower bound for our algorithm.

The rest of the paper is organized as follows. In Section 2 we describe the
three modifications performed on the input graph before applying the
algorithm. Then, in Section 3, we prove the upper bound on the optimal
solution on normalized instances. In Section 4 we combine the results from
Sections 2 and 3 to prove Theorems 1.1 and 1.2, and finally, in Section 5 we
prove Theorem 1.3.

##  2 The Algorithm

Let $G$ be a graph and $\chi$ a feasible $2$-coloring of the edges. Recall
that $\chi(e)$ marks the color of the edge $e$ in $\chi$. With a slight abuse
of notation, let us denote the set of all colors of the edges of $G$ by
$\chi(G)$ and the colors incident to a vertex $v$ by
$\chi(v):=\\{c\in\mathbb{N}\mid\exists u\in V(G):\chi(uv)=c\\}$. If a vertex
$v$ is incident to an edge colored $c$, we say that vertex $v$ _sees_ $c$. We
also denote the number of colors in a coloring $\chi$ by $|\chi|$.

For a color $c$, $E(c)$ denotes the set of edges with color $c$, that is,
$E(c):=\\{e\in E(G)\mid\chi(e)=c\\}$. We refer to $E(c)$ as the _color class_
of $c$. Furthermore, we define by $V(c):=\\{v\in V(G)\mid c\in\chi(v)\\}$ the
_color class of $c$_, i.e. the vertices that see the color $c$. Finally,
$G(c):=(V(c),E(c))$ is the subgraph of $G$ whose edges have color $c$. We call
a cycle on 3 vertices a _3-cycle_ or _triangle_. The term _pendant vertex_ or
_leaf_ is used for degree-$1$ vertices, while the term _pendant edge_ marks
the edge incident to a pendant vertex.

Algorithm 1 The basic algorithm.

1:Input: A simple undirected graph $G=(V,E)$.

2:Output: An edge 2-coloring $\chi$ on the edges of $G$.

3:Calculate a maximum cardinality matching $M$ in $G$.

4:Assign a distinct color in $\chi$ for every edge of $M$.

5:Assign a distinct color in $\chi$ for every nontrivial connected component
of $E\setminus E(M)$.

While Algorithm 1 is well studied (cf. [11, 1, 5]), we apply some
preprocessing steps to each problem instance $G$, before applying Algorithm 1
to the resulting graph $G^{\prime}$. This preprocessing gives the graph
$G^{\prime}$ more structure, which will help us to prove better approximation
guarantees.

These preprocessing steps consist of different _modifications_ , which will be
defined throughout the paper. We note that modifications can increase the size
of the maximum matching $M$, and therefore are not only for the analysis, but
they change the instance in order to obtain stronger results.

Intuitively, a valid modification is a modification such that the number of
colors in an optimal solution does not change and we can transform a solution
for the modified instance to a solution for the original instance. Formally,
we define the following equivalence relation. For a graph $G$ let
$\mathsf{opt}(G)$ denote the number of colors in an optimal edge $2$-coloring
of $G$.

###### Definition 1

Two graphs $G=(V,E)$ and $G^{\prime}=(V^{\prime},E^{\prime})$ form an
_equivalent pair_ with respect to edge 2-coloring, denoted by $\langle
G,G^{\prime}\rangle$, if

  1. 1.

an optimal edge 2-coloring of $G^{\prime}$ uses the same number of colors as
an optimal edge 2-coloring of $G$, i.e.,
$\mathsf{opt}(G)=\mathsf{opt}(G^{\prime})$.

  2. 2.

For every edge 2-coloring $\chi^{\prime}$ of $G^{\prime}$ one can in
polynomial time compute an edge 2-coloring $\chi$ for $G$ that uses the same
number of colors as $\chi^{\prime}$, i.e., $|\chi|=|\chi^{\prime}|$.

To show $\langle G,G^{\prime}\rangle$, it is sufficient to show
$\mathsf{opt}(G)\leq\mathsf{opt}(G^{\prime})$ for Condition 1 and
$|\chi|\geq|\chi^{\prime}|$ for Condition 2: For Condition 1, we use that
there is a coloring $\chi^{\prime}$ for $G^{\prime}$ and a coloring $\chi$ for
$G$ such that
$\mathsf{opt}(G)\leq\mathsf{opt}(G^{\prime})=|\chi^{\prime}|\leq|\chi|\leq\mathsf{opt}(G)$
and thus all inequalities have to be satisfied with equality. For Condition 2,
we note that it is always possible to reduce the number of colors.

###### Definition 2

A _valid modification_ is a sequence of vertex/edge alterations (additions or
deletions), that result in a graph $G^{\prime}$ such that $\langle
G,G^{\prime}\rangle$ is an equivalent pair.

All modifications that will be introduced in the following are indeed _valid_
modifications.

###### Lemma 2

Let $G$ be a graph and let $G^{\prime}$ be the graph obtained from $G$ via a
valid modification from Definition 2. Given a polynomial time
$\alpha$-approximation algorithm for $G^{\prime}$ we can obtain a polynomial
time $\alpha$-approximation algorithm for $G$.

###### Proof

An $\alpha$-approximation algorithm for $G^{\prime}$ produces a coloring
$\chi^{\prime}$ with at least $\mathsf{opt}(G^{\prime})/\alpha$ colors.
Following Definitions 1 and 2 we know that
$\mathsf{opt}(G)\leq\mathsf{opt}(G^{\prime})$ and that we can find in
polynomial time a coloring $\chi$ for the graph $G$ that uses at least as many
colors as $\chi^{\prime}$. Thus, we can find in polynomial time a coloring
$\chi$ for $G$ that has at least $\mathsf{opt}(G)/\alpha$ colors, that is, we
obtain an $\alpha$-approximation algorithm. ∎

#### Modification 1: Avoid pendant vertices with equal neighborhoods.

Figure 1: Modifications 1 and 2, and a simple cactus (Modification 3) as a
subgraph of $G$.

The first modification is to remove a leaf $w$ from $G$, if there is another
leaf $v$, such that both are incident to the same vertex $u$ (see Figure 1).
Formally, we require that the following two conditions are simultaneously
satisfied: (i) the degree of $v$ in $G$ is one; and (ii) there is a vertex
$w\neq v$ of degree one and a vertex $u$ of degree at least three adjacent to
both $v$ and $w$.

We note that we require the degree constraint on $u$ to obtain a cleaner
proof. If the degree equals $2$, we will see that the following Modification 2
applies.

#### Modification 2: Avoid degree-2 vertices.

Given a vertex $v$ of degree $2$, we break it into two vertices $v_{1}$ and
$v_{2}$ with degree $1$ each. More precisely, let $u_{1}$ and $u_{2}$ be the
two vertices adjacent to $v$. We replace the edges $u_{1}v$ and $u_{2}v$ by
the edges $u_{1}v_{1}$ and $u_{2}v_{2}$, replacing $v$ by two new vertices
$v_{1}$ and $v_{2}$.

#### Modification 3: Remove Triangular Cacti.

Recall that a triangular cactus is a connected graph such that two cycles have
at most one vertex in common and each edge is contained in a $3$-cycle.222Note
that our definition of a cactus is stricter than usual: we do not allow cut-
edges. In other words it is a ‘tree’ of triangles where triangle pairs are
joined by a single common vertex. Let $C$ be a subgraph of $G$. For the
modification we require that $C$ is a triangular cactus such that for each
vertex $v\in V(C)$, the degree of $v$ in $G$ is $3$ or $4$, and $v$ is
incident to at most one edge from $E(G)\setminus E(C)$. In the following, we
call such a cactus a _simple cactus_ , and we call an edge $e\in E(G)\setminus
E(C)$ a needle of the cactus $C$. Note that we do not require $C$ to be an
induced subgraph of $G$. Indeed, two triangles can share a needle, as
illustrated in Figure 1.

Modification 3 replaces each $3$-cycle by a single edge as follows:
Let $T_{1},T_{2},\dotsc,T_{\ell}$ be the triangles that comprise the simple
cactus $C$. For each $T_{i}$ with vertices $\\{u_{i},v_{i},w_{i}\\}$, it
removes the edges $u_{i}v_{i},v_{i}w_{i},w_{i}u_{i}$ and introduces two new
vertices $x_{i}$ and $y_{i}$ with an edge $x_{i}y_{i}$. Finally it discards
all isolated vertices (for an illustration, see the the full version of the
article).

We now show that the graph obtained this way is equivalent to the original
graph.

######  Lemma 3 ()

Modifications 1, 2 and 3 are valid.

###### Proof

_Modification 1._ We observe that adding a leaf to a vertex $u$ cannot
decrease the number of colors: we can simply color the new pendant edge with
an arbitrary color seen by $u$. We therefore only have to show that removing a
leaf does not decrease the number of colors. Let $G$ be a graph with an
optimal coloring $\chi^{\star}$. Suppose there exist vertices $v\neq w$ of
degree one that are connected to the vertex $u$ of degree at least three. Let
$x\notin\\{u,v,w\\}$ be a third vertex adjacent to $u$. By the definition of
an edge 2-coloring, $u$ sees at most two colors.

We distinguish between two cases.

  * •

Case 1: $\chi^{\star}(uv)\neq\chi^{\star}(uw)$. Then
$\chi(ux)\in\\{\chi(uv),\chi(uw)\\}$. Without loss of generality, we assume
$\chi(ux)=\chi(uv)$. Then removing $uv$ from $G$ results in a graph
$G^{\prime}$ with coloring $\chi^{\prime}$ such that
$|\chi^{\star}|=|\chi^{\prime}|$.

  * •

Case 2: $\chi^{\star}(uv)=\chi^{\star}(uw)$. Then again, removing $uv$ from
$G$ does not change the number of colors and we obtain a feasible coloring
$\chi^{\prime}$ for $G^{\prime}$ with $|\chi^{\star}|=|\chi^{\prime}|$.

#### Modification 2.

Let $G=(V,E)$ be a graph with a degree-$2$ vertex $v$ and let $G^{\prime}$ be
the graph obtained from $G$ by applying Modification 2 to $v$. Thus if $v$ is
adjacent to $u_{1},u_{2}\in V$, then $G^{\prime}$ contains the leaves $v_{1}$
and $v_{2}$ in place of $v$ as well as the new edges $v_{1}u_{1}$ and
$v_{2}u_{2}$.

Let $\chi^{\star}$ be an optimal coloring of $G$. Coloring $u_{1}v_{1}$ with
$\chi^{\star}(u_{1}v)$ and $u_{2}v_{2}$ with $\chi^{\star}(u_{2}v)$ yields a
feasible coloring $\chi^{\prime}$ for $G^{\prime}$ with the same number of
colors, hence $\mathsf{opt}(G)\leq\mathsf{opt}(G^{\prime})$. In the other
direction, let $\hat{\chi}$ be an arbitrary coloring of $G^{\prime}$. After
contracting $v_{1},v_{2}$ to a single vertex $v$, $\hat{\chi}$ is still a
feasible coloring of $G^{\prime}$ as $v$ only sees the colors of
$\hat{\chi}(vu_{1})$ and $\hat{\chi}(vu_{2})$. Thus $|\chi^{\prime}|=|\chi|$
and therefore Modification 2 is valid.

#### Modification 3.

Figure 2: Subfigures a) and b): Modification 3 for a simple triangular cactus
consisting of just one triangle. Subfigures a) and c) show a variant of
Modification 3 that keeps the perfect matching (used in Section 5).

Let $m$ be the number of adjacent triangles that comprise the cactus $C$ and
let $T_{1},T_{2},\dots,T_{m}$ be these triangles. Let $N$ be the set of
needles.

After the modification, there are $m$ isolated edges and the needles can be
colored independently of $C$. In particular, all needles can still be colored
with the same colors as before. To show that we obtain an equivalent pair, we
have to show that the modification does not decrease the optimal number of
colors and that a coloring in the modified graph gives a coloring in the
original graph without losing colors. The latter condition is simple: We color
the $m$ triangles monochromatically with the $m$ colors of the separate edges.
Since each vertex of $C$ either sees exactly two triangles or one triangle and
one needle, the obtained coloring is feasible independent of the coloring of
the needles. To show the first condition, we define a novel color to be a
color _not_ appearing in $E(G)\setminus E(C)$. Note that in particular, a
needle cannot have a novel color. We then show that $C$ cannot have more than
$m$ novel colors. Since after the modification we obtain exactly $m$ novel
colors for the $m$ separate edges, we obtain an equivalent pair and therefore
the validity of the modification follows.

We show by contradiction that $C$ cannot have more than $m$ novel colors.
Otherwise let $m$ be the smallest number of triangles such that there is a
problem instance with a cactus $C$ of $m$ triangles and at least $m+1$ novel
colors, and let $\chi$ be a feasible coloring in which $C$ has more than $m$
novel colors. Let $G^{\prime}$ be the subgraph of $G$ induced by the edges
$E(C)\cup N$.

Then in particular, $\chi$ restricted to $G^{\prime}$ is a feasible coloring.
We start by simplifying the instance. Let $c$ be a color that is not novel. We
observe that within $G^{\prime}$ we maintain a feasible coloring with the same
number of novel colors if for each $e\in E(G^{\prime})$ with $\chi(e)$ not
novel we assign $\chi(e)=c$. Note that in particular, now all needles are
colored $c$.

We define a _pseudo needle_ to be a triangle with at most one novel color
where exactly two of the three vertices are incident to a needle and both
edges incident to the non-needle have the same color. To find a pseudo needle,
we analyze the degrees within $C$. Note that the sum of degrees in $C$ is $6m$
since each triangle has $3$ edges and thus contributes $6$ to the total
degree. The cycles of $C$ form a tree in the following sense. We associate
each triangle with a vertex and each vertex contained in two triangles with an
edge. Recall that there are no vertices contained in more than two triangles.
Therefore the number of vertices contained in two triangles is exactly $m-1$.
The degree of each of these vertices is $4$. Each other vertex is incident to
a needle. If a vertex is incident to a needle, it is incident to two edges
within $C$. Thus there are $(6m-4(m-1))/2>m$ vertices in $C$ incident to a
needle. By the pigeonhole principle, there is a triangle $T_{i}$ incident to
at least $2$ needles.

Note that in $T_{i}$ there cannot be two distinct novel colors incident to a
needle as the common vertex would see at least three colors. In particular
this implies that if $T_{i}$ is incident to three needles (and thus the only
triangle in $C$), there is at most one novel color in $C$, a contradiction to
having at least $m+1$ colors. Otherwise let $\\{u,v,w\\}$ be the vertices of
$T_{i}$, with $u$ and $v$ incident to a needle and $w$ not incident to a
needle. If $T_{i}$ is a pseudo needle, we remove $T_{i}$ and its two needles
from $G^{\prime}$ and introduce a new vertex $w^{\prime}$ and a needle
$ww^{\prime}$ with $\chi(ww^{\prime})=c$. Then the resulting cactus has $m-1$
triangles and at least novel $m$ colors, not counting the possible novel color
of $T_{m}$ – a contradiction to $m$ being minimal. We show that we can always
turn $T_{i}$ into a pseudo needle, which then implies that $C$ and $\chi$
cannot exist.

If $T_{i}$ does not have a novel color, it is a pseudo needle. If $T_{i}$ has
one novel color $c^{\prime}$, we distinguish two cases. If $w$ sees color $c$,
we set $\chi(uv)=c^{\prime}$ and $\chi(uw)=\chi(vw)=c$, obtaining a feasible
coloring with the same number of colors and a pseudo needle. Otherwise
$\chi(uw)=\chi(vw)=c^{\prime}$, and thus again $T_{i}$ is a pseudo needle.

If $T_{i}$ has two novel colors $c^{\prime},c^{\prime\prime}$, both must be
incident to $w$ as otherwise $u$ or $v$ would see three colors. Let
$w^{\prime},w^{\prime\prime}\notin\\{u,v\\}$ be the other two vertices
adjacent to $w$. Then
$\chi(ww^{\prime}),\chi(ww^{\prime\prime})\in\\{c^{\prime}c^{\prime\prime}\\}$;
w.l.o.g. $\chi(ww^{\prime})=c^{\prime\prime}$. We change $\chi$ by setting
$\chi(uw)=\chi(vw)=\chi(uv)=c^{\prime}$. We thus obtain a feasible coloring
with the same number of colors but only one novel color in $T_{i}$, i.e.,
$T_{i}$ is a pseudo needle. ∎

#### Normalized Graph.

Some of our claims rely on the problem instance $G$ being a graph, such that
none of Modifications 1–3 can be applied on $G$ anymore. We define such a
graph $G$ to be normalized. Below we show that one can efficiently compute a
normalized graph $G^{\prime}$ for every problem instance $G$, and that we can
use the notion of normalized graphs to design approximation algorithms for the
maximum edge $2$-coloring problem.

###### Lemma 4

Given a graph $G$, in polynomial time we can compute a normalized graph
$G^{\prime}$ such that $\langle G,G^{\prime}\rangle$ is an equivalent pair.

###### Proof

Lemmas 3, 3 and 3 describe how Modifications 1–3 are performed, and it is
shown that they can be applied in polynomial time when given a leaf, a
degree-2 vertex, or a simple cactus respectively. Furthermore, it is clear
that if $G$ contains a leaf or a degree-2 vertex, we can find it efficiently.
Simple cacti can also be found in polynomial time as follows.

Let $\mathcal{T}$ be the set of those triangles in $G$ that only contain
vertices of degree $3$ or $4$. Observe that $\mathcal{T}$ contains all
triangles that are part of simple cacti in $G$.

We say two triangles $T_{1},T_{2}\in\mathcal{T}$ are _compatible_ if they
intersect at exactly one vertex $v$. Observe that $v$ then must be a degree-4
vertex. This means that if we fix a triangle $T_{1}\in\mathcal{T}$ and a
vertex $v\in V(T_{1})$ there is at most one compatible triangle
$T_{2}\in\mathcal{T}$ intersecting at $v$. If such a $T_{2}$ exists, any
simple cactus which contains $T_{1}$ must also contain $T_{2}$. If on the
other hand, the degree of $v$ is $4$ and no such $T_{2}$ exists, we may
discard the triangle $T_{1}$, since it cannot be part of any simple cactus.
Let $\mathcal{T}^{\prime}$ be the set of remaining triangles.

If we want to determine, whether a given triangle $T\in\mathcal{T}^{\prime}$
belongs to a simple cactus, we start with the set $\mathcal{S}=\\{T\\}$, which
represents the partial cactus containing only $T$, and grow this set until
either the triangles of $\mathcal{S}$ form a valid simple cactus, or until the
process fails. Note that each degree-$4$ vertex in a triangle of $\mathcal{S}$
joins that triangle with some compatible triangle from $\mathcal{T}$. While
there is a triangle $T_{i}$ with a degree-$4$ vertex in $\mathcal{S}$, such
that the respective compatible triangle $T_{j}$ is not in $\mathcal{S}$, we
distinguish two cases: If $T_{i}$ is the only triangle in $\mathcal{S}$ that
is compatible with $T_{j}$, we add $T_{j}$ to $\mathcal{S}$ and continue the
process. If there is another triangle
$T_{k}\in\mathcal{S}\setminus\\{T_{i}\\}$ which also is compatible to $T_{j}$,
note that adding $T_{j}$ to $\mathcal{S}$ would create a cycle of length at
least $4$ in the cactus, making it not a simple one. However, since $T_{i}$
and $T_{j}$ are compatible, any simple cactus containing $T_{i}$ must also
contain $T_{j}$. Putting these two observations together, we get that
$\mathcal{S}$ cannot be extended to a simple cactus; thus the process must
fail. Since there are $O(n^{3})$ triangles, the whole process can be done in
polynomial time.

We now complete the proof by showing that we can normalize a graph by applying
a sequence of Modifications 1–3 that ends after polynomially many steps.
Observe that by applying Modifications 1 and 3, we will reduce the number of
edges in $G$, but may create a polynomial amount of degree-$2$ vertices.
However, applying Modification 2 reduces the number of degree-$2$ vertices by
one while keeping the number of edges the same. Hence by applying Modification
2 first whenever it is possible, we reach a point when no further
modifications can be made after polynomially many steps. ∎

Let $C$ be a component of $G$ such that $C$ is an isolated vertex or $C$ has
two vertices connected by an edge. Then we say that $C$ is a _trivial
component_. Otherwise, the component is called _non-trivial_.

###### Lemma 5

Suppose there is an $\alpha$-approximation algorithm A for each non-trivial
component of a normalized graph $G^{\prime}$ such that $\langle
G,G^{\prime}\rangle$ is an equivalent pair. Then there is an
$\alpha$-approximation algorithm for $G$.

###### Proof

The statement follows by a simple application of the local ratio method. For
the non-trivial components, we color the edges of graph $G^{\prime}$ according
to the output of A. Algorithm 1 colors all trivial components optimally. Thus
for each component we obtain an $\alpha$-approximation (or better) and the
overall approximation ratio cannot be worse than $\alpha$. ∎

Due to Lemmas 4 and 5, from now on we can assume that the problem instance is
a normalized connected graph $G$ with more than two vertices. We now have a
closer look at leaves.

###### Lemma 6

Let $G$ be a graph where no two leaves share a neighbor and let $\chi$ be an
edge 2-coloring of $G$. Given $G$ and $\chi$, we can efficiently compute an
edge 2-coloring $\hat{\chi}$ of $G$ that uses at least as many colors as
$\chi$ and assigns each pendant edge of $G$ a unique color. In particular, in
a normalized graph there is an optimal edge-$2$-coloring that assigns a unique
color to each pendant edge.

###### Proof

Let $\chi$ be a coloring that does not assign a unique color to every pendant
edge. We describe a transformation that turns a $\chi$ into a new coloring
$\hat{\chi}$ with $|\hat{\chi}|\geq|\chi|$, which assigns a unique color to
one more pendant edge than $\chi$ does. The statement then follows by
iteratively applying this transformation.

Choose an arbitrary pendant vertex $v$ whose pendant edge does not have a
unique color under $\chi$. Let $u$ be the unique neighbor of $v$ in $G$ and
let $c_{1}=\chi(uv)$. If $u$ only sees color $c_{1}$, we simply introduce a
new unique color for $uv$; observe that the new coloring is feasible.
Otherwise, denote by $c_{2}$ the second color seen by $u$. Since $v$ is the
only leaf adjacent to $u$, neither $c_{1}$ nor $c_{2}$ are the unique color of
a pendant edge.

Let $\bar{\chi}$ be the coloring that arises from $\chi$ by assigning all
edges colored with $c_{2}$ the color $c_{1}$ as their new color. Then
$\bar{\chi}$ is valid and uses exactly one color less than $\chi$.

In $\bar{\chi}$, vertex $u$ only sees one color, which allows us to recolor
the edge $uv$ with color $c_{2}$ in $\hat{\chi}$. The resulting coloring
$\hat{\chi}$ uses one more color than $\bar{\chi}$, hence the same number of
colors as $\chi$. The pendant edge $uv$ has a unique color, and all pendant
edges which had a unique color under $\chi$ still do so under $\hat{\chi}$.
Since in a normalized graph leaves are unique, also the last claim of the
lemma follows. ∎

##  3 An upper bound on the optimal solution

To show Lemma 1, we analyze the character graph of the given instance.

###  3.1 Preparing the character graph

Intuitively, a character graph is an edge-induced subgraph with exactly one
representative edge for each color.

######  Definition 3 (Character Graph)

Given an optimal solution $\chi$ for a graph $G$, a _character graph_ of
$(G,\chi)$ is a subgraph $H$ with vertex set $V(G)$ and coloring
$\chi_{|E(H)}$ such that (i) for each $e,f\in E(H)$ with $e\neq f$,
$\chi(e)\neq\chi(f)$ and (ii) for each edge $e\in E(G)$ there is an edge $f\in
E(H)$ with $\chi(e)=\chi(f)$.

For ease of notation, in the following we write $\chi$ instead of
$\chi_{|E(H)}$. Observe that in a character graph $H$, no vertex can have a
degree larger than $2$ since otherwise there would be a vertex with three
incident colors. Thus $H$ is a collection of isolated vertices, paths and
cycles. We call a vertex in $H$ a _free vertex_ if its degree is zero, an _end
vertex_ if its degree is one and an _inner vertex_ if its degree is two. We
frequently use the following known simple but powerful lemma.

######  Lemma 7 (Feng et al. [11])

Let $\chi$ be a feasible 2-edge coloring of a graph $G$ and let $u\neq v$ be
two vertices in $V(G)$. If $|\chi(u)\cup\chi(v)|\geq 4$, $u$ and $v$ are not
adjacent in $G$. In particular, if $H$ is a character graph of $(G,\chi)$ and
$u\neq v$ are two inner vertices that are not neighbors in $H$ then $uv\notin
E(G)$.

Based on Lemma 7, we can avoid cycles within a character graph.

###### Lemma 8

Let $G$ be a normalized graph, and $\chi$ a coloring of $G$. Then there is a
character graph $H$ of $(G,\chi)$ such that $H$ is cycle-free.

###### Proof

Let $H$ be a character graph of $G$. By definition, each edge of $H$ has a
unique color. We claim that each connected component of a character graph can
be converted to a path. Suppose $H$ has a cycle $C$. Since the graph is
normalized, each vertex in $C$ has degree at least three. According to lemma
7, the cycle $C$ cannot contain a chord in $G$, since a chord would be
incident to two inner vertices of $H$. Thus, we consider a vertex $v\notin C$
which is adjacent to a vertex $u\in C$. Let us denote the two neighbors of
vertex $u$ in $C$, by $w_{1}$ and $w_{2}$. By definition, the edges $w_{1}u$
and $w_{2}u$ have different colors $c_{1}\neq c_{2}$ and therefore
$\chi(vu)\in\\{c_{1},c_{2}\\}$. W.l.o.g, we assume $\chi(vu)=c_{1}$. We
replace $w_{1}u$ by $vu$ in $H$ and we obtain a new character graph
$H^{\prime}$, which does not contain the cycle $C$. We iteratively apply this
change for all cycles, until $H^{\prime}$ becomes cycle-free and thus the
lemma follows. ∎

To further structure the character graph, we introduce a reachability measure.

###### Definition 4

Let $v$ be a vertex of a character graph $H$ of $(G,\chi)$. The _scope_ of $v$
($\operatorname{scope}(v)$) is the set of vertices defined inductively as
follows within $G$:

  1. (i)

$v\in\operatorname{scope}(v)$.

  2. (ii)

If $u\in\operatorname{scope}(v)$ and there is an edge $e=uu^{\prime}\in E(H)$
for an inner vertex $u^{\prime}$, then
$V(\chi(e))\subseteq\operatorname{scope}(v)$ (i.e., we include the color class
of $\chi(e)$).

We may choose a total ordering of the vertices and in (ii), we always choose
the smallest vertex that satisfies the properties. Let $\kappa\geq 0$ be an
integer which is at most the number of color classes added and let $c_{i}$ be
the color of the $i$-th color class added, for $1\leq i\leq\kappa$. The _scope
graph_ of $v$ and $\kappa$ for a given ordering is the graph
$(\operatorname{scope}(v),F)$, where $F:=\bigcup_{i=1}^{\kappa}E(c_{i})$. We
skip the ordering and say that subgraph of $G$ is a scope graph of $v$ and
$\kappa$ if there exists an ordering for which it is a scope graph of $v$ and
$\kappa$.

Note that the (total) scope of a vertex does not depend on the chosen
ordering. The scope of a vertex captures a natural sequence of dependencies
between edge colors. In the following lemma, we show how to avoid free
vertices in the scope of vertices, a property which is important in the proof
of Lemma 1.

###### Lemma 9

Let $v$ be an inner vertex such that $vv^{\prime}\in E(H)$ for an inner vertex
$v^{\prime}$. Each character graph $H$ of $(G,\chi)$ can be transformed into a
character graph $H^{\prime}$ of $(G,\chi)$ such that there is no free vertex
in $\text{scope}(v)$.

###### Proof

Suppose $H$ does not have the described properties. Then there is an inner
vertex $v$ that has a free vertex in its scope. Let $\kappa$ be the number of
color classes added to the scope graph of $v$ until the first free vertex is
reached. We show by induction on $\kappa$ that we can reduce the number of
free vertices. By iteratively applying the argument, the lemma follows since
there are at most $n$ free vertices in $H$.

Note that $\\{v,v^{\prime}\\}\subseteq\operatorname{scope}(v)$ and if
$\operatorname{scope}(v)=\\{v,v^{\prime}\\}$ there is trivially no free vertex
in $\operatorname{scope}(v)$. Thus $\kappa\geq 1$ and let $C$ be the
$\kappa$th color class added to the scope graph of $v$.

Let $c$ be the color of $C$, $w$ the first free vertex reached and let
$e=uu^{\prime}$ be the edge of $H$ of color $c$, according to Definition 4.

Thus $e\in E(H)$ and there is an edge $f=ww^{\prime}$ in the scope graph of
$v,\kappa$ with $\chi(f)=c$. We add $f$ to $H$ and remove $e$ from $H$, which
leads to a new valid character graph. Observe that $w^{\prime}$ can only be an
inner vertex if $w^{\prime}\in\\{u,u^{\prime}\\}$, by Lemma 7. In addition,
$w^{\prime}$ is either an end vertex or another free vertex. We have therefore
simply extended a path in $H$ or created a new path. (In particular, $f$
cannot close a cycle since $w$ is a free vertex.)

By construction, $u^{\prime}$ is an inner vertex. Removing $e$ therefore turns
$u^{\prime}$ into an end vertex.

If $u$ is an inner vertex (before modifying $H$), it also becomes an end
vertex and we have reduced the number of free vertices. Otherwise, $u$ is an
end vertex and becomes a free vertex. However, in that case $u$ is contained
in a color class $C^{\prime}$ created earlier in $\operatorname{scope}(v)$
according to Definition 4.

In both cases we therefore make progress: we either directly reduce the number
of free vertices or we “move” the free vertex closer to $v$. Eventually, if
the considered color class is that determined by $v$, we use that $v$ is an
inner vertex and thus cannot be turned into a free vertex. ∎

We further extend the notion of scope to a set of vertices, which is not
merely the union of scopes.

###### Definition 5

Let $S$ be a set of vertices of a character graph $H$ of $(G,\chi)$. If
$S=\\{v\\}$, we define the scope as $\operatorname{scope}(v)$ and define the
scope graph accordingly. For $|S|>1$, the scope of $S$
($\operatorname{scope}(S)$) is the set of vertices defined inductively as
follows within $G$:

  1. (i)

$\operatorname{scope}(v)\subseteq\operatorname{scope}(S)$ for each $v\in S$.

  2. (ii)

Let $uu^{\prime}\in E(H)$ be the only edge of a path in $H$. Let
$\kappa,\kappa^{\prime}$ be numbers and $U,U^{\prime}\subset S$ sets with
$U\cap U^{\prime}=\emptyset$. If $u$ is in a scope graph of $U$ for $\kappa$
and $u^{\prime}$ is in a scope graph of $U^{\prime}$ for $\kappa^{\prime}$
such that the colors of the two graphs are disjoint, then
$V(\chi(uu^{\prime}))\subseteq\operatorname{scope}(U\cup U^{\prime})$.

  3. (iii)

If $u\in\operatorname{scope}(U)$ for $U\subseteq S$ and there is an edge
$e=uu^{\prime}\in E(H)$ for an inner vertex $u^{\prime}$, then
$V(\chi(e))\subseteq\operatorname{scope}(U)$.

If $T$ is a scope graph for $U$ and $\kappa$ and the color class of $c$ is
added, then $(V(T)\cup V(\chi(c)),E(T)\cup E(\chi(c)))$ is a scope graph for
$U$ and $\kappa+1$. If additionally $T^{\prime}$ is a scope graph of
$U^{\prime}$ and (ii) applies with respect to the two scope graphs,
$((V(T)\cup V(T^{\prime})\cup V(\chi(uu^{\prime})),E(T)\cup E(T^{\prime})\cup
E(\chi(uu^{\prime})))$ is a scope graph for $U\cup U^{\prime}$ and
$\kappa+\kappa^{\prime}+1$.

We now strengthen Lemma 9.

###### Lemma 10

Let $S$ be a set of vertices such that each $v\in S$ is an inner vertex such
that $vv^{\prime}\in E(H)$ for an inner vertex $v^{\prime}$. Each character
graph $H$ of $(G,\chi)$ can be transformed into a character graph $H^{\prime}$
of $(G,\chi)$ such that there is no free vertex in $\text{scope}(S)$.

###### Proof

We only have to handle condition (ii). The remaining proof is analogous to
Lemma 9. Let $c:=\chi(uu^{\prime})$ and suppose that $w$ is a free vertex
incident to an edge $e$ colored $c$. We then add $e$ to $E(H)$ and remove
$uu^{\prime}$. The removal creates two free vertices. However, since $U\cap
U^{\prime}=\emptyset$, we can recursively move the free vertices to previous
color classes. If $|U|=1$ or $|U^{\prime}|=1$, we apply Lemma 9. ∎

We say that a character graph is _nice_ if it is (i) cycle-free and (ii) there
is no free vertex in $\operatorname{scope}(S)$ for an arbitrary set
$S\subseteq V(G)$ such that $vv^{\prime}\in E(H)$ for $v\in S$ and an inner
vertex $v^{\prime}$. The following lemma gives some guarantees for the
existence of such a character subgraph.

###### Lemma 11

Each normalized connected graph $G$ with optimal coloring $\chi$ has a nice
character graph $H$.

###### Proof

The lemma follows directly from Lemma 8 and Lemma 10, noting that in the proof
of Lemma 10 we do not introduce new cycles. Furthermore, given a normalized
graph $G$ and the coloring provided by Lemma 6, we may assume that $H$ is a
nice character graph where all pendant vertices of $G$ are endpoints of paths
in $H$. ∎

###  3.2 The proof of Lemma 1

With the preparation of Section 3.1, in this section we prove our main lemma.
See 1

Let $G$ be a normalized problem instance and $H$ a nice character graph of
$(G,\chi)$. Let $F$ be the set of free vertices, $T$ the set of end vertices
and $I$ the set of inner vertices of $H$. We define $n:=|V(H)|$, $i:=|I|$,
$f:=|F|$ and $t:=|T|$, and clearly $n=i+t+f$. We show that there is a mapping
$\iota$ from the set $I$ of inner vertices to $T\cup F$ with the property that
for each vertex $v$ from $T\cup F$ there is at most one inner vertex mapped to
$v$ if $v\in T$ and at most two inner vertices are mapped to $v$ if $v\in F$.
Intuitively, we can see $\iota$ as an injective mapping, where each vertex in
$F$ is split into two vertices. The reason is that we can see a free vertex as
a path of length zero and we count two end vertices for each path.
Furthermore, we maintain that $\iota$ never maps an inner vertex to a pendant
vertex of $G$. We first show that the mapping implies Lemma 1.

###### Lemma 12

Suppose $\iota$ exists. Then no feasible coloring has more than $3n/4-\ell/4$
colors.

###### Proof

The mapping $\iota$ implies $2f+t-\ell\geq i=n-t-f$ and thus $3f+2t\geq
n+\ell$ since $\ell$ out of $t$ end vertices cannot be used for the
assignment. Each free vertex and each path is a component of the character
graph $H$. Therefore the number of components is $f+t/2$, which is minimized
if $f=0$ and $t=(n+\ell)/2$. Thus there are at least $\frac{n+\ell}{4}$
components in $H$ and the number of colors is at most
$n-n/4-\ell/4=3n/4-\ell/4$, completing the proof. ∎

We now construct the mapping $\iota$. We associate the vertices with distinct
natural numbers $\\{1,2,\dotsc,n\\}$ and define $\iota$ iteratively. An end
vertex is _saturated_ if there is an inner vertex mapped to it and a free
vertex is saturated if there are _two_ inner vertices mapped to it. While
there are unassigned inner vertices, we continue the following process. Let
$v\in I$ be the unassigned vertex with the smallest index. We define the set
$U_{v}:=\\{u\in F\mid uv\in E(G)\setminus E(H)\text{ and }|\iota^{-1}(u)|\leq
1\\}\cup\\{u\in T\mid uv\in E(G)\setminus E(H)\text{ and
}\iota^{-1}(u)=\emptyset\\}$, that is, the set of unsaturated free- and end
vertices adjacent to $v$ via an edge _outside_ of $H$. We remark that $v$ and
$u$ are allowed to be in the same path of $H$, as long as they are not
adjacent in $H$. If $U_{v}\neq\emptyset$, we set $\iota(v):=\min_{u\in
U_{v}}u$. Clearly, if $U_{v}\neq\emptyset$, we find a valid mapping for $v$
and can continue. If $U_{v}=\emptyset$, we add $v$ to a set $Q$ of postponed
vertices and continue with the next vertex.

To finish the construction, we have to map the postponed vertices. Recall that
if $v$ is a vertex in $Q$, then $U_{v}=\emptyset$ holds. We then find a vertex
$u$ to map $v$ to by growing a plain cactus: a plain cactus is a triangular
cactus without needles that is a degree-$4$ bounded subgraph $C$ of the
problem instance $G$ where each vertex of $C$ that is connected to $G\setminus
C$ can have any number of adjacent vertices in $V(G)\setminus V(C)$, as
opposed to one in case of a simple cactus. In particular, we will be growing a
plain cactus which is not a simple cactus. As a simple cactus, a plain cactus
can have vertices adjacent in $G$. We call the edge between these vertices a
_cactus chord_.

To gain some intuition, we first argue how to grow an initial triangle of the
cactus (see also Figure 3). There are no degree-two vertices in $G$, therefore
$v$ has a neighbor $u^{\prime}$ in $G$ that is not a neighbor of $v$ in $H$.
Due to Lemma 7, $u^{\prime}$ is not an inner vertex. We note that $u^{\prime}$
cannot be a free vertex either: if $u^{\prime}$ was a free vertex and we could
not map $v$ to $u^{\prime}$, then $u^{\prime}$ would be saturated and $v$
would be the third inner vertex adjacent to $u^{\prime}$. By Lemma 10,
however, that would mean $u^{\prime}$ seeing 3 colors, as each of the three
inner vertices would be connected to $u^{\prime}$ with different colors,
contradicting the feasibility of $\chi$. Hence $u^{\prime}$ is an end vertex.

Since we cannot map $v$ to $u^{\prime}$, there must be another vertex
$\hat{v}$ already mapped to $u^{\prime}$. Let $P$ denote the path of
$u^{\prime}$ and let $u^{\prime\prime}$ be the vertex adjacent to $u^{\prime}$
in $P$. Observe that $u^{\prime\prime}\notin\\{v,\hat{v}\\}$ because otherwise
the edge $u^{\prime}v$ or $u^{\prime}\hat{v}$ would be contained in $E(H)$,
but both have to be in $E(G)\setminus E(H)$ in order to be considered to map
to $v$ or $\hat{v}$, respectively. Since $v$ and $\hat{v}$ are inner vertices,
the colors of $u^{\prime}v$ and $u^{\prime}\hat{v}$ have to be from $\chi(v)$
and $\chi(\hat{v})$, respectively.

By Lemma 7, $\chi(u^{\prime}v)\neq\chi(u^{\prime}u^{\prime\prime})$ and
$\chi(u^{\prime}\hat{v})\neq\chi(u^{\prime}u^{\prime\prime})$. Therefore
$c:=\chi(u^{\prime}v)=\chi(u^{\prime}\hat{v})$ and, again by Lemma 7, $v$ has
an incident edge $e$ and $\hat{v}$ has an incident edge $\hat{e}$ in $H$ with
$\chi(e)=\chi(\hat{e})=c$, which implies $e=\hat{e}$. Therefore, $v$ and
$\hat{v}$ are neighbors in the same path $P^{\prime}$ of $H$; note that
$P^{\prime}$ is not necessarily distinct from $P$.

Figure 3: End vertices are marked by hollow circles, inner vertices are marked
by filled circles. A half-filled vertex can be either an inner- or an end
vertex.

We observe that if there are only the edges from $H$ and the edges from the
triangle formed by $v,\hat{v},u^{\prime}$ incident to these three vertices, we
have a simple cactus, i.e., a cactus of the form removed by Modification 3.
Therefore there is another vertex adjacent to $v$, $\hat{v}$, or $u^{\prime}$.
We now argue that no matter which vertex has another adjacent vertex, we can
either extend the plain triangular cactus or find the aimed-for vertex $u$.

More precisely, starting from $V(K):=\\{v\\}$ we grow a set of vertices
$V(K)$; this process is shown in detail as Algorithm 2. Formally, we also grow
an edge set $E(K)$ such that $K$ is the aimed-for cactus. For a cactus $K$ let
$N(K):=\\{\tilde{v}\in V(G)\setminus V(K)\mid\text{there is a vertex
}\tilde{u}\in V(K)\text{ with }\tilde{u}\tilde{v}\in E(G)\\}$.

Algorithm 2 Mapping a vertex $v\in Q$.

1:Let $V(K):=\\{v\\}$ and $E(K):=\emptyset$;

2:while $\iota(v)$ is not yet determined do

3: if $N(K)$ contains a not saturated free vertex or end vertex $u$ then

4: $\iota(v):=u$;

5: else

6: Find $w\in V(K)$ and $w^{\prime},w^{\prime\prime}\in V(G)\setminus V(K)$
with $w^{\prime}\neq w^{\prime\prime}$, $ww^{\prime}\in
E(H),ww^{\prime\prime}\in E(G)$;

7: $V(K):=V(K)\cup\\{w^{\prime},w^{\prime\prime}\\}$ and
$E(K):=E(K)\cup\\{ww^{\prime},w^{\prime}w^{\prime\prime},w^{\prime\prime}w\\}$;

8: if $w^{\prime}\in V(K^{\prime})$ for a previously considered cactus
$K^{\prime}$ then

9: $V(K):=V(K)\cup V(K^{\prime})\cup\\{w^{\prime\prime}\\}$ and
$E(K):=E(K)\cup
E(K^{\prime})\cup\\{ww^{\prime},ww^{\prime\prime},w^{\prime}w^{\prime\prime}\\}$;

We will show that the cactus constructed by Algorithm 2 satisfies the
following invariants.

  1. 1.

The graph $K$ is a plain cactus.

  2. 2.

Each inner vertex of $K$ except for $v$ is mapped to an end vertex within
$V(K)$.

  3. 3.

For each end vertex of $K$, there is an inner vertex in $V(K)$ mapped to it.

  4. 4.

All triangles of $K$ are monochromatic.

  5. 5.

For each color $c$ in $K$, there is a color-$c$ edge $e$ in $K$ that is also
in $E(H)$.

  6. 6.

$V(K)\subseteq\text{scope}(Q)$.

  7. 7.

$V(K)$ does not include free vertices.

  8. 8.

Each degree-$2$ vertex of $K$ is incident to an edge from $E(H)\setminus
E(K)$.

We first show the invariants assuming that $V(K)\cup N(K)$ does not contain
vertices from previously constructed cacti. Observe that the initial cactus
with $V(K)=\\{v\\}$ satisfies all invariants. From now on we assume that $K$
is a cactus constructed during the execution of Algorithm 2 and $K$ satisfies
all invariants.

Our proof is based on the following technical lemmas.

###### Lemma 13

Let $u$ be an inner or a saturated vertex. Then $|\chi(u)|=2$. Furthermore, if
$u\notin V(K)$ and it is either an inner vertex or $\iota^{-1}(u)\cap
V(K)=\emptyset$, then $\chi(u)\cap\chi(K)=\emptyset$.

###### Proof

If $u$ is an inner vertex, the claim is true by definition of inner vertices
and Invariant 5 If $u$ is an end vertex, it is incident to an edge $e\in
E(H)$, which is not in $E(K)$ if $u\notin V(K)$. Let
$\\{u^{\prime}\\}:=\iota^{-1}(u)$. Since $e$ is not incident to $u^{\prime}$
and $u^{\prime}$ sees two colors, $|\chi(u)|=2$. By Invariant 5, none of these
colors are contained in $\chi(K)$. If $u$ is a free vertex, there are two
vertices $u^{\prime}\neq u^{\prime\prime}$ with
$\iota^{-1}(u)=\\{u^{\prime},u^{\prime\prime}\\}$. Due to Lemma 10,
$u^{\prime}$ and $u^{\prime\prime}$ are not adjacent in $H$. Then the claim
follows by applying the argument of the end-vertex case twice. ∎

The next lemma shows that growing a cactus is independent of vertices that
connect two triangles.

###### Lemma 14

Let $\tilde{u}$ be a degree-$4$ vertex of the cactus $K$. Then $\tilde{u}$ is
also a degree-$4$ vertex in $G$.

###### Proof

By contradiction, suppose that the degree of $\tilde{u}$ is at least $5$ in
$G$. Then $\tilde{u}$ is incident to two triangles of $K$ and it sees the two
colors of these triangles. Let $u^{\prime}$ be a fifth adjacent vertex.
Case 1: Suppose $u^{\prime}\notin V(K)$. Then $\tilde{u}u^{\prime}\notin E(H)$
since both colors in $\chi(\tilde{u})$ have their edges from $H$ within the
cactus, by Invariant 5. The same invariant and Lemma 7 imply that $u^{\prime}$
is not an inner vertex. Among the two triangles incident to $\tilde{u}$, the
one added later to $V(K)$ was only added if $\tilde{u}$ cannot be mapped to
$u^{\prime}$. Due to Invariants 2 and 3, previous mappings to $u^{\prime}$ do
not originate in $V(K)$.

There are two possible situations that can occur: $u^{\prime}$ is either a
saturated free vertex or a saturated end vertex. In both cases, it sees two
distinct colors by Lemma 13. Note that it does not matter if $u^{\prime}$ was
mapped directly or using Algorithm 2, due to Invariants 4, 5 and 8. In both
cases $|\chi(\tilde{u})\cup\chi(u^{\prime})|=4$ and thus there is no valid
color for $\tilde{u}u^{\prime}$ by Lemma 7.

Case 2: Suppose $u^{\prime}\in V(K)$. Then $u^{\prime}$ cannot be an inner
vertex or a degree-$4$ vertex, by Lemma 7. Since by Invariant 7 $V(K)$ does
not contain free vertices, it has to be an end vertex of degree $2$ in $V(K)$.
However, by Invariants 4, 5 and 8, $u^{\prime}$ then also sees two colors
distinct from $\chi(\tilde{u})$. ∎

Furthermore, cactus chords do not influence the process.

###### Lemma 15

Suppose $K$ has two vertices $u^{\prime},u^{\prime\prime}\in V(K)$ such that
$u^{\prime}u^{\prime\prime}\notin E(K)$ but $u^{\prime}u^{\prime\prime}\in
E(G)$, and $N(K)$ does not have unsaturated vertices. Then in $G$, the degrees
of both $u^{\prime}$ and $u^{\prime\prime}$ are three.

###### Proof

By Lemma 14, the degrees of both vertices in $V(K)$ are two. We first argue
that $u^{\prime}$ sees two colors. If $u^{\prime}$ is an internal vertex this
is true by definition. Otherwise $u^{\prime}$ is an end vertex and therefore
incident to one edge from $H$. By Invariant 8, the edge is not in $E(K)$ and
thus the claim follows from Invariants 4 and 5. Symmetrically, the same claim
holds for $u^{\prime\prime}$. In particular, $u^{\prime}u^{\prime\prime}\in
E(H)$ since otherwise $|\chi(u^{\prime})\cup\chi(u^{\prime\prime})|=4$ and
Lemma 7 applies.

The vertex $u^{\prime}$ does not have further neighbors since otherwise by
Lemma 13, it would see more than two colors. The claim for $u^{\prime\prime}$
follows symmetrically. ∎

With this preparation we show that all vertices and edges within Algorithm 2
exist.

###### Lemma 16

In Algorithm 2, the vertices $w,w^{\prime},w^{\prime\prime}$ exist,
$\iota(w^{\prime})=w^{\prime\prime}$,
$\chi(ww^{\prime})=\chi(ww^{\prime\prime})=\chi(w^{\prime}w^{\prime\prime})$,
and there is no other vertex $\bar{w}\in V\setminus V(K)$ adjacent to $w$.

###### Proof

Since $K$ is a plain cactus and we cannot apply Modification $3$, there have
to be edges not allowed in a simple cactus. These cannot be degree-$4$
vertices, due to Lemma 14. Also, by Lemma 15, edges between vertices from $K$
cannot violate the properties of simple cacti. Thus there has to be a
degree-$2$ vertex $w$ of $K$ which has a set $A$ of at least two adjacent
vertices in $V(G)\setminus V(K)$. By Invariant 8, there is a vertex
$w^{\prime}\in A$ with $ww^{\prime}\in E(H)$. Let $c$ be the color of the
triangle containing $w$ and $c^{\prime}:=\chi(ww^{\prime})$.

We claim that there is no vertex $\hat{w}\in A$ with $\chi(w\hat{w})\neq
c^{\prime}$. Since $w$ only sees two colors, the only possibility would be
$\chi(w\hat{w})=c$. However, since $w$ sees two colors, $\hat{w}$ cannot be an
inner vertex and by Lemma 13 it also cannot be a free vertex or an end vertex.

Next, we show that $\iota(w^{\prime})=w^{\prime\prime}$. Suppose
$\iota(w^{\prime})\neq w^{\prime\prime}$. Then, by Lemma 13, it sees two
colors which are distinct from $c$, and also distinct from $c^{\prime}$ since
$ww^{\prime}\in E(H)$ and $w,w^{\prime}\notin\iota^{-1}(w^{\prime\prime})$.
However, $w^{\prime\prime}$ also sees $c^{\prime}$ and therefore more than two
colors, a contradiction. Thus $\iota(w^{\prime})=w^{\prime\prime}$. In
particular,
$\chi(ww^{\prime})=\chi(ww^{\prime\prime})=\chi(w^{\prime}w^{\prime\prime})$.
∎

With Lemma 16 we know that adding the triangle
$\\{w,w^{\prime},w^{\prime\prime}\\}$ does not violate the conditions of plain
cacti, i.e., adding it still satisfies Invariant 1. Since
$\iota(w^{\prime})=w^{\prime\prime}$, also Invariants 2 and 3 are satisfied.
Invariant 4 follows directly from Lemma 16. Since $ww^{\prime}\in E(H)$ by
definition (within Algorithm 2), Invariant 5 follows. Invariant 6 follows by
noting that $w\in\text{scope}(v)$, the edge $ww^{\prime}$ satisfies the
conditions of the lemma, and thus the color class $c$ is added to the scope.
Invariant 7 is a direct consequence of Invariant 6. Invariant 8 requires
additional arguments.

###### Lemma 17

Invariant 8 is satisfied.

###### Proof

Let $\tilde{u}$ be a degree-$2$ vertex. We distinguish the type of
$\tilde{u}$. Due to Invariant 7, $\tilde{u}$ is not free. If $\tilde{u}$ is an
inner vertex, only one of the two incident edges from $E(H)$ can be in $E(K)$,
due to Invariant 4. Thus due to the other edge, the invariant is satisfied. If
$\tilde{u}$ is an end vertex, it has to have an incident edge
$\tilde{u}u^{\prime}$ not in $E(K)$, due to Modification $2$. If
$u^{\prime}\in V(K)$, Lemma 15 implies the invariant. We therefore may assume
that $u^{\prime}\notin V(K)$.

By Invariant 3, there is a vertex $\bar{u}\in V(K)$ with
$\iota(\bar{u})=\tilde{u}$. In particular, $\bar{u}$ is an inner vertex,
$\bar{u}\tilde{u}\in E(K)$ and $\bar{u}\tilde{u}\notin E(H)$. Let $\hat{u}$ be
the third vertex in the same triangle. By Invariant 4,
$\chi(\hat{u}\tilde{u})=\chi(\hat{u}\bar{u})=\chi(\tilde{u}\bar{u})$. But then
$\hat{u}\bar{u}\in E(H)$ as otherwise $\bar{u}$ would see three colors. Thus
$\hat{u}\tilde{u}\notin E(H)$. However, since $u$ is an end vertex, it is
incident to an edge from $E(H)$, which then can only lead outside of $K$. ∎

Finally, we argue that all invariants are also preserved when merging two
cacti. For a cactus $K^{\prime}$, let $v(K^{\prime})$ be the vertex from $Q$
mapped using cactus $K^{\prime}$.

###### Lemma 18

Let $w^{\prime},w^{\prime\prime}$ be the vertices from Algorithm 2 and let
$V(K^{\prime})$ be the vertex set of a cactus constructed in a previous
application of Algorithm 2. Then $w^{\prime\prime}\notin V(K^{\prime})$.
Furthermore, if $w^{\prime}\in V(K^{\prime})$, $v(K^{\prime})$ is mapped to
$w^{\prime\prime}$.

###### Proof

If neither $w^{\prime}$ nor $w^{\prime\prime}$ are in $V(K^{\prime})$, there
is nothing we have to show. Suppose $w^{\prime}\notin V(K^{\prime})$. Then
also $w^{\prime\prime}\notin V(K^{\prime})$ since by Lemma 16, $w^{\prime}$ is
mapped to $w^{\prime\prime}$ which by Invariant 3 would imply that both
$w^{\prime}$ and $w^{\prime\prime}$ are in $V(K^{\prime})$. We therefore may
assume $w^{\prime}\in V(K^{\prime})$. Now suppose that both $w^{\prime}$ and
$w^{\prime\prime}$ are in $V(K^{\prime})$. Then there is a vertex
$\tilde{w}\in V(K^{\prime})$ such that
$\\{w^{\prime},w^{\prime\prime},\tilde{w}\\}$ form a triangle within
$K^{\prime}$. By Invariant 4, the triangle is monochromatic and by Invariant
5, the edge in $H$ with color $\chi(w^{\prime}w^{\prime\prime})$ is contained
in the triangle. However, this contradicts Lemma 16 according to which the
edge in $H$ colored $\chi(w^{\prime}w^{\prime\prime})$ is contained in the
triangle formed by $\\{w,w^{\prime},w^{\prime\prime}\\}$. Thus
$w^{\prime\prime}\notin V(K^{\prime\prime})$.

Since we could not map $v$ to $w^{\prime\prime}$, by Lemma 16, $w^{\prime}$ is
mapped to $w^{\prime\prime}$. If $w^{\prime}$ is an inner vertex, we have a
contradiction since by Invariant 2, $w^{\prime}$ would be mapped to a vertex
within $V(K^{\prime})$. Thus $w^{\prime}$ is an end vertex, which implies that
via $w^{\prime}$, $v(K^{\prime})$ is mapped to $w^{\prime\prime}$. ∎

Then composing a new cactus from $K,K^{\prime}$, and the triangle formed by
$\\{w,w^{\prime},w^{\prime\prime}\\}$ satisfies all conditions: Since by
induction they are satisfied by $K$ and $K^{\prime}$, we only have to check
the new triangle $\\{w,w^{\prime},w^{\prime\prime}\\}$. We obtain a plain
cactus since the degrees of $w$ and $w^{\prime}$ are four and the degree of
$w^{\prime\prime}$ is two. The inner vertex $v(K^{\prime})$ is mapped to
$w^{\prime\prime}$ which implies Invariant 2 and 3. The triangle
$\\{w,w^{\prime},w^{\prime\prime}\\}$ satisfies Invariant 4 by Lemma 16.

Since $ww^{\prime}\in E(H)$, Invariant 5 is satisfied, both $w$ and
$w^{\prime}$ are in the scope of $Q$ and $K,K^{\prime}$ provide disjoint scope
graphs, the conditions of Definition 5 and therefore Invariant 6 are
satisfied. Invariant 7 follows from Invariant 6 and that $Q$ satisfies the
conditions of Lemma 10. Finally, Invariant 8 follows since $w^{\prime\prime}$
is an end vertex and its incident edge from $H$ is not in the constructed
cactus.

##  4 Subcubic Graphs and Claw-Free Graphs

The upper bound shown in Section 3 directly gives the following result.

###### Lemma 19

There is a polynomial-time $1.5$-approximation for normalized graphs that
contain a perfect matching.

###### Proof

Let $G$ be a normalized graph on $n$ vertices that has a perfect matching $M$.
Recall that we can assume without loss of generality that $G$ is a connected
graph with more than $2$ vertices. By Lemma 1, there is no feasible coloring
of $G$ with more than $3n/4$ colors, and Algorithm 1 obtains at least
$|M|=n/2$ colors. Thus the attained approximation ratio is at most
$\frac{3n/4}{n/2}\leq 3/2$. ∎

In particular, our algorithm solves the tight worst-case instance depicted in
Figure 4 for the algorithm of Adamaszek and Popa [1] optimally.

Figure 4: Worst-case instance containing a perfect matching from [1]. Without
applying modifications, Algorithm 1 may chose a perfect matching such that
removing the matching leaves a connected graph – resulting in a $5/3\approx
1.667$ approximation. An improved approximation ratio of $1.625$ is possible
due to Modification 3. In particular, Modification 3 replaces all simple cacti
by independent edges, which results in a modified graph $G^{\prime}$
consisting only of independent edges, which means that Algorithm 1 actually
computes an optimal solution.

In order to handle subcubic graphs, we need to introduce additional
modifications. The validity of these modifications follows from Lemma 6, which
says that we can always assume that pendant edges are colored with a unique
color.

#### Modification 4: Bridge Removal

The next modification is only applied to subcubic graphs, after none of
Modifications 1–3 can be applied anymore. Note that between two consecutive
applications of Modification 4, we may have to update the graph by applying
Modifications 1–3.

Suppose we have such a normalized, subcubic graph $G$ with a cut of size one
consisting of an edge $uv$, that is, the removal of $uv$ disconnects $G$ (see
Figure 5). Due to the definition of $G$, $u$ and $v$ are either degree-$1$ or
degree-$3$ vertices: their degree cannot be more than $3$, and if it was $2$,
Modification 2 could be applied.

Intuitively, Modification 4 disconnects $G$ by removing all edges adjacent to
$uv$ and, if they exist, connects the former neighbors of $u$ and $v$,
respectively. Formally, let $v,u_{1},u_{2}$ be the neighbors of $u$ and
$u,v_{1},v_{2}$ the remaining neighbors of $v$, if they exist. We remove the
edges $u_{1}u$, $u_{2}u$, $v_{1}v$, and $v_{2}v$. Then we add the edge
$u_{1}u_{2}$ if $u_{1}$ and $u_{2}$ exist and $v_{1}v_{2}$ if $v_{1}$ and
$v_{2}$ exist.

Figure 5: Modification 4: Bridge removal, when $\deg(u)=3$ and $\deg(v)=1$,
and Modification 5, with $c_{1}$, $c_{2}$ and $c_{3}$ marked with red, blue
and black edges, respectively.

###### Lemma 20

Modification 4 is valid.

###### Proof

We consider 3 cases.

Case 1: If $\deg(u)=\deg(v)=1$, Modification 4 has no effect.

Case 2: $\deg(u)=3$ and $\deg(v)=1$; the proof goes analogously if $\deg(u)=1$
and $\deg(v)=3$. Since we have a subcubic graph, $u$ has no neighbors besides
$u_{1}$, $u_{2}$ and $v$. For every given optimal coloring $\chi^{\star}$ of
$G$, we may assume that every pendant edge has a unique color, according to
Lemma 6. Since $uv$ has a unique color $c_{1}$, the edges $u_{1}u$ and
$u_{2}u$ have to be colored with the same color $c_{2}\neq c_{1}$.

After the modification, the now disjoint edge $uv$ can keep the color $c_{1}$.
If we introduced a new edge $u_{1}u_{2}$, it can be colored by $c_{2}$, as
this way all vertices see the same set of colors as before the modification.

Therefore $|\chi^{\prime}|\geq|\chi^{\star}$, hence
$\mathsf{opt}(G)\leq\mathsf{opt}(G^{\prime})$. Applying the steps in reverse,
one can also construct a coloring $\chi$ in $G$, given a coloring
$\chi^{\prime}$ in $G^{\prime}$, so that $|\chi|=|\chi^{\prime}|$: the edges
$u_{1}u$ and $u_{2}u$ can inherit the color of $u_{1}u_{2}$, and then every
vertex will see at most $2$ colors.

It remains to deal with the case where there existed an edge $u_{1}u_{2}$ in
$G$. Performing Modification 4 on $uv$ then results in two copies of the edge
$u_{1}u_{2}$. If both copies are colored $c_{2}$, simply remove one copy. If
one of the copies has a different color $c_{3}$, observe that there must be
other edges colored by either $c_{2}$ or $c_{3}$ (or both) at $u_{1}$ or
$u_{2}$. Remove a copy of $u_{1}u_{2}$ that has such a color. The arguments
about both directions follow.

Case 3: $\deg(u)=\deg(v)=3$. Given an optimal coloring $\chi^{\star}$ we can
assume that the edge $uv$ has a unique color due to the following argument. By
removing the edge $uv$ from $G$ we obtain two graphs $G_{1},G_{2}$; let us
consider the graphs $G_{1}^{+}:=G_{1}\cup\\{uv\\}$ and
$G_{2}^{+}:=G_{2}\cup\\{uv\\}$. Notice that $uv$ is a pendant edge in both
graphs. According to Lemma 6 we may assume that $G_{1}^{+}$ and $G_{2}^{+}$
have optimal colorings $\chi^{\star}_{1}$ and $\chi^{\star}_{2}$,
respectively, such that
$|\chi^{\star}_{i}(G_{i}^{+})|=|\chi^{\star}(G_{i}^{+})|$ holds for $i=1,2$
and $uv$ has a unique color in both: denote this color by $c_{1}$ and $c_{2}$,
respectively. Now, identifying $c_{1}$ and $c_{2}$, taking the colors of
$\chi^{\star}_{1}$ and $\chi^{\star}_{2}$ we can obtain a coloring for $G$, in
which the bridge $uv$ has a unique color and which uses $|\chi^{\star}|$ many
colors.

Let $G_{1}^{\prime}$ and $G_{2}^{\prime}$ (respectively) denote $G_{1}$ and
$G_{2}$ (respectively) after Modification 4; that is, replacing edges $u_{1}u$
and $u_{2}u$ by $u_{1}u_{2}$ and replacing edges $v_{1}v$ and $v_{2}v$ by
$v_{1}v_{2}$, respectively. In the case with two copies of edges $u_{1}u_{2}$
or $v_{1}v_{2}$, we use the same argument as above. Then, the modified graph
$G^{\prime}$ consists of 3 components: $G_{1}^{\prime}$, $G_{2}^{\prime}$ and
the edge $uv$.

As for the colorings of $G$ and $G^{\prime}$, we can use the arguments of Case
2. After the modification, all vertices of $G^{\prime}$ see the same colors as
in $G$ and $|\chi^{\prime}|=|\chi^{\star}|$ holds and hence
$\mathsf{opt}(G)\leq\mathsf{opt}(G^{\prime})$ is true. In the other direction,
a coloring $\chi$ for $G$ can be obtained from a coloring $\chi^{\prime}$ for
$G^{\prime}$, such that $|\chi|=|\chi^{\prime}|$. Therefore, Modification 4 is
valid. ∎

See 1.1

###### Proof

Let $G$ be a subcubic graph. Apply Modifications 1–4, until they do not change
the graph anymore, and denote the resulting graph by $G^{\prime}$. We prove
that all components of $G^{\prime}$ are either trivial or they contain only
degree-$3$ vertices.

Observe that Modifications 1–4 cannot increase the degree of any vertex. Note
that $G^{\prime}$ does not contain vertices of degree 2, due to Modification
2. Now consider vertices of degree 1. Since we remove pendant edges via
Modification 4, the only vertices of degree 1 are the end vertices of
independent edges, which are trivial components. Vertices of degree 0 are also
trivial components.

After applying Modifications 1–4, each component is therefore either a trivial
component or a bridgeless cubic graph. It is well-known that each bridgeless
cubic graph has a perfect matching [20]. Using the equivalence of modified
graphs due to Lemma 2, the claim follows as a consequence of Lemma 19. ∎

In order to prove our result on claw-free graphs, we need to introduce a new
modification that helps us control the number of claws.

#### Modification 5: Avoid neighboring pendant edges

Suppose there are two adjacent vertices in $G$, denoted by $u_{1}$ and
$u_{2}$, such that both of them have exactly one adjacent pendant vertex,
denoted by $v_{1}$ and $v_{2}$, respectively (see Figure 6). Modification 5
contracts the edge $u_{1}u_{2}$ into a new vertex $u_{12}$ with exactly one
pendant edge $u_{12}v_{12}$ incident. Then $u$ ‘inherits’ all other neighbors
of $u_{1}$ and $u_{2}$, without multiplicities. Furthermore, we introduce an
isolated edge $w_{1}w_{2}$.

###### Lemma 21

Modification 5 is valid.

###### Proof

According to Lemma 6, we can assume that we have an optimal coloring
$\chi^{\star}$ which assigns unique colors to pendant edges. Then
$\chi^{\star}(u_{1}v_{1})=c_{1}$ and $\chi^{\star}(u_{2}v_{2})=c_{2}$, such
that $c_{1}\neq c_{2}$ and no other edge is colored $c_{1}$ or $c_{2}$. But
then $\chi^{\star}(u_{1}u_{2})=c_{3}$, where $c_{3}\notin\\{c_{1},c_{2}\\}$.
Every other edge adjacent to $u_{1}$ or $u_{2}$ (besides $u_{1}v_{1}$ and
$u_{2}v_{2}$) is colored $c_{3}$.

After Modification 5, we construct a coloring $\chi^{\prime}$ for the modified
graph $G^{\prime}$ as follows. For every possible $v\neq v_{12}$, each
existing edge $u_{12}v$ gets color $c_{3}$, $u_{12}v_{12}$ gets color $c_{1}$
and the isolated edge $w_{1}w_{2}$ gets color $c_{2}$. Observe that this is a
feasible coloring $\chi^{\prime}$ for $G^{\prime}$ that uses the same number
of colors as $\chi^{\star}$, hence
$\mathsf{opt}(G)\leq\mathsf{opt}(G^{\prime})$.

In the other direction, suppose we have a graph $G^{\prime}$ with a pendant
edge $u_{12}v_{12}$ at $u_{12}$, and an isolated edge $w_{1}w_{2}$. Using
Lemma 6, for a coloring $\chi^{\prime}$ of $G^{\prime}$ we can construct a
coloring $\hat{\chi}^{\prime}$ that assigns $u_{12}v_{12}$ a unique color
$c_{1}$ and $|\chi^{\prime}|\leq|\hat{\chi}^{\prime}|$. Then, for each $v\neq
v_{12}$, if the edge $u_{12}v$ exists it is colored $c_{3}\neq c_{1}$.
Additionally, $\hat{\chi}^{\prime}(w_{1}w_{2})=c_{2}$ for some unique color
$c_{2}$.

Let us now construct a graph $G$ by splitting vertex $u_{12}$ into two
adjacent vertices $u_{1}$ and $u_{2}$, and replacing some vertices $u_{12}v$
with $u_{1}v$ or $u_{2}v$, or both, inheriting the color $c_{2}$ of $u_{12}v$.
Furthermore, replace $u_{12}v_{12}$ by $u_{1}v_{1}$, and replace $w_{1}w_{2}$
by $u_{2}v_{2}$, and inherit the respective colors, $c_{1}$ and $c_{2}$.
Finally, use the color $c_{3}$ for the edge $u_{1}u_{2}$. Observe that
(regardless to possible equivalences between colors $c_{1}$, $c_{2}$ and
$c_{3}$) this leads to a coloring $\chi$ feasible for $G$, with the same
amount of colors than $\hat{\chi}^{\prime}$, so then
$|\chi^{\prime}|\leq|\hat{\chi}^{\prime}|=|\chi|$ holds, finishing the proof.
∎

Figure 6: Modification 5, with $c_{1}$, $c_{2}$ and $c_{3}$ marked with red,
blue and black edges, respectively.

Now we are ready to handle claw-free graphs.

See 1.2

###### Proof

Let $G$ be a claw-free graph. We will show that applying Modifications 1–3
either does not create a claw, or creates a claw in a controlled manner.

Keeping it (almost) claw-free. Modification 1 removes pendant vertices, so it
cannot create a claw. Suppose $v$ is a degree-$2$ vertex in a claw-free graph
$G$, with two adjacent edges $u_{1}v$ and $u_{2}v$. Modification 2 splits $v$
into $v_{1}$ and $v_{2}$, and replaces the two incident edges by $u_{1}v_{1}$
and $u_{2}v_{2}$. Since $G$ did not contain a claw, the only way $G^{\prime}$
can contain a claw is if there was a vertex $x\notin\\{u_{1},u_{2},v\\}$ and
edges $u_{1}u_{2}$ and $u_{1}x$ (or analogously $u_{2}x$), but no edge
$u_{2}x$ (analogously no $u_{1}x$). Since $v$ has a degree of $2$, the
vertices $u_{1},u_{2},v_{1},x$ induce a claw in $G^{\prime}$.

Observe that the pendant edges $u_{1}v_{1}$ and $u_{2}v_{2}$ are neighbors,
therefore we can apply Modification 5, that is, contract $u_{1}u_{2}$ into
$u_{12}$ and replace edges $u_{1}v_{1}$ and $u_{2}v_{2}$ by $u_{12}v_{12}$ and
$w_{1}w_{2}$. Furthermore, we replace all existing edges of form $u_{1}v$ and
$u_{2}v$ by an edge $u_{12}v$, and denote this graph $G^{\prime\prime}$.
Observe that by contracting the edge $u_{1}u_{2}$, Modification 5 has removed
the claw $u_{1},u_{2},v_{1},x$. It is possible, however, that the newly
introduced edge $u_{12}v_{12}$ participates in a claw
$\\{u_{12},v_{12},y_{1},y_{2}\\}$, for some vertices $y_{1}$, $y_{2}$. Note
that this means there was no edge $y_{1}y_{2}$ in $G$, and therefore
$G^{\prime}$, and additionally, $y_{1}$ and $y_{2}$ were adjacent to $u_{1}$
and $u_{2}$ in $G$, respectively. Indeed, if both $y_{1}$ and $y_{2}$ were
adjacent to $u_{1}$ (or $u_{2}$), this would lead to the claw
$\\{u_{1},u_{2},y_{1},y_{2}\\}$ in $G$, contradicting its claw-freeness.
Therefore, Modification 2 creates at most one claw, but when it does it also
creates a pendant edge and an isolated edge in the process, both of which will
be accounted for in the second part of the proof. Note that $u_{12}v_{12}$
does not have a neighboring pendant edge, as that would mean a pendant edge at
$u_{1}$ or $u_{2}$, which would contradict the claw-freeness of $G$; hence no
pendant edges will be removed after creating the claw.

Modification 3 removes a simple cactus $C$ but keeps its needles in $G$.
Therefore the only way it can create a claw is if two needles of $C$, say
$u_{1}v$ and $u_{2}v$ are incident to the same vertex $v$ in $G\setminus C$:
the claw is induced by $v$, $u_{1}$, $u_{2}$ and $u_{3}$ where $u_{3}$ is a
vertex adjacent to $v$.333Note that before the modification the edge
$u_{1}u_{2}$ prevented the claw. But then, after Modification 3 has been
applied, $v$ has two adjacent pendant vertices $u_{1}$ and $u_{2}$, and one of
them, say $u_{2}$, can be removed via Modification 1. This removes the claw as
well; if there were another vertex $x$ such that $u_{1}$, $u_{3}$, $v$, $x$ is
a claw in the modified graph, these vertices would induce a claw in the
original graph as well, a contradiction.

Bounding the approximation factor. As a result, we arrive to a normalized
graph $G^{\prime}$ with possibly more than one component. Consider first the
case when $G^{\prime}$ is claw free; we argue about each component $C$
independently. Since $C$ is normalized, the optimal coloring of $C$ has at
most $3|C|/4$ colors. If $|C|$ is even, it contains a perfect matching, which
is of size $|C|/2$ due to Sumner [24] and Las Vergnas [17] and the claw-
freeness of $G$. If $|C|$ is odd, we show that it contains a matching of size
$(|C|-1)/2$. Remove a non-cutvertex $v$ from $C$ and denote the resulting
connected graph $C^{\prime}$.

Note that the removal of $v$ does not create a claw in $C^{\prime}$, hence it
has a matching of size $|C^{\prime}|/2=(|C|-1)/2$ [24, 17]. As a consequence,
there is a matching of size $(|C|-1)/2$ in $C$. In both cases, there is a
matching of size $(|C|-1)/2$, so Algorithm 1 outputs a solution of size444Note
that the only case when we do not have the one additional color as per Step 3
of Algorithm 1 is when $E(C)\setminus E(M)$ is empty, but then the graph $C$
itself is $|C|/2$ independent edges, which has an approximation ratio of $1$.
at least $(|C|-1)/2+1=|C|/2+1/2$, leading to an approximation factor at most
$\frac{3|C|/4}{|C|/2+1/2}<3/2$ for every component $C$ in $G^{\prime}$, and
hence the claim follows.

Now let us consider the case when claws have been created during the
normalization process. As shown in the first half of the proof, performing
Modification 2 then Modification 5 results in creating a claw, but it also
creates a new pendant edge and a new isolated edge in the process. Let us
isolate the creation of one single claw, we will see that this argument can be
repeated for all claws created. During Modification 2 and Modification 5 we
remove a vertex from $G$ and add an isolated edge to it, which means the
number of vertices is increased by $1$. On the other hand, we introduced $3$
new pendant vertices: $v_{12}$, $w_{1}$ and $w_{2}$. According to Lemma 1, the
number of colors in a feasible coloring is therefore at most
$3(n+1)/4-3/4=3n/4$. Observe that the size of the maximum matching did not
change: it decreased by $1$ due to the contraction, but increased by $1$ due
to the isolated edge; therefore Algorithm 1 still finds a coloring with at
least $n/2$ colors (depending on the parity of $n$). Creating a claw this way
thus always results in a graph, for which Algorithm 1 is a
$3/2$-approximation. Since the pendant edge and the isolated edge do not get
removed by any modification in a later step of the algorithm, we can simply
repeat the same argument for every claw created. Thus, the claim follows. ∎

##  5 $1.625$-approximation for Graphs with Perfect Matching

###### Definition 6

A modification is _perfect matching preserving_ , if for each graph $G$ that
has a perfect matching $M$, the modification generates a graph
$G^{\prime}\equiv G$ such that $G^{\prime}$ also has a perfect matching.

###### Lemma 22

Modification 1 and Modification 3 are perfect matching preserving.

###### Proof

We first show that Modification 1 is perfect matching preserving. Observe that
if there are adjacent pendant edges $uv$ and $uw$ in $G$, only one of the
vertices $v$ and $w$ can be matched, therefore there is no perfect matching in
$G$. Otherwise Modification 1 does not have any effect. Therefore, it is
trivially perfect matching preserving.

In order to ensure that Modification 3 is perfect matching preserving, we have
to apply some variation to the modification. Let us fix a perfect matching $M$
in $G$ and start with a simple cactus $C$ consisting of just one triangle
$T=\\{u,v,w\\}$. Let us denote the needles of $T$ by $e_{u}$, $e_{v}$ and
$e_{w}$. If $e_{u}$, $e_{v}$ and $e_{w}$ are in $M$, then just perform
Modification 3, i.e. replace the triangle $uvw$ by an edge $xy$. In the
resulting graph $G^{\prime}$, vertices $u$, $v$ and $w$ will be still matched
by $e_{u}$, $e_{v}$ and $e_{w}$, respectively, and $M$ can be extended with
the edge $xy$ to cover the newly added vertices $x$ and $y$.

Suppose now that $T$ contains an edge from $M$, w.l.o.g. assume that it is the
edge $uv$. In this case, replace the triangle $\\{u,v,w\\}$ not with an edge
$xy$ but with the edge $uv$, illustrated on Figure 2c) in Section 2. Note that
the edge can be still colored with a new color, as $u$ and $v$ will only have
a single adjacent edge in $G^{\prime}$, $e_{u}$ and $e_{v}$, respectively.
Moreover, there were no new vertices added, and there were no edges that
participate in the matching $M$ removed, so the modified graph $G^{\prime}$
also has a perfect matching. Notice that this variant of Modification 3 is
still valid: in the latter case the edge $uv$ simply takes the role of $xy$,
as it can still hold the color of $T$ in the modified graph $G^{\prime}$.

We follow the same approach for cacti $C$ with more than one triangle. In case
a perfect matching $M$ exists in $G$, each triangle
$T_{i}=\\{u_{i},v_{i},w_{i}\\}$ of $C$ will either (i) contain one edge from
$M$ (w.l.o.g. $u_{i}v_{i}$), and have one vertex matched to outside $T_{i}$;
or (ii) have all three of its vertices matched to outside $T_{i}$. In case
(i), we keep the edge $u_{i}v_{i}$, whereas either $w_{i}$ is incident to a
needle or the neighboring triangle keeps its edge containing $w_{i}$,
therefore all vertices of $T_{i}$ remain matched. In case (ii), we add an edge
$x_{i}y_{i}$ and keep the vertices $u_{i}$, $v_{i}$ and $w_{i}$ matched to
outside of $T_{i}$, either in another triangle (where it is matched due to
case (i)) or outside the cactus $C$ (where it is matched due to it being
matched in $G$). In this case, the new edge $x_{i}y_{i}$ will be added to the
perfect matching, and no vertex will become unmatched.

Using the same arguments as in the proof of Lemma 3, we can assume that each
triangle is monochromatic. Then, similarly to the single triangle case there
is an edge in $G^{\prime}$ for each triangle in $G$ to allow for calculating a
feasible coloring $\chi^{\prime}$ from $\chi$ of equal size, and vice versa. ∎

We remark that coming up with a perfect matching preserving modification that
removes degree-$2$ vertices would yield a $1.5$-approximation for graphs that
contain a perfect matching. Indeed, in that case the arguments in the proof of
Lemma 19 would give us the result, as we could apply Modifications 1–3 to a
graph containing a perfect matching until we obtain a normalized graph with a
perfect matching. As we do not have a perfect matching preserving Modification
2, we use another approach, yielding a slightly worse approximation factor.

Suppose $G$ has a perfect matching, then Modification 2 introduces a new
vertex, making the number of vertices odd, hence the resulting graph does not
have a perfect matching anymore. This affects the approximation ratio of
Algorithm 1: the number of vertices increases by one, the number of leaves by
two, while the size of the maximum matching stays the same. One can show that
although the approximation ratio can get worse, it does not get worse than
$13/8=1.625$. Thus, we obtain Theorem 1.3.

See 1.3

###### Proof

Let $G$ be a graph that contains a perfect matching; let us fix such a
matching $M$ for the rest of the proof. According to Lemma 22, Modification 1
and 3 do not violate the property of having a perfect matching. Therefore if
we only perform these two modifications and arrive at a normalized graph,
Algorithm 1 gives a $1.5$-approximation according to Lemma 19. We will now
analyze how Modification 2 can affect the performance of Algorithm 1 using
arguments similar to those in the case of claws in the proof of Theorem 1.2.

Recall that Modification 2 splits a degree-$2$ vertex $v$ into two new
vertices, $v_{1}$ and $v_{2}$, replacing the edges $u_{1}v$ and $u_{2}v$ by
$u_{1}v_{1}$ and $u_{2}v_{2}$, respectively. This operation (let us call them
individually as events) increases the total number of vertices in $G$ by one
and creates two leaves; however, it might create neighboring pendant edges,
which also get simplified by Modification 1.

Upper bound on the number of colors. Let us analyze the changes in the number
of pendant edges and vertices, in all possible cases.
Case 1: no pendant edge gets removed, therefore their number grows by $2$.
Then the number of vertices is increased by $1$ and the upper bound is
$3/4(n+1)-1/2=3/4n+1/4$, by Lemma 1.
Case 2: one of the pendant edges gets removed, therefore their number grows by
$1$. Then the number of vertices stays $n$, hence the upper bound is
$3/4n-1/4$. Notice that in this case we had a pendant edge $u_{1}w$ (or
$u_{2}w$) in $G$, which was part of $M$ along with $u_{2}v$ (or $u_{1}v$), and
the newly created $u_{1}v_{1}$ (or $u_{2}v_{2}$) got removed by Modification
1.
Case 3: both pendant edges get removed, so their number does not change. Then
the number of vertices decreases by $1$, so the upper bound is $3/4n-3/4$.
Note that this would mean both $u_{1}v_{1}$ and $u_{2}v_{2}$ have neighboring
pendant edges, say $u_{1}w_{1}$ and $u_{2}w_{2}$. But this could only be a
result of Case 1: $G$ originally contained a perfect matching, and either
$u_{1}v$ or $u_{2}v$ was a matching edge. If $u_{i}v$ was the matching edge,
the unmatched pendant edge $u_{i}w_{1}$ must have been created by Case $1$.
Let us couple these two individual events, and later argue that in total the
number of vertices stays the same, but the number of pendant edges is
increased by $2$. Observe that since $u_{i}$ only has one incident matching
edge, $u_{i}v$, this particular Case $1$ event will not be coupled to any
other Case $3$ event.

Following the arguments above, we can see that for each time Case 3 happens
there is an occasion where Case 1 happened. As a result, the upper bound after
these two coupled events becomes $3/4n-1/2$, which means it decreases by $1/4$
per event. Let us do the accounting the following way. We have Case 3, coupled
with Case 1, that decrease the bound by $1/4$ for each time we perform
Modification 2. The same holds for Case 2; let us denote the total number of
such instances of Modification 2 by $d_{2}^{-}$. On the other hand, let us
denote the number of Case 1 events without a following Case 3 event by
$d_{2}^{+}$; we have shown that these events increase the bound by $1/4$.

In total, after performing all possible events of Modification 2, the upper
bound on the number of colors hence becomes $3/4n+1/4d_{2}^{+}-1/4d_{2}^{-}$.

Two lower bounds on the number of colors returned by Algorithm 1. Note that
Modification 2 kept all matching edges, in all three cases, and every pendant
edge removal that follows will also not remove a matching edge: if there are
multiple pendant edges adjacent to a common vertex, at most one will be part
of a matching, and we simply choose to keep that pendant edge. This means that
the size of the maximum matching did not decrease, hence Algorithm 1 will
output a coloring of size at least $n/2+1$. The number of vertices and thus
the bound on the size of the optimal solution, however, may have increased.

Fortunately, there is another way we can bound the size of the maximum
matching from below. Notice that the pendant edges introduced by Modification
2 are independent, i.e. they form a matching. Using the same case distinction
as before, there are $d_{2}^{+}$ events that increase the number of pendant
edges by $2$, and $d_{2}^{-}$ events that increase it by $1$. This means that
in the modified graph $G^{\prime}$ we can always find a matching of size
$2d_{2}^{+}+d_{2}^{-}$, simply by choosing the newly created pendant edges.

Combining the bounds. Assume first that we introduce with Modification 2 at
most $n/2$ pendent edges, that is, $2d_{2}^{+}+d_{2}^{-}\leq n/2$ $(*)$ holds.
Then the approximation ratio of Algorithm 1 is at most

$\frac{\frac{3}{4}n+\frac{1}{4}d_{2}^{+}-\frac{1}{4}d_{2}^{-}}{\frac{n}{2}}\stackrel{{\scriptstyle(*)}}{{\leq}}\frac{\frac{3}{4}n+\frac{1}{16}n-\frac{3}{8}d_{2}^{-}}{\frac{n}{2}}\leq\frac{\frac{13}{16}n}{\frac{n}{2}}=\frac{13}{8}\enspace.$
(1)

Assume now that we introduce with Modification 2 at least $n/2$ pendent edges,
that is, $2d_{2}^{+}+d_{2}^{-}\geq n/2$ $(**)$ holds. Then the approximation
ratio of Algorithm 1 is at most

$\frac{\frac{3}{4}n+\frac{1}{4}d_{2}^{+}-\frac{1}{4}d_{2}^{-}}{2d_{2}^{+}+d_{2}^{-}}\leq\frac{\frac{3}{4}n}{2d_{2}^{+}+d_{2}^{-}}+\frac{\frac{1}{4}d_{2}^{+}-\frac{1}{4}d_{2}^{-}}{2d_{2}^{+}+d_{2}^{-}}\stackrel{{\scriptstyle(**)}}{{\leq}}\frac{\frac{3}{4}n}{\frac{n}{2}}+\frac{\frac{1}{4}d_{2}^{+}}{2d_{2}^{+}}=\frac{3}{2}+\frac{1}{8}=\frac{13}{8}\enspace,$
(2)

finishing the proof. ∎

## References

  * [1] A. Adamaszek and A. Popa.  Approximation and hardness results for the maximum edge q-coloring problem.  J. Discrete Algorithms, 38-41:1–8, 2016.
  * [2] M. Axenovich and T. Jiang.  Anti-Ramsey numbers for small complete bipartite graphs.  Ars Comb., 73, 2004.
  * [3] M. Axenovich, T. Jiang, and A. Kündgen.  Bipartite anti-Ramsey numbers of cycles.  J. Graph Theory, 47(1):9–28, 2004.
  * [4] A. Blokhuis, R. J. Faudree, A. Gyárfás, and M. Ruszinkó.  Anti-Ramsey colorings in several rounds.  J. Comb. Theory. Ser. B, 82(1):1–18, 2001.
  * [5] L. S. Chandran, A. Lahiri, and N. Singh.  Improved approximation for maximum edge colouring problem.  Discret. Appl. Math., 2021.
  * [6] L. Sunil Chandran, Talha Hashim, Dalu Jacob, Rogers Mathew, Deepak Rajendraprasad, and Nitin Singh.  New bounds on the anti-ramsey numbers of star graphs, 2023.
  * [7] H. Chen, X. Li, and J. Tu.  Complete solution for the rainbow numbers of matchings.  Discrete Math., 309(10):3370–3380, 2009.
  * [8] P. Erdős, M. Simonovits, and V.T. Sós.  Anti-Ramsey theorems.  Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, pages 633–643. Colloq. Math. Soc. János Bolyai, Vol. 10, 1975.
  * [9] W. Feng, P. Chen, and B. Zhang.  Approximate maximum edge coloring within factor 2: a further analysis.  In ISORA, pages 182–189, 2008.
  * [10] W. Feng, L. Zhang, W. Qu, and H. Wang.  Approximation algorithms for maximum edge coloring problem.  In TAMC, pages 646–658, 2007.
  * [11] W. Feng, L. Zhang, and H. Wang.  Approximation algorithm for maximum edge coloring.  Theor. Comput. Sci., 410(11):1022–1029, 2009.
  * [12] A. Frieze and B. Reed.  Polychromatic Hamilton cycles.  Discrete Math., 118(1):69–74, 1993.
  * [13] R. Haas and M. Young.  The anti-Ramsey number of perfect matching.  Discrete Math., 312(5):933–937, 2012.
  * [14] T. Jiang.  Edge-colorings with no large polychromatic stars.  Graphs Combin., 18(2):303–308, May 2002.
  * [15] T. Jiang and D. B. West.  Edge-colorings of complete graphs that avoid polychromatic trees.  Discrete Math., 274(1-3):137–145, 2004.
  * [16] T. Larjomaa and A. Popa.  The min-max edge q-coloring problem.  J. Graph Algorithms Appl., 19(1):507–528, 2015.
  * [17] M. Las Vergnas.  A note on matchings in graphs.  Cah. Cent. Étud. Rech. Opér., 17:257–260, 1975.
  * [18] R. S. Mincu and A. Popa.  Heuristic algorithms for the min-max edge 2-coloring problem.  In COCOON, pages 662–674, 2018.
  * [19] J. J. Montellano-Ballesteros and V. Neumann-Lara.  An anti-Ramsey theorem on cycles.  Graphs Combin., 21(3):343–354, Sep 2005.
  * [20] J. Petersen.  Die Theorie der regulären graphs.  Acta Math., 15(1):193–220, 1891.
  * [21] A. Raniwala and T. Chiueh.  Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network.  In INFOCOM 2005, volume 3, pages 2223–2234, march 2005.
  * [22] A. Raniwala, K. Gopalan, and T. Chiueh.  Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks.  Mobile Computing and Communications Review, 8(2):50–65, 2004.
  * [23] I. Schiermeyer.  Rainbow numbers for matchings and complete graphs.  Discrete Math., 286(1-2):157–162, 2004.
  * [24] D. P. Sumner.  Graphs with $1$-factors.  Proc. Amer. Math. Soc., 42:8–12, 1974.