# Odd edge-colorings of subdivisions of odd graphs

Mirko Petruševski , Riste Škrekovski Department of Mathematics and
Informatics, Faculty of Mechanical Engineering - Skopje, Republic of North
Macedonia. E-Mail<EMAIL_ADDRESS>University of Ljubljana &
Faculty of Information Studies, Novo mesto, Slovenia. E-Mail:
<EMAIL_ADDRESS>
###### Abstract

An odd graph is a finite graph all of whose vertices have odd degrees. Given
graph $G$ is decomposable into $k$ odd subgraphs if its edge set can be
partitioned into $k$ subsets each of which induces an odd subgraph of $G$. The
minimum value of $k$ for which such a decomposition of $G$ exists is the odd
chromatic index, $\chi_{o}^{\prime}(G)$, introduced by Pyber (1991). For every
$k\geq\chi_{o}^{\prime}(G)$, the graph $G$ is said to be odd $k$-edge-
colorable. Apart from two particular exceptions, which are respectively odd
$5$\- and odd $6$-edge-colorable, the rest of connected loopless graphs are
odd $4$-edge-colorable, and moreover one of the color classes can be reduced
to size $\leq 2$. In addition, it has been conjectured that an odd $4$-edge-
coloring with a color class of size at most $1$ is always achievable. Atanasov
et al. (2016) characterized the class of subcubic graphs in terms of the value
$\chi_{o}^{\prime}(G)\leq 4$. In this paper, we extend their result to a
characterization of all subdivisions of odd graphs in terms of the value of
the odd chromatic index. This larger class $\mathcal{S}$ is of a particular
interest as it collects all ‘least instances’ of non-odd graphs. As a prelude
to our main result, we show that every connected graph $G\in\mathcal{S}$
requiring the maximum number of four colors, becomes odd $3$-edge-colorable
after removing a certain edge. Thus, we provide support for the mentioned
conjecture by proving it for all subdivisions of odd graphs. The paper
concludes with few problems for possible further work.

Keywords: odd graph, odd edge-coloring, odd chromatic index, subdivision.

##  1 Introduction

###  1.1 Basic terminology

All considered graphs $G=(V(G),E(G))$ are undirected and finite, loops and
parallel edges are allowed. We follow [2] for the terminology and notation not
defined here. The parameters $n(G)=|V(G)|$ and $m(G)=|E(G)|$ are called order
and size of $G$, respectively. A graph of order $1$ is trivial, and a graph of
size $0$ is empty. A path or cycle is said to be odd (resp. even) if its size
is odd (resp. even.) A path (resp. edge) with endpoints $x$ and $y$ is
referred to as an $x$-$y$ path (resp. $x$-$y$ edge). Given a path $P$ and
$x,y\in V(P)$, the $x$-$y$ subpath of $P$ is denoted $xPy$. For every vertex
$v\in V(G)$, $E_{G}(v)$ denotes the set of edges incident with $v$, and the
size of $E_{G}(v)$ (every loop being counted twice) is the degree of $v$ in
$G$, with notation $d_{G}(v)$. The maximum (resp. minimum) vertex degree in
$G$ is denoted by $\Delta(G)$ (resp. $\delta(G)$). A graph $G$ is subcubic if
$\Delta(G)\leq 3$. Each vertex $v$ of even (resp. odd) degree $d_{G}(v)$ is an
even (resp. odd) vertex. In particular, if $d_{G}(v)$ equals $0$ (resp. $1$),
we say that $v$ is an isolated (resp. pendant) vertex of $G$. Any vertex of
degree $d$ is called a $d$-vertex. A graph is even (resp. odd) whenever all
its vertices are even (resp. odd). The set of neighboring vertices of $v\in
V(G)$ is denoted by $N_{G}(v)$. For every $u\in N_{G}(v)$, the edge set
$E_{G}(u)\cap E_{G}(v)$ is the $u$-$v$ bouquet in $G$, with notation
$\mathcal{B}_{uv}$. The maximum size of a bouquet in $G$ is its multiplicity.
A graph $G$ is simple if it is loopless and of multiplicity at most $1$.

To split a vertex $v$ is to replace it by two (not necessarily adjacent)
vertices $v^{\prime}$ and $v^{\prime\prime}$, and to replace each edge
incident to $v$ by an edge incident to either $v^{\prime}$ or
$v^{\prime\prime}$ (but not both, unless the edge is a loop at $v$), the other
end of the edge remaining unchanged. A vertex of positive degree can be split
in several ways, so the resulting graph is not unique in general. Another
local operation on graph $G$ is to suppress a vertex $v$ of degree
$d_{G}(v)=2$. The modified graph $G\%v$ is obtained from $G-v$ by adding an
edge between the neighbors of $v$ (the new edge is a link unless $N_{G}(v)$ is
a singleton). For $X\subseteq V(G)\cup E(G)$, $G-X$ is the subgraph of $G$
obtained by removing $X$; we abbreviate $G-\\{x\\}$ to $G-x$. Similarly, given
a subgraph $H\subseteq G$, $H+X$ is the subgraph of $G$ obtained by adding to
$H$ all the vertices and edges from $X$.

A $v\in V(G)$ is a cut-vertex of $G$ if $G-v$ has more (connected) components
than $G$. If $V_{1},\ldots,V_{k}$ are vertex sets of the components of $G-v$,
then for $i=1,\ldots,k$, the induced subgraph $G[V_{i}\cup\\{v\\}]$ is called
a $v$-lobe of $G$. A block graph is a connected graph without cut-vertices.
Given a graph $G$, any maximal block subgraph is a block of $G$. For a block
$B$, each vertex $v\in V(B)$ which is not a cut-vertex of $G$ is an internal
vertex of $B$ (and of $G$). The collection of internal vertices of $B$ is
denoted by $\mathrm{Int}_{G}(B)$. If $V(B)$ contains at most one cut-vertex of
$G$ then $B$ is an end-block. Every vertex $v$ of a block graph $G$ has a
neighbor among the internal vertices of each end-block of $G-v$. For a
connected graph $G$, an edge $e\in E(G)$ is a bridge of $G$ if $G-e$ is
disconnected. If $vw$ is a bridge and $w$ is not the only neighbor of $v$,
then $v$ is a cut-vertex of $G$. The connectivity $\kappa(G)$ (resp. edge-
connectivity $\kappa^{\prime}(G)$) of a graph $G$ is the minimum size of a
subset $S\subseteq V(G)$ (resp. $S\subseteq E(G)$) such that $G-S$ is
disconnected or of order $1$.

###  1.2 Odd edge-colorings and odd chromatic index

An assignment $\varphi:E(G)\to S$ is an edge-coloring of $G$ with color set
$S$. We say that $\varphi$ is a $k$-edge-coloring if $|S|\leq k$. Nature of
the colors being irrelevant, it is conventional to use
$S=[k]:=\\{1,2,\ldots,k\\}$ if the color set is of size $k$. For each color
$c\in S$, $E_{c}(G,\varphi)$ denotes the color class of $c$, being the set of
edges colored by $c$ (i.e., $E_{c}(G,\varphi)=\varphi^{-1}(c)$); whenever $G$
and $\varphi$ are clear from the context, we denote the color class of $c$
simply by $E_{c}$. Given an edge-coloring $\varphi$ and a vertex $v$ of $G$,
we say the color $c$ appears at $v$ if $E_{c}\cap E_{G}(v)\neq\emptyset$. Any
decomposition $\\{H_{1},\ldots,H_{k}\\}$ of $G$ can alterably be interpreted
as an $k$-edge-coloring of $G$ for which the color classes are
$E(H_{1}),\ldots,E(H_{k})$.

An odd edge-coloring of a given graph $G$ is an edge-coloring such that each
nonempty color class induces an odd subgraph. In other words, at each vertex
$v$, for any appearing color $c$ the degree $d_{G[E_{c}]}(v)$ is odd.
Equivalently, an odd edge-coloring can be seen as a decomposition of $G$ into
(edge-disjoint) odd subgraphs. As usual, we are most interested in the least
number of colors necessary to create such a coloring. An odd edge-coloring of
$G$ using at most $k$ colors is referred to as an odd $k$-edge-coloring, and
then we say that $G$ is odd $k$-edge-colorable. Whenever $G$ is odd edge-
colorable, the odd chromatic index $\chi_{o}^{\prime}(G)$ is defined to be the
minimum integer $k$ for which $G$ is odd $k$-edge-colorable.

It is obvious that a necessary and sufficient condition for odd edge-
colorability of $G$ is the absence of vertices incident only to loops. Apart
from this, the presence of loops does not influence the existence nor changes
the value of the index $\chi_{o}^{\prime}(G)$. Therefore, the class of
loopless graphs comprise a natural framework for the study of the odd
chromatic index.

Figure 1: A simple graph with odd chromatic index equal to $4$.

As a notion, odd edge-coloring was introduced by Pyber in his survey on graph
coverings [8]. The mentioned work considers simple graphs and (among other
results) contains a proof of the following.

######  Theorem 1.1 (Pyber, 1991).

For every simple graph $G$, it holds that $\chi_{o}^{\prime}(G)\leq 4$.

Pyber remarked that the established upper bound is realized by the wheel on
four spokes $W_{4}$ (see Fig. 1). However, this upper bound of four colors
does not apply to the class of all looplees graphs $G$. For instance, Fig. 2
depicts four graphs with the following characteristic property: each of their
odd subgraphs is of order $2$ and size $1$, i.e., a copy of $K_{2}$.
Consequently, for each of these graphs the odd chromatic index equals the
size.

Figure 2: Four Shannon triangles (the smallest one of each type).

As defined in [4], a Shannon triangle is a loopless graph on three pairwise
adjacent vertices. And if $p,q,r$ are parities of the sizes of its bouquets in
non-increasing order, with $2$ (resp. $1$) denoting an even-sized (resp. odd-
sized) bouquet, then $G$ is a Shannon triangle of type $(p,q,r)$. For example,
Figure 2 depicts (from left to right) the smallest in terms of size Shannon
triangle of type $(1,1,1)$, $(2,1,1)$, $(2,2,1)$, and $(2,2,2)$, respectively.
It is straightforward that if $G$ is a Shannon triangle of type $(p,q,r)$,
then

$\chi^{\prime}_{o}(G)=p+q+r\,.$ (1.1)

The main result of [4] is that six colors suffice for an odd edge-coloring of
any connected loopless graph. Furthermore, it characterizes when six colors
are necessary.

######  Theorem 1.2.

For every connected loopless graph $G$, it holds that
$\chi_{o}^{\prime}(G)\leq 6$. Moreover, equality is attained if and only if
$G$ is a Shannon triangle of type $(2,2,2)$.

Recently, the following improvement of Theorems 1.1 and 1.2 has been shown in
[6]:

######  Theorem 1.3.

Let $G$ be a connected loopless graph that is not a Shannon triangle of type
$(2,2,1)$ or $(2,2,2)$. Then $G$ admits an odd edge-coloring with color set
$\\{1,2,3,4\\}$ such that the color class $E_{4}$ satisfies two additional
conditions:

  1. $(i)$

$|E_{4}|\in\\{0,1,2\\}$;

  2. $(ii)$

if $\mathcal{B}_{xy}\cap E_{4}\neq\emptyset$ then another common color
(besides $4$) appears at $x$ and $y$;

and in case of $|E_{4}|=2$, the pair of edges colored by $4$ are at distance
$2$ (i.e., second-neighbors in the line graph).

It is not known whether there exists a connected graph $G$ with
$\chi^{\prime}_{o}(G)=4$ that does not admit an odd $4$-edge-coloring with a
color class of size $1$. In this regard, the following has been conjectured in
[7].

######  Conjecture 1.4.

Every connected graph $G$ with $\chi^{\prime}_{o}(G)=4$ becomes odd $3$-edge-
colorable by removing a particular edge.

Concerning odd $2$-edge-colorability of graphs, Kano et al. [3] have shown the
following.

######  Theorem 1.5.

The decision problem whether a given graph $G$ is odd $2$-edge-colorable is
solvable in polynomial time. Moreover, in the affirmative case, such a
coloring can be found in polynomial time.

In view of Theorem 1.3, the decision problem whether a given graph $G$ is odd
$4$-edge-colorable is also solvable in polynomial (in fact, linear) time.
Moreover, its proof can be used as an efficient algorithm for exhibiting such
a coloring. The analogous complexity questions regarding odd $3$-edge-
colorability of general graphs are still open. Nevertheless, these questions
have been answered (in the affirmative) for subcubic graphs. Namely, a
complete characterization of the class of loopless subcubic graphs in terms of
their odd chromatic index was obtained in [1] through the following:

######  Theorem 1.6.

Let $G$ be a connected loopless subcubic graph. Then

$\chi^{\prime}_{o}(G)=\begin{cases}0&\text{\quad if\, }G\text{ is empty}\,;\\\
1&\text{\quad if \,}G\text{ is odd}\,;\\\ 2&\text{\quad if \,}G\text{ has
2-vertices, with an even number of them on each cycle}\,;\\\ 4&\text{\quad if
\,}G\text{ is obtainable from a cubic bipartite graph by a single edge
subdivision}\,;\\\ 3&\text{\quad otherwise}\,.\end{cases}$

In this paper we focus on subdivisions of odd graphs, which are in some sense
the least non-odd graphs among all. Let us denote this collection by
$\mathcal{S}$, and similarly, let $\mathcal{O}$ be the class of odd graphs,
with the understanding that $\mathcal{O}\subset\mathcal{S}$. Our main result,
see Theorem 4.3 in Section $3$, is a characterization of the members of
$\mathcal{S}$ in terms of the value of their odd chromatic index. Thus, we
achieve a generalization of Theorem 1.6, and at the same time answer a
question raised by the end of [6]. Our findings here also provide support for
Conjecture 1.4 over the class $\mathcal{S}$.

The rest of the article is divided into three sections. In the next one, as a
preliminary, we collect several ‘easy’ results (most of them previously
known). Section $3$ is devoted to a derivation of our main result - a
characterization of $\mathcal{S}$ in terms of the value of the odd chromatic
index. The final section briefly conveys some possible directions for further
related study.

##  2 Preliminaries

If $H\subseteq G$ and the underlying (host) graph $G$ is clear from the
context, then the edge-complement of the subgraph $H$, denoted $\hat{H}$, is
the spanning subgraph $\hat{H}=G-E(H)$. A co-forest in $G$ is a subgraph whose
edge-complement is a forest. For a graph $G$, let $T$ be an even-sized subset
of $V(G)$. Following [2], a spanning subgraph $H$ of $G$ is said to be a
$T$-join of $G$ if $d_{H}(v)$ is odd for all $v\in T$ and even for all $v\in
V(G)\setminus T$. For instance, if $P\subseteq G$ is a path with endpoints $x$
and $y$, the spanning subgraph of $G$ with edge set $E(P)$ is an
$\\{x,y\\}$-join of $G$. As another example, every even spanning subgraph is
an $\emptyset$-join of $G$. Observe that the symmetric difference of an
$S$-join and a $T$-join is an $S\oplus T$-join. (We shall use $\oplus$ to
denote both the symmetric difference operation on spanning subgraphs and on
sets.) Hence, the symmetric difference $H\oplus K$ of a $T$-join $H$ and a
spanning even subgraph $K$ of $G$, is a $T$-join. In particular, removal
(resp. addition) of the edges of an edge-disjoint cycle from (resp. to) a
$T$-join, produces another $T$-join. Therefore, if a $T$-join of $G$ exists,
there also exists such a forest (resp. co-forest). By the handshake lemma,
necessary for the existence of a $T$-join is that the intersection of $T$ with
the vertex set of every component of $G$ is even-sized, and a straightforward
implementation of the above mentioned facts (see [9]) is that this condition
also suffices. Consequently, given a connected graph $G$ and an even-sized
subset $T$ of $V(G)$,

  1. $(1)$

there exists a $T$-join of $G$ that is a forest;

  2. $(2)$

there exists a $T$-join of $G$ that is a co-forest;

  3. $(3)$

additionally, if $G$ is of even order, then it contains a spanning odd co-
forest.

An edge-coloring $\varphi$ is said to be odd (resp. even) at vertex $v$ if
each color appearing at $v$ is odd (resp. even). Similarly, we say that
$\varphi$ is odd (resp. even) away from $v$ if $\varphi$ is odd (resp. even)
at every vertex $w\in V(G)\backslash\\{v\\}$, with no assumptions about the
behavior of $\varphi$ at $v$ being made. The following useful result appears
in [5, 6].

######  Proposition 2.1.

Let $v$ be a vertex in a forest $F$. Any local coloring of $E_{F}(v)$ which
uses at most two colors extends to a $2$-edge-coloring of $F$ that is odd away
from $v$. In particular, $F$ is odd $2$-edge-colorable.

An immediate consequence of Proposition 2.1 is the result below, which
concerns a graph all of whose cycles (if any) share a vertex.

######  Proposition 2.2.

If $v$ is a vertex of a graph $G$ such that $G-v$ is a forest, then $G$ admits
a $2$-edge-coloring that is odd away from $v$. Additionally, if $d_{G}(v)$ is
odd, then $G$ admits an edge-coloring with color set $\\{1,2\\}$ that is odd
away from $v$ and the color $1$ (resp. $2$) is odd (resp. even) at $v$.

###### Proof.

We may assume that $G$ is loopless. It suffices to prove the first part. Split
$v$ into $k=d_{G}(v)$ pendant vertices $v_{1},\ldots,v_{k}$ in order to obtain
a forest $F$. By Proposition 2.1, $F$ admits an odd $2$-edge-coloring. Re-
identify $v_{1},\ldots,v_{k}$ into $v$ while keeping the colors on all edges.
We thus regain $G$ and a required edge-coloring. ∎

As observed in [8], the odd $2$-edge-colorability of forests implies odd
$3$-edge-colorability of connected graphs of even order, which in turn yields
odd $3$-edge-colorability of graphs with edge-connectivity $1$.

######  Proposition 2.3.

If $G$ is a connected graph such that $n(G)$ is even or $\kappa^{\prime}(G)=1$
then $\chi_{o}^{\prime}(G)\leq 3$.

The next result can be used to characterize odd $2$-edge-colorability of
unicyclic graphs.

######  Proposition 2.4.

Let $G$ be a unicyclic graph, and let $C\subseteq G$ be the (unique) cycle.
Then $\chi^{\prime}_{o}(G)\leq 3$. Moreover, the upper bound is attained if
and only if the following two conditions hold simultaneously:

  * $(i)$

$\\{v\in V(C):d_{G}(v)=2\\}$ is odd-sized;

  * $(ii)$

$\\{v\in V(C):0\equiv_{2}d_{G}(v)\neq 2\\}$ is empty.

###### Proof.

If $G=C$ then condition $(ii)$ is clearly met, and the statement is trivially
true (as by then the notions ‘odd edge-coloring’ and ‘proper edge-coloring’
become equivalent). Assuming $G\neq C$, let $S=\\{v\in V(C):d_{G}(v)\neq 2\\}$
and $\hat{S}=V(C)\backslash S$. Denote by $S^{\prime}$ and $S^{\prime\prime}$,
respectively, the subsets of $S$ comprised of those vertices $v$ for which the
degree $d_{G}(v)$ is odd or even. Observe that for every $v\in S^{\prime}$, a
coloring of $E_{C}(v)$ extends to an odd $2$-edge-coloring of $E_{G}(v)$ if
and only if it is monochromatic. Contrarily, for every $v\in S^{\prime\prime}$
each coloring of $E_{C}(v)$ extends to an odd $2$-edge-coloring of $E_{G}(v)$.
Consequently, in view of Proposition 2.1, a given $k$-edge-coloring of $E(C)$
extends to an odd $k$-edge-coloring of $G$ if and only if it is dichromatic at
each $v\in\hat{S}$ and monochromatic at each $v\in S^{\prime}$. In particular,
it is readily implied that $\chi^{\prime}_{o}(G)\leq 3$.

Additionally, if condition $(ii)$ fails to hold, then a color can be saved;
indeed, simply select a vertex $v\in S^{\prime\prime}$, take a $2$-edge-
coloring of $C$ which is monochromatic at each vertex from $S^{\prime}$ and
dichromatic at each vertex from $V(C)\backslash(S^{\prime}\cup\\{v\\})$; by
the above observation, such a coloring of $E(C)$ extends to an odd $2$-edge-
coloring of $G$. On the other hand, assuming $(ii)$, odd $2$-edge-colorability
of $G$ is equivalent to the existence of a $2$-edge-coloring of $C$ that is
dichromatic precisely at each vertex of $\hat{S}$. The latter is clearly
equivalent to $(i)$. ∎

######  Corollary 2.5.

Let $G$ be a connected unicyclic graph, $C\subseteq G$ be the (unique) cycle
and $\\{v\in V(C):d_{G}(v)\text{ is odd}\\}=\emptyset$. Then
$\chi^{\prime}_{o}(G)\leq 2$ unless $G=C$ is an odd cycle.

We end the preliminaries with two more already known results (proofs can be
found in [6]).

######  Proposition 2.6.

In a connected loopless graph $G$, let $v$ be an internal vertex, $e\in
E_{G}(v)$, and $T\subseteq V(G)$ be even-sized. Then there exists a $T$-join
$H$ of $G$ which is a co-forest, such that $E_{\hat{H}}(v)\subseteq\\{e\\}$.

If additionally the graph $G$ from Proposition 2.6 is of even order, by
setting $T=V(G)$, we derive the following.

######  Corollary 2.7.

In a connected loopless graph $G$ of even order, let $v$ be an internal vertex
and $e\in E_{G}(v)$. Then there exists a spanning odd co-forest $H$ of $G$
such that $E_{\hat{H}}(v)\subseteq\\{e\\}$.

##  3 Subdivisions of odd graphs

Recall that $\mathcal{S}$ denotes the class of subdivisions of odd graphs. The
following proposition is an overture to our subsequent study of the class
$\mathcal{S}$ in terms of the value of the odd chromatic index. The final
product of the study, our main result here, shall be formulated by the end of
the article. As a warm-up, we commence by showing that four colors always
suffice for an odd edge-coloring of any member of $\mathcal{S}$. Moreover, if
necessary at all, the fourth color can be reduced to a single appearance.

######  Proposition 3.1.

Let $G\in\mathcal{S}$ be connected and non-trivial, let $v$ be a $2$-vertex of
$G$ and $e\in E_{G}(v)$. Then $G$ admits an odd edge-coloring with color set
$\\{1,2,3,4\\}$ such that the color class $E_{4}\subseteq\\{e\\}$. Moreover,
if $\chi^{\prime}_{o}(G)=4$ then it holds that:

  * $(i)$

Every $2$-vertex is internal;

  * $(ii)$

No $2$-vertices are adjacent.

###### Proof.

If there happens to exist a cut-vertex $u$ of $G$ such that $d_{G}(u)=2$, then
$u$ must be incident with two bridges. Consequently, Proposition 2.3 yields
odd $3$-edge-colorability of $G$. Assuming $(i)$, the vertex $v$ is internal.
Consequently, the graph $G-e$ is connected and of minimum degree $1$, so it
admits an odd edge-coloring with color set $\\{1,2,3\\}$. By assigning the
color $4$ to the edge $e$ we obtain the promised coloring of $E(G)$. This
proves the first part and, in addition, confirms $(i)$ whenever
$\chi^{\prime}_{o}(G)=4$.

As for $(ii)$, still assuming $\chi^{\prime}_{o}(G)=4$, suppose there is an
edge $f$ whose endpoints $u$ and $w$ are $2$-vertices. Let $g_{u}$ and $g_{w}$
be the other edges (besides $f$) incident with $u$ and $w$, respectively.
Since $g_{u}$ and $g_{w}$ are pendant edges in the graph $G-f$, Proposition
2.3 guarantees that there is an odd edge-coloring $\varphi$ of $G-f$ with
color set $\\{1,2,3\\}$. Extend $\varphi$ to $E(G)$ by assigning $f$ with a
color from $\\{1,2,3\\}\backslash\\{\varphi(g_{u}),\varphi(g_{w})\\}$. This
completes an odd $3$-edge-coloring of $G$, a contradiction.∎

Note that the first part of Proposition 3.1 supports Conjecture 1.4. For our
intended characterization of the members of the class $\mathcal{S}$ in terms
of their odd chromatic index, let us denote by $\mathcal{S}_{i}$ $(i=1,2,3,4)$
the subclass consisting of those $G\in\mathcal{S}$ having
$\chi^{\prime}_{o}(G)=i$. Clearly, $\mathcal{S}_{1}$ comprises the class of
odd graphs $\mathcal{O}$. At the other end of the spectrum, the second part of
Proposition 3.1 gives a pair of necessary conditions for membership into
$\mathcal{S}_{4}$, or equivalently, describes two sufficient conditions for
odd $3$-edge-colorability of a subdivision of an odd graph. The following
result provides another such condition (which shall be useful on more than one
occasion later on in this section).

######  Proposition 3.2.

Let $G\in\mathcal{S}$ be a connected graph, and $C\subseteq G$ be a cycle
passing through a $2$-vertex $v$ of $G$. If the cycle $C$ is even or it passes
through another $2$-vertex, then $G$ is odd $3$-edge-colorable.

###### Proof.

By Propositions 2.3 and 3.1 $(ii)$, respectively, we may assume that the order
$n(G)$ and the degree of each neighbor of $v$ are odd. If the neighborhood
$N_{G}(v)$ happens to be a singleton, in which case there is a cycle $C$ of
length $2$ that goes through $v$, the odd $3$-edge-coloring of $G$ is
immediate. Indeed, since $G-v$ is connected and of even order, simply take an
odd co-forest of $G-v$ and its edge-complement in regard to $G$: the former
graph is odd $1$-edge-colorable, whereas the latter is a unicyclic graph that
is odd $2$-edge-colorable (as Corollary 2.5 applies).

Thus, assuming $N_{G}(v)=\\{u,w\\}$, let $P=C-v$ be a $u$-$w$ path that (by
assumption) is even or passes through another $2$-vertex of $G$. For an
arbitrary odd co-forest $H$ of $G-v$, consider the forest $\hat{H}=G-v-E(H)$.
Note that the vertices of odd degree in $\hat{H}$ are precisely $u,w$ and the
$2$-vertices of $G$ that are within $G-v$. In particular, every $2$-vertex
$\neq v$ is a pendant vertex of the forest $\hat{H}$. Looking at
$G-E(H)=\hat{H}+\\{uv,vw\\}$, there are two possibilities: this graph is
either a forest (if $u,w$ do not share a component of $\hat{H}$), or it is a
unicyclic graph such that no vertex of the cycle has an odd degree. Therefore,
in view of Corollary 2.5, the graph $\hat{H}+\\{uv,vw\\}$ is odd $2$-edge-
colorable (and consequently $G$ is odd $3$-edge-colorable), unless it is
always the case that a component of $\hat{H}$ is an odd $u$-$w$ path, say $Q$.

Supposing the latter, it is essential to note that $P\neq Q$. Namely, if the
cycle $C$ happens to be even, then $P$ and $Q$ are of different parities; and
if $C$ passes through a $2$-vertex of $G$ contained within $G-v$, then so does
$P$ but not $Q$ (as every such $2$-vertex of $G$ is a pendant vertex of
$\hat{H}$). Let $Q_{u}$ and $Q_{w}$ be, respectively, the components of $u$
and $w$ in $P\cap Q$. Notice that these two are disjoint paths having as an
endpoint $u$ and $w$, respectively. Thus $Q_{u}\cup Q_{w}\subset P$. Now
consider an odd co-forest $H$ of $G-v$ that maximizes $Q_{u}\cup Q_{w}$ in
respect of $\subseteq$. Say $e_{u}$ and $e_{w}$ are the first and the last
edge lying outside $Q_{u}\cup Q_{w}$ on a traversing of $P$ from $u$ to $w$.

Figure 3: The path $P$ and the components of $\hat{H}$ (all are shaded, apart
from $Q$). The edges of $P$ are depicted as heavier, and those of $Q_{u}\cup
Q_{w}$ as fat. On a traversal of $P$ from $u$ to $w$, the arrows notify the
first embarkment and last disembarkment of $P-E(Q)$. Since this happens
precisely along the edges $e_{u}$ and $e_{w}$, respectively, these two cannot
be cycle edges of $\hat{H}\oplus P\oplus Q$. The same is obviously true for
any edge of $Q_{u}\cup Q_{w}$.

Take the symmetric difference $H\oplus P\oplus Q$, with both $P$ and $Q$ seen
as spanning subgraphs of $G-v$. The obtained graph is clearly another odd
factor of $G-v$, though not necessarily a co-forest. Nevertheless, the
important feature (which is preserved in passing from $H$ to $H\oplus P\oplus
Q$) is that no edge from $Q_{u}\cup\\{e_{u}\\}\cup\\{e_{w}\\}\cup Q_{w}$
belongs to a cycle contained entirely in the edge-complement of $H\oplus
P\oplus Q$ with reference to $G-v$ (cf. Figure 3). Therefore, by taking as
$H^{\prime}$ any maximal odd factor of $G-v$ subjected to the condition
$H\oplus P\oplus Q\subseteq H^{\prime}$, we are guaranteed that $H^{\prime}$
is a spanning odd co-forest of $G-v$ and it is also edge-disjoint from
$Q_{u}\cup Q_{w}$. Moreover, if $Q^{\prime}$ denotes the odd $u$-$w$ path that
(according to our supposition) constitutes a component of the forest
$\hat{H^{\prime}}=G-v-E(H^{\prime})$, and $Q^{\prime}_{u},Q^{\prime}_{w}$ are
defined analogously as before, then $Q_{u}\subset Q^{\prime}_{u}$ and
$Q_{w}\subset Q^{\prime}_{w}$. Indeed, as $Q_{u}\cup Q_{w}\subseteq
Q^{\prime}$ and $Q^{\prime}$ constitutes a path, it must be that
$Q_{u}\cup\\{e_{u}\\}\subseteq Q^{\prime}_{u}$ and similarly
$Q_{w}\cup\\{e_{w}\\}\subseteq Q^{\prime}_{w}$. Consequently, $Q_{u}\cup
Q_{w}\subset Q^{\prime}_{u}\cup Q^{\prime}_{w}$, contradicting our choice of
$H$. This settles the proposition. ∎

Our next result concerns odd $2$-edge-colorability of subdivisions of odd
graphs, and thus yields a structural characterization of $\mathcal{S}_{2}$.

######  Proposition 3.3.

The following statements are equivalent for every graph $G\in\mathcal{S}$:

  * $(i)$

$\chi^{\prime}_{o}(G)\leq 2$;

  * $(ii)$

For every cycle $C$ of $G$ the set $\\{v:v\in V(C)\text{ and }d_{G}(v)=2\\}$
is even-sized.

###### Proof.

Let $G_{0}$ be the underlying odd graph, that is, a graph whose subdivision is
$G$. Noting that $G_{0}$ is well-defined, distinguish between even and odd
edges $e\in E(G_{0})$ depending on the parity of the number of $2$-vertices of
$G$ that have been introduced along $e$. The corresponding subsets of
$E(G_{0})$ are $E_{\mathrm{even}}$ and $E_{\mathrm{odd}}$. Let $P_{e}$ be the
path (or cycle) in $G$ arising from the edge $e$; thus, $e$ is even if and
only if the length $\ell(P_{e})$ is odd. Define a graph $H$ whose vertices
correspond to the components of $G_{0}-E_{\mathrm{odd}}$; for each $e\in
E_{\mathrm{odd}}$, we put an edge in $H$ whose endpoints are the components of
$G_{0}-E_{\mathrm{odd}}$ containing the endpoints of $e$. In other words, $H$
is the graph obtained from $G_{0}$ by contracting every component of
$G_{0}-E_{\mathrm{odd}}$. The equivalence of $(i)$ and $(ii)$ shall be
established via a third statement:

  * $(iii)$

$H$ is bipartite.

Namely, we proceed to show the following string of implications:
$(i)\Rightarrow(ii)\Rightarrow(iii)\Rightarrow(i)$.

  * •

$(i)\Rightarrow(ii)$: Considering an odd $2$-edge-coloring $\varphi$ of $G$,
let $C$ be an arbitrary cycle in $G$. For any $v\in V(C)$, the set $E_{C}(v)$
is dichromatic under $\varphi$ if and only if $d_{G}(v)=2$. Therefore,
$\\{v:v\in V(C)\text{ and }d_{G}(v)=2\\}$ is of even size.

  * •

$(ii)\Rightarrow(iii)$: From a cycle $C$ in $H$, we can obtain a cycle $C_{0}$
in $G_{0}$ as follows. For $v\in V(C)$, let $e,f$ be the edges of $C$ incident
to $v$ (not necessarily distinct), and let $x,y$ be the endpoints of $e,f$ in
the component of $G_{0}-E_{\mathrm{odd}}$ corresponding to $v$. We expand $v$
into an $x$-$y$ path in that component. Since $C$ visits each vertex at most
once, the resulting $C_{0}$ is a cycle in $G_{0}$. Let $C^{\prime}$ be the
cycle in $G$ obtained by replacing each $e\in E(C_{0})$ with $P_{e}$. By
construction, we have $|\\{v:v\in V(C^{\prime})\text{ and
}d_{G}(v)=2\\}|\equiv_{2}\ell(C)$, where $\ell(C)$ denotes the length of $C$.
Hence, $(ii)$ implies that $\ell(C^{\prime})$ is even. Consequently, $H$ is
bipartite.

  * •

$(iii)\Rightarrow(i)$: Let $X,Y$ be a bipartition of $H$. To every edge $e\in
E_{\mathrm{even}}$ assign a color from the set $\\{1,2\\}$ as follows. If the
component of $G_{0}-E_{\mathrm{odd}}$ containing $e$ represents a vertex in
$X$, then color $e$ by $1$; contrarily, color $e$ by $2$. This readily gives a
partial $2$-edge-coloring of $G$: namely, for every $2$-vertex $v$ of $G$
lying on an even edge $e$ of $G_{0}$, color $E_{G}(v)$ by the color assigned
to $e$. The uncolored part of $E(G)$ is $\bigcup_{e\in
E_{\mathrm{odd}}}E(P_{e})$. Since $e\in E_{\mathrm{odd}}$ has an endpoint
within each partite set, the path $P_{e}$ admits a proper $2$-edge-coloring
such that its edge ‘incident’ with $X$ (resp. $Y$) receives color $1$ (resp.
$2$). This completes an odd $2$-edge-coloring of $G$.

∎

The above proof provides more than just another glimpse at the beautiful idea
of proving an equivalence of two given assertions using a third (not obvious)
one, which is equivalent to each of them. Namely, as the fulfillment of
statement $(iii)$ can be efficiently checked, our characterization of odd
$2$-edge-colorability within $\mathcal{S}$ is good and, in the affirmative,
such a coloring can be found in polynomial time.

######  Corollary 3.4.

Let $G\in\mathcal{S}$. Then $\chi^{\prime}_{o}(G)=2$ if and only if
$G\notin\mathcal{O}$ and for every cycle $C$ of $G$ the set $\\{v:v\in
V(C)\text{ and }d_{G}(v)=2\\}$ is even-sized.

In the remainder of the paper we provide a structural characterization of the
class $\mathcal{S}_{4}$. The next result shall allow us to confine to
$2$-connected graphs.

######  Proposition 3.5.

If $G\in\mathcal{S}$ is a connected graph, then $\chi^{\prime}_{o}(G)=4$ if
and only if every block of $G$ belongs to $\mathcal{S}_{4}$ and for every cut-
vertex $v$ there is a unique block $B$ such that $d_{B}(v)$ is odd.

###### Proof.

The essential part of our proof is to establish property $(P)$ below, which
sheds some light on the structure of graphs $G\in\mathcal{S}$ of connectivity
$\kappa(G)=1$ that require four colors for an odd edge-coloring.

$(P)$ Let $G\in\mathcal{S}$ be connected and $v$ a cut-vertex of $G$. If
$G_{1},\ldots,G_{k}$ are the $v$-lobes of $G$, then the following statements
are equivalent:

  * $(i)$

$\\{G_{1},G_{2},\ldots,G_{k}\\}\subseteq\mathcal{S}_{4}$ and there is a unique
$j$ such that $d_{G_{j}}(v)$ is odd;

  * $(ii)$

$G\in\mathcal{S}_{4}$.

Notice that, once the equivalence stated in $(P)$ is verified, the proposition
may be derived by inducting on the number $t$ of cut-vertices in $G$. Namely,
the case $t=0$ is trivial, whereas the case $t=1$ follows immediately from
$(P)$. For $t>1$, consider an end-block of $G$, say $B_{0}$, and let $v_{0}$
be the corresponding cut-vertex of $G$. By applying $(P)$ to the pair
$G,v_{0}$ we deduce that $G\in\mathcal{S}_{4}$ if and only if both
$B_{0},G-\mathrm{Int}(B_{0})\in\mathcal{S}_{4}$. Now the inductive hypothesis
applies to $G-\mathrm{Int}(B_{0})$.

In what follows, we verify $(P)$ by proving both $(i)\Rightarrow(ii)$ and
$(ii)\Rightarrow(i)$. First we show the easy part, which is direction
$(i)\Rightarrow(ii)$. Arguing by contradiction, in view of Proposition 3.1,
assume $(i)$ and consider an odd $3$-edge-coloring $\varphi$ of $G$. For every
$i=1,\ldots,k$, let $\varphi_{i}$ be the restriction of $\varphi$ to
$E(G_{i})$, i.e., $\varphi_{i}=\varphi_{|E(G_{i})}$. Since
$\chi^{\prime}_{o}(G_{i})=4$, the edge-coloring $\varphi_{i}$ is even at $v$.
Consequently, whenever $d_{G_{i}}(v)=2$ the edge set $E_{G_{i}}(v)$ is
monochromatic under $\varphi_{i}$. However, then $\varphi_{j}$ must be an odd
$3$-edge-coloring of $G_{j}$, a contradiction.

Now let us prove direction $(ii)\Rightarrow(i)$. Assuming $(ii)$, note that
degree $d_{G}(v)$ is odd by Proposition 3.1. We break the argument into
several claims which eventually lead to $(i)$.

Claim 1. If $G^{\prime}\cup G^{\prime\prime}=G$ and $G^{\prime}\cap
G^{\prime\prime}=\\{v\\}$, then orders $n(G^{\prime}),n(G^{\prime\prime})$ are
odd.

By Proposition 2.3, $n(G)$ is odd. Suppose $n(G^{\prime}),n(G^{\prime\prime})$
are even. Then there exist spanning odd co-forests $H^{\prime}$ and
$H^{\prime\prime}$ in $G^{\prime}$ and $G^{\prime\prime}$, respectively.
Denote $F=G-E(H^{\prime}\cup H^{\prime\prime})$. Note that $F$ is a forest and
$d_{F}(v)$ is odd. This enables construction of an odd $3$-edge-coloring of
$G$ as follows: color $E(H^{\prime})$ by $1$ and $E(H^{\prime\prime})$ by $2$;
color $E_{F}(v)$ by $3$; extend the coloring of $E_{F\cap G^{\prime}}(v)$ to
an edge-coloring of the forest $F\cap G^{\prime}$ with color set $\\{2,3\\}$
that is odd away from $v$; similarly, extend the coloring of $E_{F\cap
G^{\prime\prime}}(v)$ to an edge-coloring of the forest $F\cap
G^{\prime\prime}$ with color set $\\{1,3\\}$ that is odd away from $v$. The
obtained contradiction proves our point. $\diamond$

Consequently, every $v$-lobe of $G$ has an odd order. We show next that none
of the $v$-lobes is odd $3$-edge-colorable.

Claim 2. $\chi^{\prime}_{o}(G_{i})=4$ for every $i=1,2,\ldots,k$.

Supposing a $v$-lobe $G_{i}$ is odd $3$-edge-colorable, take an odd edge-
coloring $\varphi_{i}$ of $G_{i}$ with color set $\\{1,2,3\\}$ such that the
color $1$ appears (resp. does not appear) on $E_{G_{i}}(v)$ if $d_{G_{i}}(v)$
is odd (resp. even). Let $\bar{G_{i}}=\bigcup\\{G_{j}:j=1,2,\ldots,k\text{ and
}j\neq i\\}$. Since $n(G_{j})$ is odd for every $j\neq i$, there exists an odd
co-forest $K$ in $\bar{G_{i}}-v$. (Indeed, simply take an odd co-forest
$K_{j}$ in every $G_{j}-v$ and then form the union of these $K_{j}$’s.) Color
the edge set $E(K)$ by $3$. Use the color $1$ on all of $E_{\bar{G_{i}}}(v)$
and (by Proposition 2.1) extend to an edge-coloring of $\bar{G_{i}}-E(K)$ with
color set $\\{1,2\\}$ that is odd away from $v$. This completes a $3$-edge-
coloring $\bar{\varphi_{i}}$ of $\bar{G_{i}}$ that is odd away from $v$.
However, then $\varphi_{i}\cup\bar{\varphi_{i}}$ is an odd $3$-edge-coloring
of $G$, a contradiction. $\diamond$

Proceed by showing that each $v$-lobe is a subdivision of an odd graph.

Claim 3. $G_{i}\in\mathcal{S}$ for every $i=1,2,\ldots,k$.

Supposing the opposite, let $G_{i}$ be a $v$-lobe such that $d_{G_{i}}(v)$ is
even and $d_{G_{i}}(v)\geq 4$. Once again, consider the subgraph
$\bar{G_{i}}=\bigcup\\{G_{j}:j=1,2,\ldots,k\text{ and }j\neq i\\}$. By Claim
1, every component of $\bar{G_{i}}-v$ is of even order, and thus there is an
odd co-forest $K$ in $\bar{G_{i}}-v$. Note that the edge-complement
$\hat{K}=\bar{G_{i}}-E(K)$ is such that $\hat{K}-v$ is a forest, and moreover
the degree $d_{\hat{K}}(v)=d_{\bar{G_{i}}}(v)$ is odd. Color $E(K)$ by $3$. By
Proposition 2.2, $\hat{K}$ admits an edge-coloring with color set $\\{1,2\\}$
that is odd away from $v$ and under which the color $1$ (resp. $2$) is odd
(resp. even) at $v$. This furnishes an edge-coloring $\bar{\varphi_{i}}$ of
$\bar{G_{i}}$ with color set $\\{1,2,3\\}$ that is odd away from $v$, whereas
at $v$ the color $1$ is odd, the color $2$ is even, and the color $3$ does not
appear. We shall prove the existence of an edge-coloring $\varphi_{i}$ of
$G_{i}$ with color set $\\{1,2,3\\}$ that is also odd away from $v$, and such
that at $v$ both the colors $2$ and $3$ are odd while the color $1$ is even.
(Then $\varphi_{i}\cup\bar{\varphi_{i}}$ would be an odd $3$-edge-coloring of
$G$, which would give the desired contradiction.)

Begin by noting that the following assertion is equivalent to the existence of
$\varphi_{i}$: The lobe $G_{i}$ can be turned into an odd $3$-edge-colorable
graph by splitting out $v$ entirely into $2$-vertices and then suppressing all
of them except one. Indeed, if such a splitting modification of $G_{i}$
exists, then the obtained graph admits an odd edge-coloring with color set
$\\{1,2,3\\}$ so that the colors $2$ and $3$ appear at the $2$-vertex which
‘survives the suppression’, and this coloring readily leads to the desired
$\varphi_{i}$; the other way around, with an existing $\varphi_{i}$, create
the $2$-vertex which remains unsuppressed so that its incident edges are
colored by $2$ and $3$ under $\varphi$, and then create the rest of the
$2$-vertices so that each of them is incident with equally colored edges.

Therefore, in view of Proposition 3.2, it suffices to show that there is an
even cycle $C$ in $G_{i}$ which passes through $v$. Namely, using such a cycle
$C$, start the ‘splitting procedure’ by creating a $2$-vertex $v^{\prime}$
incident to the edges forming $E_{C}(v)$. Then arbitrarily split out the rest
of $v$ into $2$-vertices and suppress them all (except $v^{\prime}$). The
obtained graph is odd $3$-edge-colorable (by Proposition 3.2) because $C$ has
become an even cycle passing through the $2$-vertex $v^{\prime}$.

For demonstrating the existence of an even cycle $C\subseteq G$ with $v\in
V(C)$, we may assume that every bouquet of $G_{i}$ incident with $v$ is a
singleton. Since $d_{G_{i}}(v)\geq 4$, consider a triplet $x,y,z\in
N_{G_{i}}(v)$. If there is an even $x$-$y$ path in $G_{i}-v$, we are obviously
done. As $G_{i}-v$ is connected, let $Q$ be an odd $x$-$y$ path. We show there
is an even path going from $z$ to the set $\\{x,y\\}$. In view of the
connectedness, say $P$ is an odd $z$-$x$ path. On a traversal of $P$ from $z$
to $x$, take $w$ to be the first vertex that belongs to $Q$. Then $zPw\cup
wQx$ and $zPw\cup wQy$ are paths (by the choice of $w$). Because $wQx$ and
$wQy$ are of opposite parities, we have found an even $z$-$\\{x,y\\}$ path,
which in turn yields an even cycle $C$ through $v$. In conclusion, it is
always possible to construct the desired $\varphi_{i}$. $\diamond$

The final piece of our argument is showing that $v$ is of odd degree in
precisely one $v$-lobe.

Claim 4. There is a unique $j\in\\{1,2,\ldots,k\\}$ such that $d_{G_{j}}(v)$
is odd.

Since $d_{G}(v)$ is odd, so is $d_{G_{j}}(v)$ for some $j$. Suppose there are
at least two such indices, say $j_{1}$ and $j_{2}$. Let
$G^{\prime}=G_{j_{1}}\cup G_{j_{2}}$ and
$G^{\prime\prime}=\bigcup\\{G_{i}:i=1,2,\ldots,k\text{ and }i\neq
j_{1},j_{2}\\}$. There exists an odd edge-coloring $\varphi^{\prime}$ of
$G^{\prime}$ with color set $\\{1,2,3\\}$ such that $E_{G}^{\prime}(v)$ is
colored by $1$ and $2$. Indeed, simply take an odd co-forest $H_{k}$ of
$G_{j_{k}}-v$ for $k=1,2$, color $H_{1}\cup H_{2}$ with $3$, and take an edge-
coloring of $\hat{H_{k}}=G_{j_{k}}-E(H_{k})$ with color set $\\{1,2\\}$ which
is odd away from $v$ and so that the color $k$ is odd at $v$ in $\hat{H_{k}}$.
Combine this $\varphi^{\prime}$ with an edge-coloring $\varphi^{\prime\prime}$
of $G^{\prime\prime}$ with color set $\\{1,2,3\\}$ that is odd away from $v$
and colors $E_{G^{\prime\prime}}(v)$ by $1$. Such $\varphi^{\prime\prime}$ can
be obtained as follows: take an odd co-forest in each $G_{i}-v$ for $i\neq
j_{1},j_{2}$, and color its edge set by $3$; then color
$E_{G^{\prime\prime}}(v)$ by $1$ and extend to an edge-coloring with color set
$\\{1,2\\}$ (of the still uncolored part of $G^{\prime\prime}$) such that the
coloring is odd away from $v$. We thus obtain an odd $3$-edge-coloring
$\varphi^{\prime}\cup\varphi^{\prime\prime}$ of $G$, a contradiction.
$\diamond$

This completes the verification of $(ii)\Rightarrow(i)$, and thus settles
$(P)$ and the proposition. ∎

We are left with the task of determining which $2$-connected graphs belong to
$\mathcal{S}_{4}$. Let us first narrow down the search by establishing a
necessary condition.

######  Proposition 3.6.

If $G\in\mathcal{S}_{4}$ is a block graph, then $G$ can be obtained from a
bipartite $2$-connected odd graph by a single edge subdivision.

###### Proof.

Since $G\in\mathcal{S}_{4}$, its order is odd (by Proposition 2.3). Hence,
there exists a $2$-vertex $v\in V(G)$. As $G$ is a block graph, every pair of
vertices lie on a cycle. Thus, in view of Proposition 3.2, vertex $v$ is the
only $2$-vertex in $G$. Moreover, every cycle through $v$ is odd. We are left
to show that every cycle that avoids $v$ is even.

Letting $N_{G}(v)=\\{u,w\\}$, suppose there is an odd cycle $C_{o}$ in $G-v$.
By the $2$-connectedness of $G$, there exist two disjoint
$\\{u,w\\}$-$V(C_{o})$ paths, say a $u$-$u^{\prime}$ path $P$ and a
$w$-$w^{\prime}$ path $Q$. Let $R$ denote the $u^{\prime}$-$w^{\prime}$ path
along $C_{o}$ which is even (resp. odd) if $P$ and $Q$ have same (resp.
opposite) parities. Then $P\cup R\cup Q$ is an even $u$-$w$ path in $G-v$.
However, we have already established that no cycle through $v$ is even. This
contradiction proves our point. Namely, the graph $G\%v$, obtained from $G$ by
suppressing $v$, is a $2$-connected bipartite odd graph. ∎

Not every graph which can be obtained from a bipartite $2$-connected odd graph
by a single edge subdivision belongs in $\mathcal{S}_{4}$. For example, it can
be readily seen from Figure 4 that the graph obtained from $K_{3,5}$ by a
single edge subdivision is odd $3$-edge-colorable. On the other hand, in view
of Theorem 1.6, this is not the case for the analogous graph obtained from
$K_{3,3}$. So our next step is to characterize which graphs obtainable from a
bipartite $2$-connected odd graph by a single edge subdivision are members of
$\mathcal{S}_{4}$.

Figure 4: An odd $3$-edge-coloring of the graph obtained from $K_{3,5}$ by a
single edge subdivision.

Consider a graph $G$ that is obtainable from a bipartite $2$-connected odd
graph by a single edge subdivision. Thus
$\kappa(G)=\kappa^{\prime}(G)=\delta(G)=2$. Assume $G$ is not essentially
$3$-edge-connected, that is, let there be an (edge) $2$-cut $[X,\bar{X}]$ such
that $|X|,|\bar{X}|\geq 2$. If the unique $2$-vertex falls in $X$, consider
the graphs $G^{\prime}$ and $G^{\prime\prime}$ constructed as follows:
$G^{\prime}$ is derived from $G[X]$ by adding an edge between the endpoints of
the $2$-cut in $X$; $G^{\prime\prime}$ is obtained from $G[\bar{X}]$ by
introducing a new vertex and joining it with the endpoints of the $2$-cut in
$\bar{X}$ (equivalently, $G^{\prime\prime}=G/X$). Notice that both
$G^{\prime},G^{\prime\prime}$ are obtainable from bipartite $2$-connected odd
graphs by single edge subdivisions (see Figure 5). Reversing the process, let
$G^{\prime},G^{\prime\prime}$ be disjoint graphs that are obtained from
$2$-connected bipartite odd graphs by single edge subdivisions. Break a
selected edge of $G^{\prime}$ into two half-edges, then remove the $2$-vertex
of $G^{\prime\prime}$ along with its incident half-edges, and finally glue the
half-edges emanating from $G^{\prime}$ with the half-edges emanating from
$G^{\prime\prime}$ so that two new (whole) edges are created. Call this
process gluing of $G^{\prime}$ and $G^{\prime\prime}$. Notice that the
resulting graph $G$ is also obtainable from a $2$-connected bipartite odd
graph by single edge subdivision, and moreover has a non-trivial $2$-cut.

Figure 5: Graph $G$ (left), and graphs $G^{\prime},G^{\prime\prime}$ (right).
The fat edges form the symmetric difference $E(G)\oplus(E(G^{\prime})\cup
E(G^{\prime\prime}))$.

The importance of transforming $G$ into the pair $G^{\prime},G^{\prime\prime}$
and vice versa comes from the following.

######  Proposition 3.7.

Let $G$ be a graph that is obtained from a $2$-connected bipartite odd graph
by a single edge subdivision, and let $[X,\bar{X}]$ be a nontrivial $2$-cut in
$G$ such that the unique $2$-vertex is in $X$. With
$G^{\prime},G^{\prime\prime}$ as described above, the following equivalence
holds:

$\chi^{\prime}_{o}(G)=4\quad\text{ if and only if
}\quad\chi^{\prime}_{o}(G^{\prime})=\chi^{\prime}_{o}(G^{\prime\prime})=4\,.$

###### Proof.

Assuming $\chi^{\prime}_{o}(G)=4$, we argue by contradiction that
$\chi^{\prime}_{o}(G^{\prime})=\chi^{\prime}_{o}(G^{\prime\prime})=4$. In view
of Proposition 3.1, more than four colors are never required. Let $e\in
E(G^{\prime})\backslash E(G)$. Suppose $\chi^{\prime}_{o}(G^{\prime})\leq 3$
and consider an odd $3$-edge-coloring $\varphi$ of $G^{\prime}$. Extend the
restriction $\varphi_{|E(G[X])}$ to $E(G)$ by using the color $\varphi(e)$ for
$E(G)\backslash E(G[X])$. This gives an odd $3$-edge-coloring of $G$, a
contradiction.

Suppose now that $\chi^{\prime}_{o}(G^{\prime\prime})\leq 3$. We already know
from Proposition 3.6 (or from Proposition 2.3) that the graph $G^{\prime}\%e$,
obtained from $G^{\prime}$ by introducing a $2$-vertex on the edge $e$, is odd
$3$-edge-colorable. However then an odd $3$-edge-coloring of $G$ arises by
combining an odd $3$-edge-coloring of $G^{\prime}\%e$ and an odd $3$-edge-
coloring of $G^{\prime\prime}$ with the same color set (after possibly
permuting colors in the latter). This contradiction settles that from
$\chi^{\prime}_{o}(G)=4$ it follows that
$\chi^{\prime}_{o}(G^{\prime})=\chi^{\prime}_{o}(G^{\prime\prime})=4$.

Let us show the reversed implication by contrapositive. Assume an odd
$3$-edge-coloring of $G$ exists and consider its restrictions over the $2$-cut
$[X,\bar{X}]$. If the two edges from the cut are colored the same, then we
have an odd $3$-edge-coloring of $G^{\prime}$. Contrarily, if the two edges
are colored differently, then an odd $3$-edge-coloring of $G^{\prime\prime}$
readily appears. ∎

##  4 Characterization of $\mathcal{S}_{4}$

As a result of Proposition 3.5, we may confine to $2$-connected graphs. Let us
denote by $\mathcal{F}$ the family defined inductively as follows:

  * $(a)$

every Shannon triangle of type $(2,1,1)$ and minimum degree $2$ belongs to
$\mathcal{F}$;

  * $(b)$

every graph that can be obtained from a $2$-connected bipartite cubic graph by
a single edge subdivision belongs to $\mathcal{F}$;

  * $(c)$

every other graph in $\mathcal{F}$ can be constructed by taking disjoint
members $G^{\prime},G^{\prime\prime}\in\mathcal{F}$ and gluing them together.

Clearly, every member of $\mathcal{F}$ is a $2$-connected graph and a
subdivision of an odd graph. Note in passing that parts $(a)$ and $(b)$ of the
above constructive definition are not entirely ‘disjoint’ as the smallest
Shannon triangle of type $(2,1,1)$ is included in both. The family
$\mathcal{F}$ happens to be vital for our desired characterization. Namely, it
turns out that a block graph $G$ belongs to $\mathcal{S}_{4}$ if and only if
it belongs to $\mathcal{F}$, which we prove next.

######  Theorem 4.1.

Let $G\in\mathcal{S}$ be a 2-connected graph. Then the following statements
are equivalent:

  * $(i)$

$G\in\mathcal{F}$;

  * $(ii)$

$G\in\mathcal{S}_{4}$.

To prove Theorem 4.1, we proceed by separately establishing that
$(i)\Rightarrow(ii)$ and $(ii)\Rightarrow(i)$. Since
$\mathcal{F}\subseteq\mathcal{S}$, the former implication amounts to showing
that every graph $G\in\mathcal{F}$ has odd chromatic index
$\chi^{\prime}_{o}(G)=4$. So, in view of the equality (1.1) and Proposition
3.7, we only need to use the following fact: Every graph that may be obtained
from a bipartite cubic graph by a single edge subdivision is not odd $3$-edge-
colorable. The proof of this is a straightforward double-counting argument
(see [1] for the details).

The key ingredient for proving the implication $(ii)\Rightarrow(i)$ is
provided by the next auxiliary result, that clarifies which $2$-connected and
essentially $3$-edge-connected subdivisions of odd graphs require four colors
for an odd edge-coloring.

######  Lemma 4.2.

If $G\in\mathcal{S}_{4}$ is a $2$-connected and essentially $3$-edge-connected
graph, then its maximum degree $\Delta(G)$ or its order $n(G)$ equals $3$.

Proof of Lemma 4.2. In view of Proposition 3.6, let $v$ be the unique
$2$-vertex of $G$, and set $N_{G}(v)=\\{u,w\\}$. As $\chi^{\prime}_{o}(G)=4$,
it follows from Proposition 2.3 that the order $n(G)$ is odd. Moreover, by
Proposition 3.6, the graph $G\%v$ is bipartite, that is, every cycle through
$v$ is odd and every cycle avoiding $v$ is even. Since, apart from $v$, every
other vertex in $G$ is of odd degree we have the following.

Claim 1. No connected even subgraph $H\subseteq G$ is such that $v\in V(H)$
and $n(H)$ is even.

Arguing by contradiction, note that in the edge-complement $\hat{H}=G-E(H)$,
the vertex $v$ is isolated whereas every other vertex has an odd degree. Take
an odd factor $K$ of $H$, and color $E(K)$ by $1$, $E(H)\backslash E(K)$ by
$2$ and $E(G)\backslash E(H)$ by $3$. This gives an odd $3$-edge-coloring of
$G$, a contradiction. $\diamond$

In particular, it follows from Claim 1 that there is no pair of cycles
$C,C^{\prime}$, one of which passes through $v$, such that $V(C)\cap
V(C^{\prime})$ is a singleton; call this formation a forbidden cycle pair (cf.
Figure 6). Several structural constraints arise from the absence of forbidden
cycle pairs.

Figure 6: A forbidden cycle pair.

Supposing $\Delta(G)\geq 5$ and $n(G)\geq 5$, consider an arbitrary ‘large’
vertex $z$, that is, a vertex of degree $d_{G}(z)\geq 5$. By the
$2$-connectedness of $G$, there exists a cycle $C\subseteq G$ such that
$v,z\in V(C)$ and $|V(C)|\geq 5$. Indeed, if $z\neq u,w$ then any cycle
through $v$ and $z$ works; contrarily, select a vertex from
$V(G)\backslash\\{u,v,w\\}$ and use a cycle passing through $v$ and that
vertex. Let $P=C-v$ be the $u$-$w$ path that goes through $z$ and is contained
within $C$ (it may happen that $z$ is an endpoint of $P$). We consider the
collection $\mathcal{P}_{z}$ of paths $Q$ in $G-v$ such that $P\cap Q$
consists of two isolated points, one of which is $z$. Let us refer to the
other endpoint of $Q\in\mathcal{P}_{z}$ as its ending. We denote by
$\mathrm{In}(Q)$ the set of internal vertices of the path $Q$, those that are
not its endpoints.111Not to be confused with ‘internal vertices of a block’.

Claim 2. There is a mapping from $E_{G}(z)\backslash E_{C}(z)$ to
$\mathcal{P}_{z}$, sending $e\mapsto Q_{e}$, such that $e$ is the initial edge
of $Q_{e}$ (on a traversing of $Q_{e}$ that starts at $z$). Moreover, for
every such mapping it holds that

$e\neq e^{\prime}\quad\Rightarrow\quad Q_{e}\text{ and }Q_{e^{\prime}}\text{
are internally disjoint, i.e.,
}\mathrm{In}(Q_{e})\cap\mathrm{In}(Q_{e^{\prime}})=\emptyset\,.$

If the other endpoint of $e$ (besides $z$) belongs to $V(P)$, then the path
$Q_{e}$ is uniquely determined: namely, it is the $1$-path with edge set
$\\{e\\}$. Contrarily, if that endpoint of $e$ does not belong to $V(P)$, then
it falls into a component, say $K_{e}$, of $G-V(C)$. Note that then $e\neq
e^{\prime}$ implies $K_{e}\neq K_{e^{\prime}}$, for otherwise a forbidden
cycle pair (that includes $C$) is present (cf. Figure 7). Thus, $Q_{e}$ exists
in this case as well. (However, as $e\notin\\{vu,vw\\}$, the ending of $Q_{e}$
is no longer uniquely determined: indeed, for then $|\partial(K_{e})|\geq 3$
and no two edges from the edge cut $\partial(K_{e})$ have the same endpoint on
$P$.)

Figure 7: A forbidden cycle pair (at $z$) if $K_{e}=K_{e^{\prime}}$. Namely,
if $x$ and $y$ are the other endpoints (besides $z$) of $e$ and $e^{\prime}$,
respectively, then an $x$-$y$ path taken within the shared component combines
with $e$ and $e^{\prime}$ to produce a cycle.

As for the implication $e\neq
e^{\prime}\Rightarrow\mathrm{In}(Q_{e})\cap\mathrm{In}(Q_{e^{\prime}})=\emptyset$,
note that it follows immediately from the above discussion. $\diamond$

Any subsequent use of notation $Q_{e}$ is to be understood in the context of
Claim 2. We study next the following situation: $e,e^{\prime}\in
E_{G}(z)\backslash E_{C}(z)$ are distinct edges and $Q_{e},Q_{e^{\prime}}$
have endings on the same side of $P$ in respect of $z$.

Claim 3. Let $Q^{\prime},Q^{\prime\prime}\in\mathcal{P}_{z}$ be internally
disjoint, and with their respective endings lying on the same side of $z$
along $P$. If $\bar{z}\in N_{P}(z)$ is on that side of $P$, then both
$Q^{\prime},Q^{\prime\prime}$ are $z$-$\bar{z}$ edges.

First we show that $Q^{\prime}$ and $Q^{\prime\prime}$ share the same ending.
Arguing by contradiction, suppose their respective endings, say $z^{\prime}$
and $z^{\prime\prime}$, differ. Without loss of generality, let $z^{\prime}$
be an internal vertex of the subpath $zPz^{\prime\prime}$. Denote
$C^{\prime}=zPz^{\prime}\cup Q^{\prime}$ and
$C^{\prime\prime}=zPz^{\prime\prime}\cup Q^{\prime\prime}$. Then $C\oplus
C^{\prime\prime}$ and $C^{\prime}$ constitute a forbidden cycle pair. The
obtained contradiction confirms that $Q^{\prime},Q^{\prime\prime}$ have the
same ending, say $z^{*}$.

Figure 8: A detour from $P$ that yields a forbidden cycle pair at $z$.

Next we prove that $Q^{\prime},Q^{\prime\prime}$ are actually $1$-paths. For
argument’s sake, suppose $\mathrm{In}(Q^{\prime})\neq\emptyset$. Then, as
$\mathrm{In}(Q^{\prime})\neq\\{v\\}$, the essential $3$-edge-connectedness of
$G$ guarantees that there is an edge $f\notin E(Q^{\prime})$ such that: $(1)$
it emanates from the component of $G-V(C)$ containing
$\mathrm{In}(Q^{\prime})$, and $(2)$ has its other endpoint within $V(P)$.
However, such an edge $f$ would contradict the already established feature of
shared path endings (either in regard to the large vertex $z$ or to the large
vertex $z^{*}$). Consequently, both $Q^{\prime}$ and $Q^{\prime\prime}$ are
$z$-$z^{*}$ edges.

Finally, let us show that $z^{*}\in N_{P}(z)$, that is, $z^{*}=\bar{z}$ is a
neighbor of $z$ along $P$. Once again we argue by contradiction and evoke
essential $3$-edge-connectedness. Suppose $\mathrm{In}(zPz^{*})\neq\emptyset$,
and let $H$ be the component of $G-(V(C)\backslash\mathrm{In}(zPz^{*}))$ that
includes $\mathrm{In}(zPz^{*})$. Since $|\partial(H)|\geq 3$ there exists an
edge $h\in\partial(H)\backslash E(P)$. It cannot be that $h$ has an endpoint
within $\\{z,z^{*}\\}$. Indeed, for otherwise, $h$ would contradict the
feature of shared path endings in regard to its endpoint in $\\{z,z^{*}\\}$
(see Figure 9). Thus, without loss of generality, assume $h$ meets $P$ on the
side of $z$ not including $z^{*}$. If $x$ is the endpoint of $h$ on $P$, then
there is a path $R$ that starts at $x$ along $h$ and goes through $H$ until it
reaches $P$ again, say at a vertex $y\in\mathrm{In}(zPz^{*})$.

Figure 9: A detour from $P$ along $R$ that yields a forbidden cycle pair.

Define $\bar{C}=xPy\cup R$ and $\bar{\bar{C}}=Q^{\prime}\cup
Q^{\prime\prime}$. Then $C\oplus\bar{C}$ and $\bar{\bar{C}}$ form a forbidden
cycle pair. The obtained contradiction settles the claim. $\diamond$

Since $z$ is a large vertex, we have that $|E_{G}(z)\backslash E_{C}(z)|\geq
3$. Consequently, on at least one side along $P$ the vertex $z$ is incident
with a $3^{+}$-bouquet $\mathcal{B}_{z\bar{z}}$ (see Figure 10); call it a
large bouquet. Thus, every large vertex lying on $P$ is incident with at least
one large bouquet (shared with an adjacent large vertex along $P$).
Consequently, for each $e\in E_{G}(z)\backslash E_{C}(z)$, all the paths
$Q_{e}$ have endings on the same side of $P$ with regard to $z$.

Figure 10: A large bouquet at the vertex $z$ (and at the vertex
$\overline{z}$).

Concerning the parity of their size, we distinguish between even and odd large
bouquets. In case a large vertex along $P$ is incident with two large
bouquets, then clearly one of them is even whereas the other one is odd.

Claim 4. If $z^{\prime},z^{\prime\prime}$ are adjacent large vertices along
$P$ such that $\mathcal{B}_{z^{\prime}z^{\prime\prime}}$ is an even large
bouquet of $G$, then at least one of them is incident with an odd large
bouquet as well.

Since both $d_{G}(z^{\prime}),d_{G}(z^{\prime\prime})$ are odd and
$\mathcal{B}_{z^{\prime}z^{\prime\prime}}$ is even, the sets
$E_{G}(z^{\prime})\backslash(E(P)\cup\mathcal{B}_{z^{\prime}z^{\prime\prime}})$
and
$E_{G}(z^{\prime\prime})\backslash(E(P)\cup\mathcal{B}_{z^{\prime}z^{\prime\prime}})$
are even-sized. Suppose neither of $z^{\prime},z^{\prime\prime}$ is incident
with an odd large bouquet along $P$. Then, in view of Claims 2 and 3, the sets
$E_{G}(z^{\prime})\backslash(E(P)\cup\mathcal{B}_{z^{\prime}z^{\prime\prime}})$
and
$E_{G}(z^{\prime\prime})\backslash(E(P)\cup\mathcal{B}_{z^{\prime}z^{\prime\prime}})$
are actually empty. However, this gives
$|\partial(\\{z^{\prime},z^{\prime\prime}\\})|=2$, contradicting that $G$ is
essentially $3$-edge-connected. $\diamond$

In particular, as every large vertex along $P$ is incident with at least one
large bouquet, there exists an odd large bouquet, say
$\mathcal{B}_{z\overline{z}}$. Noting that
$\\{z,\overline{z}\\}\cap\\{u,w\\}=\emptyset$ (for otherwise every vertex from
$\\{z,\overline{z}\\}\cap\\{u,w\\}$ would have an even degree $\geq 4$), we
may assume that $u,z,\overline{z},w$ appear in this relative order along $P$.
We shall gradually construct a triplet
$(H,\mathcal{Z},\overline{\mathcal{Z}})$ whose entries are a subgraph
$H\subseteq G$ and two subsets $\mathcal{Z}\subseteq
V(uPz),\overline{\mathcal{Z}}\subseteq V(\overline{z}Pw)$ so that
$\mathcal{B}_{z\overline{z}}\subseteq E(H)$ and the union
$\mathcal{Z}\cup\overline{\mathcal{Z}}$ comprises all $3^{+}$-vertices of $H$.
To do so, we initially plug in values $H=C+\mathcal{B}_{z\overline{z}}$,
$\mathcal{Z}=\\{z\\}$ and $\overline{\mathcal{Z}}=\\{\overline{z}\\}$, and
then suitably augment each entry. Once completed, the key features of the
subgraph $H$ will be:

  * •

each of its $3^{+}$-vertices has equal degrees in $H$ and $G$;

  * •

it admits an odd edge-coloring $\varphi_{H}$ with color set $\\{1,2,3\\}$ such
that the color $3$ is used only on an edge of $\mathcal{B}_{z\overline{z}}$.

These features of $H$ would immediately imply that the graph $G$ is odd
$3$-edge-colorable: namely, as every non-isolated vertex of $\hat{H}$ has an
odd degree in $\hat{H}$ and degree $2$ in $H$, simply extend the above
mentioned $\varphi_{H}$ from $E(H)$ to $E(G)$ by coloring $E(G)\backslash
E(H)$ with $3$; as $z,\overline{z}$ are isolated in $\hat{H}$, the described
extension is an odd $3$-edge-coloring of $G$.

Let us explain the construction of the triplet
$(H,\mathcal{Z},\overline{\mathcal{Z}})$. We augment the initial value
$H=C+\mathcal{B}_{z\overline{z}}$ along $P$ on each ‘side’ of
$\mathcal{B}_{z\overline{z}}$. Since the augmentation process is analogous on
both sides, it will only be described for the side of $z$, noting that this
half only gives the final value of $\mathcal{Z}$ whereas the final value of
$H$ is reached once the process is repeated on the side of $\overline{z}$ as
well.

The set $\mathcal{Z}$ is being perceived as linearly ordered (i.e., an ever
increasing stack) and comprised of the vertices from $V(H)\cap V(uPz)$ for
which $d_{H}$ exceeds $d_{C}$. Initially, the head of this stack is the vertex
$z$. At each stage, the value $d_{G}-d_{H}$ is scanned for the vertex $x$ at
the head of $\mathcal{Z}$. The algorithm terminates when this value becomes
zero at the head. Meanwhile $d_{H}(x)<d_{G}(x)$, and we act as follows:

  * $(i)$

the subgraph $H$ is augmented with $\bigcup\\{Q_{e}:e\in E_{G}(x)\backslash
E_{H}(x)\\}$, where one path $Q_{e}$ is added for each edge $e$);

  * $(ii)$

the shared ending of those $Q_{e}$’s is appended to $\mathcal{Z}$ as the new
head of the stack.

To slightly clarify this two-fold action, with its part $(i)$ the difference
$d_{G}-d_{H}$ becomes equal to $0$ at the old head, but with its part $(ii)$
the focus has already switched to the new head. We observe in passing that the
important fact of the mentioned $Q_{e}$’s sharing the same ending is
guaranteed by Claims $2$ and $3$. Moreover, depending on the value of
$d_{G}(x)-d_{H}(x)$, there are two possibilities for $\\{Q_{e}:e\in
E_{G}(x)\backslash E_{H}(x)\\}$, cf. steps 5–11 in the algorithm below. Also
note that steps 6 and 7 of this algorithm are justified by Claim $3$. Namely,
in step 6 it is assumed that $d_{G}(x)-d_{H}(x)>1$, hence Claim $3$ assures
there is a large bouquet towards $u$ incident with $x$ and its neighbor (see
Figure 11). As for steps 9 and 10, there it is assumed that
$d_{G}(x)-d_{H}(x)=1$, implying $E_{G}(z)\backslash E_{H}(z)$ is a singleton.
The outcome $(H,\mathcal{Z})$ is not uniquely determined because there is a
possible freedom of choice for $Q_{e}\in\mathcal{P}_{x}$ in step 9.

Augmentation algorithm (on the side of $z$)

INPUT: a cycle $C$ through $v$ and an odd large bouquet
$\mathcal{B}_{z\overline{z}}$

OUTPUT: a subgraph $H\subseteq G$ and a queue $\mathcal{Z}\subseteq V(uPz)$

  1. 1.

set $t=0$, $\mathcal{Z}=\\{z\\}$ and $H=C+\mathcal{B}_{z\overline{z}}$

  2. 2.

consider the head $x$ of $\mathcal{Z}$

  3. 3.

while $d_{H}(x)<d_{G}(x)$ do

  4. 4.

increment $t$ by $1$

  5. 5.

if $d_{G}(x)-d_{H}(x)>1$ then

  6. 6.

augment $H$ with the large bouquet $\mathcal{B}$ incident with $x$

  7. 7.

append the other endpoint of $\mathcal{B}$ to the queue $\mathcal{Z}$

  8. 8.

else

  9. 9.

augment $H$ with a path $Q_{e}\in\mathcal{P}_{x}$, where $e$ is the unique
edge in $E_{G}(z)\backslash E_{H}(z)$

  10. 10.

append the ending of the path $Q_{e}$ to the queue $\mathcal{Z}$

  11. 11.

end if

  12. 12.

end while

  13. 13.

return $H$ and $\mathcal{Z}$

Figure 11: The augmentation of $H$ and $\mathcal{Z}$ described in steps 6 and
7. The edges currently forming $E(H)\cap E(P)$ are depicted heavier, and the
vertices currently forming the stack $\mathcal{Z}$ are depicted as squares.
The several light edges in the upper drawing complete the existing large
bouquet (towards $u$) incident with the old head $x$ (and also with the new
one).

For the second run of the algorithm, replace every mention of $\mathcal{Z}$
with $\overline{\mathcal{Z}}$, initially defined as
$\overline{\mathcal{Z}}=\\{\overline{z}\\}$. Moreover, on this occasion use as
a starting value of $H$ the output value from the first run. Observe that, as
promised, the eventually obtained subgraph $H\subseteq G$ is such that every
vertex from $\mathcal{Z}\cup\overline{\mathcal{Z}}$ is isolated in the edge-
complement $\hat{H}$, and every other vertex of $H$ has degree $2$. Moreover,
the set $E(H)$ has the following important property: it contains at least one
odd large bouquet (surely $\mathcal{B}_{z\overline{z}}$ is such), and if all
large bouquets are to be removed from $H$, then the remaining cycles would be
even and disjoint. In addition, each of them would intersect with either
$\mathcal{Z}$ or $\overline{\mathcal{Z}}$ and it would do so in precisely two
consecutive vertices (of the corresponding stack), see Figure 12.

Figure 12: A sketch of the final outcome for
$(H,\mathcal{Z},\overline{\mathcal{Z}})$. All vertices from
$\mathcal{Z}\cup\overline{\mathcal{Z}}$ are depicted as squares, and
$|\mathcal{Z}|=|\overline{\mathcal{Z}}|=4$. There are five large bouquets
within $H$, three of which are odd. If all large bouquets are removed, only
two disjoint cycles would remain: one of length $8$ and one of length $10$;
the former shares couple of vertices with $\mathcal{Z}$, and the latter with
$\overline{\mathcal{Z}}$.

The above features of $E(H)$ enable us to construct the desired $\varphi_{H}$.
We start by coloring $E(C)$ with color set $\\{1,2,3\\}$ as follows: use $1$
for $uv$, $2$ for $vw$, and $3$ for $z\overline{z}$ (this is the edge in
$\mathcal{B}_{z\overline{z}}\cap E(P)$); then by simultaneously traversing $P$
from both endpoints, alternate between the colors $1$ and $2$ at each vertex
outside $\mathcal{Z}\cup\overline{\mathcal{Z}}$, and repeat the same color
($1$ or $2$) at each vertex from
$(\mathcal{Z}\cup\overline{\mathcal{Z}})\backslash\\{z,\overline{z}\\}$. Once
the described coloring of $E(C)$ is completed, next we color each large
bouquet of $H-\mathcal{B}_{z\overline{z}}$ monochromatically, i.e. use for the
whole of it the color already appearing on its edge within $P$. As for
$\mathcal{B}_{z\overline{z}}$, use the color $1$ on an odd number of its
remaining uncolored edges, and use the color $2$ for the rest of it. At this
point, the uncolored part of $E(H)$ consists of those $Q_{e}$’s included in
$H$ which are of length $\ell(Q_{e})\geq 2$. To each of them apply a proper
edge-coloring with color set $\\{1,2\\}$ so that at every endpoint the
coloring of $E(H)$ remains locally monochromatic. Such coloring is clearly
possible since every such $Q_{e}$ forms an even cycle with a suitable portion
of $P$, and the endpoints of $Q_{e}$ are consecutive vertices of either
$\mathcal{Z}$ or $\overline{\mathcal{Z}}$. ∎

The freshly proved Lemma 4.2, combined with Propositions 3.6 and 3.7, settles
the implication $(ii)\Rightarrow(i)$. Indeed, arguing by contradiction, let
$G$ be a $2$-connected member of $\mathcal{S}_{4}\backslash\mathcal{F}$ that
minimizes the order $n(G)$. Taking into account Propositions 3.6 and 3.7, it
is implied by part $(c)$ of the construction of $\mathcal{F}$ that $G$ is
essentially $3$-edge-connected. Consequently, by Lemma 4.2, $\Delta(G)=3$ or
$n(G)=3$. However, if the former holds then Proposition 3.6 assures that
$G\in\mathcal{F}$ (due to part $(b)$ of the construction). Similarly, if
$n(G)=3$ then its assumed $2$-connectedness and the fact that
$G\in\mathcal{S}$ imply it is a Shannon triangle of type $(2,2,1)$ with
$\delta(G)=2$. Hence $G\in\mathcal{F}$ (due to part $(a)$ of the
construction). The obtained contradiction settles that $(ii)\Rightarrow(i)$.
This completes the proof of Theorem 4.1.

Finally, we arrive at our main result. To formulate it succinctly, the
standard notion of a ‘block-cutpoint graph’ proves useful. Recall that for a
given connected graph $G$, its block-cutpoint graph is a simple bipartite
graph in which one partite set consists of the cut-vertices of $G$ and the
other has a vertex $b_{i}$ for each block $B_{i}$ of $G$; we include $vb_{i}$
as an edge of the block-cutpoint graph if and only if $v\in B_{i}$. Our
findings can be summarized as follows.

######  Theorem 4.3.

Let $G\in\mathcal{S}$ be a connected graph. If $(\mathcal{B},\mathcal{V})$ is
the bipartition of the block-cutpoint graph of $G$, where $\mathcal{B}$ is the
set of blocks and $\mathcal{V}$ the set of cut-vertices, then the following
holds:

$\chi^{\prime}_{o}(G)=\begin{cases}1&\text{\quad if \,}G\text{ is odd}\,;\\\
2&\text{\quad if \,}G\text{ has 2-vertices, with an even number of them on
each cycle}\,;\\\ 4&\text{\quad if \,}\mathcal{B}\subseteq\mathcal{F}\text{
and for every }v\in\mathcal{V}\text{ there is a unique }B\in\mathcal{B}\text{
with odd }d_{B}(v)\,;\\\ 3&\text{\quad otherwise}\,.\end{cases}$

###### Proof.

Straightforward from Corollary 3.4, Proposition 3.5 and Theorem 4.1. ∎

##  5 Further work

It is implied by Theorem 4.3 that the problem of determining the odd chromatic
index of a subdivision of an odd graph is solvable in polynomial time. In view
of Theorems 1.3 and 1.5, the complexity questions concerning the value of the
odd chromatic index of general graphs amount to deciding on their odd
$3$-edge-colorability. As already mentioned in Section 1.2, this question is
still open.

We propose the study of a related set of questions arising from the following
line of reasoning. The class $\mathcal{S}$ can be captured by using the notion
of maximum even degree, defined as follows. Let $\Delta_{\mathrm{even}}(G)$
denote the maximum even value among the vertex degrees of $G$. Thus
$\mathcal{S}=\\{G:G\text{ is a graph and }\Delta_{\mathrm{even}}(G)\leq 2\\}$,
and Theorem 4.3 tells that the problem of determining $\chi^{\prime}_{o}(G)$
whenever $\Delta_{\mathrm{even}}(G)\leq 2$ can be efficiently solved. For
every $k=1,2,\ldots,$ introduce notation $\mathcal{S}^{(k)}=\\{G:G\text{ is a
graph and }\Delta_{\mathrm{even}}(G)\leq 2k\\}$. So, by ignoring isolated
vertices, $\mathcal{S}^{(0)}=\mathcal{O}$; and obviously
$\mathcal{S}^{(1)}=\mathcal{S}$. We find the next question interesting.

######  Question 5.1.

Is the decision problem whether a graph $G\in\mathcal{S}^{(2)}$ has
$\chi^{\prime}_{o}(G)\leq 3$ solvable in polynomial time?

A positive answer for Question 5.1 would open the door to consider the
following more general problem.

######  Question 5.2.

Given a positive integer $k$, is the decision problem whether a graph
$G\in\mathcal{S}^{(k)}$ has $\chi^{\prime}_{o}(G)\leq 3$ solvable in
polynomial time?

Another possible field of study is to consider $\mathcal{S}^{(k)}$-edge-
colorability of graphs for a fixed positive integer $k$ (instead of odd edge-
colorability); that is, define a new type of edge-coloring by requiring that
each color class is a member of $\mathcal{S}^{(k)}$ (rather than of
$\mathcal{O}=\mathcal{S}^{(0)}$). Say the corresponding index (representing
the minimum sufficient number of colors) is
$\chi^{\prime}_{\mathcal{S}^{(k)}}(G)$. For example, it is readily observed
that $\chi^{\prime}_{\mathcal{S}}(W_{4})=2$ as opposed to
$\chi^{\prime}_{o}(W_{4})=4$. Similarly, if $G$ is a Shannon triangle of type
$(2,2,2)$, then $\chi^{\prime}_{\mathcal{S}}(G)\leq 3$ in contrast to
$\chi^{\prime}_{o}(G)=6$. Note that there are graphs that require at least
four colors for an $\mathcal{S}$-edge-coloring. Namely, every Shannon triangle
$G$ of type $(2,2,1)$ and multiplicity at least $3$ has
$\chi^{\prime}_{\mathcal{S}}(G)=4$ (see Figure 13).

Figure 13: A Shannon triangle of type $(2,2,1)$ that requires four colors for
an $\mathcal{S}$-edge-coloring. Its bouquets are of size $4,4$ and $3$,
respectively.

We are tempted to end our discussion here with the following.

######  Conjecture 5.3.

If $G$ is a connected loopless graph that is not a Shannon triangle of type
$(2,2,1)$ and multiplicity $\geq 3$, then $\chi^{\prime}_{\mathcal{S}}(G)\leq
3$.

Acknowledgements. This work is partially supported by ARRS Program P1-0383 and
ARRS Project J1-1692.

## References

  * [1] R. Atanasov, M. Petruševski, R. Škrekovski, Odd edge-colorability of subcubic graphs, Ars Math. Contemp. $\mathbf{10}$ (2016), 359–370.
  * [2] J. A. Bondy, U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, Springer, New York $\mathbf{244}$ (2008).
  * [3] M. Kano, G. Y. Katona, K. Varga, Decomposition of a graph into two disjoint odd subgraphs, Graphs and Combin. $\mathbf{34}(6)$ (2018) 1581–1588.
  * [4] B. Lužar, M. Petruševski, R. Škrekovski, Odd edge coloring of graphs, Ars Math. Contemp. $\mathbf{9}$ (2015) 277–287.
  * [5] T. Matrai, Covering the edges of a graph by three odd subgraphs, J. Graph Theory $\mathbf{53}$ (2006) 75–82.
  * [6] M. Petruševski, Odd $4$-edge-colorability of graphs, J. Graph Theory $\mathbf{87}(4)$ (2018) 460–474.
  * [7] M. Petruševski, R. Škrekovski, Odd decompositions and coverings of graphs, European J. Combin. $\mathbf{91}$ (2021) 103225.
  * [8] L. Pyber, Covering the edges of a graph by…, Sets, Graphs and Numbers, Colloquia Mathematica Societatis János Bolyai $\mathbf{60}$ (1991), 583–610.
  * [9] A. Schrijver, Combinatorial optimization. Polyhedra and efficiency. Vol. A, Algorithms and Combinatorics, Springer-Verlag, Berlin (2003).