ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P3.03 / 403–413
https://doi.org/10.26493/1855-3974.2638.d0b
(Also available at http://amc-journal.eu)
On the chromatic index
of generalized truncations
Brian Alspach * , Aditya Joshi †
School of Mathematical and Physical Sciences, University of Newcastle, Callaghan,
NSW 2308, Australia
Received 21 May 2021, accepted 17 March 2022, published online 24 June 2022
Abstract
We examine the chromatic index of generalized truncations of graphs and multigraphs.
The insertion graphs considered are complete graphs, cycles, regular graphs and forests.
Keywords: generalized truncation, chromatic index
Math. Subj. Class. (2020): 05C15
1 Introduction
A broad definition of generalized truncations of graphs was introduced in [1]. We give
this definition now for completeness, but first a brief word about terminology is in order.
The term multigraph is used if multiple edges are allowed. Thus, a graph does not have
multiple edges. We use V (X) to denote the set of vertices of a multigraph X and E(X) to
denote the set of edges. The order of X is |V (X)| and the size of X is |E(X)|. Finally,
the valency of a vertex u, denoted val(u), is the number of edges incident with u. The term
k-valent multigraph is used for regular multigraphs of valency k. Throughout the paper,
∆(X) denotes the maximum valency of the multigraph X and ∆ often is used when the
graph X involved is apparent.
Given a multigraph X , a generalized truncation of X is obtained as follows via a two-
step operation. The first step is the excision step. Let M denote an auxiliary matching (no
two edges have a vertex in common) of size |E(X)|. Let F : E(X) → M be a bijective
function and for [u, v] ∈ E(X), label the ends of the edge F ([u, v]) with u and v. Let
*Corresponding author.
†Author wishes to thank the University of Newcastle for support from a 2020 - 2021 Summer Research Schol-
arship during which time this research was begun.
E-mail addresses: brian.alspach@newcastle.edu.au (Brian Alspach), aditya.joshi@uon.edu.au (Aditya
Joshi)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
404 Ars Math. Contemp. 22 (2022) #P3.03 / 403–413
MF denote the vertex-labelled matching thus obtained. So MF represents the edges of X
completely disassembled.
The second step is the assemblage step. For each v ∈ V (X), the set of vertices of
MF labelled with v is called the cluster at v and is denoted cl(v). Insert an arbitrary graph
on cl(v). The inserted graph on cl(v) is called the constituent graph at v and is denoted
con(v). The resulting graph
MF ∪v∈V (X) con(v)
is a generalized truncation of X . We usually think of the labels on the vertices of MF as
being removed following the assemblage stage, but there are many times when the labels
are useful in the exposition. We use TR(X) to denote a generalized truncation of the
multigraph X .
Truncations arise via action involving the edges incident with a vertex. Consequently,
isolated vertices are useless and we make the important convention that the multigraphs
from which we are forming generalized truncations do not have isolated vertices. This
will not be mentioned in the subsequent material, but is required for the validity of a few
statements.
Recall that a proper edge coloring of a multigraph X is a coloring of the edges so that
adjacent edges do not have the same color. The chromatic index of X , denoted χ′(X), is
the fewest number of colors for which a proper edge coloring exists. We now state Vizing’s
well-known theorem [4] which plays a fundamental role in studying chromatic index.
Theorem 1.1. If X is a graph, then its chromatic index is either ∆(X) or ∆(X) + 1.
The preceding theorem leads to a classification of graphs as follows. A graph is class I if
its chromatic index is equal to its maximum valency ∆ and is class II otherwise. There is a
generalization for multigraphs and to ease subsequent exposition we shall say a multigraph
is class I if its chromatic index equals its maximum valency.
The following result was proved in [1]. A generalized truncation TR(X) is called
complete when every constituent is a complete subgraph.
Theorem 1.2. If X is a class I graph, then its complete truncation also is class I. If X is a
class II graph and its maximum valency is even, then its complete truncation is class I.
The purpose of this paper is to extend the preceding result and explore edge colorings
of generalized truncations in more detail.
2 Some useful results
In the following material we shall be considering the relationship between multigraphs and
their generalized truncations that are class I. Doing so requires the use of some well-known
edge coloring results which we now give for completeness.
Let σ be a permutation of the vertex set of the complete graph Kn of order n. If Y is a
subgraph of Kn, then σ(Y ) denotes the subgraph of Kn whose edge set is
{[σ(u), σ(v)] : [u, v] ∈ E(Y )}. Let n be even and ρ be the permutation defined by
ρ = (u0)(u1 u2 u3 · · · un−1). So ρ fixes one vertex and cyclically rotates the remaining
vertices. Let Y be the perfect matching of Kn consisting of the edges
[u0, u1], [u2, un−1], [u3, un−2], . . . , [un/2, u(n+2)/2].
B. Alspach and A. Joshi: On the chromatic index of generalized truncations 405
t t
t t
t tttu0
u1
u2
u3
u4u5
u6
u7
Figure 1: Canonical edge coloring.
We then obtain a proper edge coloring of Kn by letting the color classes be
Y, ρ(Y ), ρ2(Y ), . . . , ρn−2(Y ). We call this proper edge coloring the canonical edge col-
oring of Kn. Figure 1 shows Y for K8. We obtain a proper edge coloring of Kn with n
colors, n odd, by starting with the canonical edge coloring of Kn+1 and then removing the
central vertex u0 and the edges incident with it. Note that each vertex is missing an edge
of one color and the set of missing colors has cardinality n. This fact is true for any proper
edge coloring of Kn, n odd.
Because we use the preceding canonical edge coloring for both even and odd orders, we
describe it by referring to the edge of length 1 as the anchor. When n is even, the anchor
is the edge [un/2, u1+n/2]. When n is odd, the anchor is the edge [u(n+1)/2, u(n+3)/2]. To
obtain proper edge colorings of complete graphs, we cyclically rotate the canonical edge
coloring which, of course, cyclically rotates the anchor. So we may determine a color class
by specifying the anchor.
Lemma 2.1. Every proper edge coloring of Kn with n colors, n odd, has the property that
there is one color missing on the edges incident with a given vertex, and the set of missing
colors at the vertices has cardinality n.
Proof. There are at most (n− 1)/2 edges of a fixed color in a proper edge coloring of Kn
because n is odd. Thus, there is no proper edge coloring using just n − 1 colors because
(n − 1)2/2 <
(
n
2
)
. There is a proper edge coloring using n colors by Vizing’s Theorem.
Hence, each color class contains precisely (n − 1)/2 edges from which the conclusion
follows.
We use a result about list chromatic index so we discuss it briefly here and present the
result. Given a graph X and for each edge [u, v] a list L[u,v] of colors we may use for the
edge [u, v], a proper list edge coloring is a proper edge coloring of X so that the color on
each edge [u, v] belongs to L[u,v]. The list chromatic index of X is the smallest N such
that if every list L[u,v] has cardinality N , then X admits a proper list edge coloring. We
denote this value by χ′L(X). The following important result was proved by Häggkvist and
Jansen in [2].
Theorem 2.2. The complete graph Kn satisfies χ′L(Kn) ≤ n.
406 Ars Math. Contemp. 22 (2022) #P3.03 / 403–413
3 A general result
We are interested in determining which generalized truncations of a given multigraph X
are class I. Theorem 3.1 below provides a general answer and in subsequent sections we use
the theorem to describe class I generalized truncations of specific types. Some definitions
and notation are required before stating the theorem.
Given a generalized truncation TR(X), for convenience we call the subgraph induced
by the edges of con(v) together with the edges of MF incident with the vertices of con(v)
the sun centered at con(v). Given that con(v) is regular of valency d− 1, when is the sun
centered at con(v) class I? If it is class I, then there is a proper edge coloring using d colors.
We use a vector of length d to describe the number of edges of MF of the various colors in
the sun centered at con(v).
Given a vertex v ∈ X of valency r, we say that a vector (x1, x2, . . . , xd) is admissible
if
∑
i xi = r, the edges of MF are colored according to the vector, that is, xi edges have
color i, and there is a (d− 1)-regular graph on con(v) such that the sun centered at con(v)
is class I. We say the vector is totally inadmissible if there is no (d − 1)-regular graph on
con(v) which makes the sun class I.
Theorem 3.1. If (x1, x2, . . . , xd) satisfies x1+x2+· · ·+xd = r ≥ d, then (x1, x2, . . . , xd)
is admissible if and only if all of x1, x2, . . . , xd and r have the same parity and when the
parity is odd, d also is odd. Otherwise, the vector is totally inadmissible.
Proof. Suppose that val(v) = r in a multigraph X and that there is a class I sun centered
at con(v) which is regular of valency d. Let (x1, x2, . . . , xd) be the vector for the colors
of MF . For an arbitrary color c(i), if the number of edges of color c(i) in con(v) is
k, then the number of edges of color c(i) in MF must be r − 2k. It then follows that
x1, x2, . . . , xd and r all have the same parity. Moreover, if r is odd, then the graph con(v)
is regular of valency d− 1 and order r which implies that d− 1 is even. This completes the
necessity.
Now suppose that all coordinates of (x1, x2, . . . , xd) are odd, r is odd and x1 + x2 +
· · ·+ xd = r. In this case we also have that d is odd. Label the r vertices of the constituent
u1, u2, u3, . . . , ur so that the first x1 vertices are incident with the x1 edges of MF of color
c(1), the next x2 vertices are incident with the x2 edges of MF of color c(2) and continue
in this way. Also carry out subscript arithmetic modulo r on the residues 1, 2, 3, . . . , r.
Consider the xi successive vertices incident with the xi edges of MF of color c(i).
Because xi is odd, there is a central edge of MF of color c(i) and let it be incident with
ua. Letting α = (xi − 1)/2, the vertices incident with edges of MF of color c(i) are
ua−α, ua−α+1, . . . , ua, ua+1, . . . , ua+α.
Consider the canonical color class whose anchor is [ua+(r−1)/2, ua+(r+1)/2]. Color
the edges of this class with color c(i) starting with the anchor and stopping with the edge
[ua−α−1, ua+α+1]. This yields edges colored with c(i) so that each vertex of the con-
stituent is incident with one edge of color c(i). After doing this for each of the d colors, the
resulting sun centered at the constituent is class I and the constituent is regular of valency
d− 1.
This leaves us with the case that all the coordinates of (x1, x2, . . . , xd) are even so that
their sum r also is even. There is no restriction on the parity of d in this case. Also note
that xi = 0 is possible for various values of i. Without loss of generality, let x1, x2, . . . , xa
be the non-zero entries of the vector.
B. Alspach and A. Joshi: On the chromatic index of generalized truncations 407
We label the vertices of the constituent a little differently using the canonical edge
coloring of Figure 1 as a template. The central vertex is labelled u0 and the others are
labelled u1, u2, . . . , ur−1.
Let the x1 edges of MF of color c(1) be incident with u0, u1, . . . , ux1−1. Let the
remaining edges of MF be incident with vertices of the constituent as in the preceding
case, that is, edges of the same color are incident with successively labelled vertices.
The edges of color c(1) have a different form than the other colored edges making
the completion of the coloring a little different for them. Vertices u1, u2, . . . , ux1−1 are
incident with edges of MF of color c(1). This corresponds to the color class with anchor
[u(x1+r−4)/2, u(x1+r−2)/2]. So color the edges of that class with color c(1) starting with
the anchor until finishing with [ur−1, ux1 ]. Every vertex of the constituent now is incident
with an edge of color c(1).
For all the other colors c(j), 1 < j ≤ a, there are an even number of successive
vertices, say uj , uj+1, . . . , uj+t, incident with edges of MF of color c(j). Then the edge
[uj+(t−1)/2, uj+(t+1)/2] is the anchor of a color class. So complete the coloring of the
edges of this color class starting with [uj−1, uj+t+1] moving away from the anchor. For
xi = 0, simply include an entire color class from the canonical coloring scheme using an
unused anchor.
Doing the preceding yields a class I coloring of the sun centered at the constituent so
that the constituent graph is regular of valency d− 1 and completes the proof.
We now obtain three corollaries from Theorem 3.1, but first require a couple of defini-
tions. An edge coloring of a multigraph X is said to be parity-balanced if for each vertex
v of X , the parity of the number of edges of each color incident with v is the same as the
parity of val(v). A regular truncation is a generalized truncation for which every vertex
has the same valency. A generalized truncation is said to be semiregular if each sun cen-
tered at a constituent con(v) is class I and the subgraph con(v) is regular. The distinction
between a semiregular truncation and a regular truncation is that valencies of regularity for
a semiregular truncation may differ over the constituents. Note that the source multigraph
need not be regular in order to have a regular truncation.
Corollary 3.2. Let every entry of the feasible vector (x1, x2, . . . , xd) be even and x1 +
x2 + · · · + xd = r. If d′ is the number of non-zero entries of the vector, then there are
class I suns centered at the appropriate constituent such that the constituents are regular
of every valency from d′ through r − 1.
Proof. This result follows from the proof of Theorem 3.1 rather than the statement. Be-
cause the number of colors on edges of MF is d′, the scheme used in the proof of Theorem
3.1 introduces no new colors so that the valency of regularity is d′. Because r is even, we
may add canonical coloring classes one at a time until reaching Kr. This completes the
proof.
Corollary 3.3. A multigraph X has a class I semiregular truncation if and only if it has a
parity-balanced edge coloring.
Proof. If X has a parity-balanced edge coloring, it follows immediately from Theorem 3.1
that it has a semiregular truncation. On the other hand, if X has a semiregular truncation,
then performing the standard contraction and retention of the colors on the edges of MF
produces a parity-balanced edge coloring of X .
408 Ars Math. Contemp. 22 (2022) #P3.03 / 403–413
Corollary 3.4. A multigraph X has a class I regular truncation of valency d if and only if
it has a parity-balanced coloring and one of the following conditions holds:
(i) When d is odd, every vertex of odd valency has precisely d colors on its incident
edges, and every vertex of even valency has valency at least d + 1 and at most d
colors on its incident edges ; or
(ii) When d is even, every vertex of X has even valency at least d.
Proof. Let X be a mutigraph and suppose it has a generalized truncation Y which is regular
of valency d. Consider the case that d is even. This means that a constituent con(v) is
regular of valency d − 1 and the latter is odd. Thus, the constituent has even order. This
implies that every vertex of X has even valency. Clearly every valency is at least d.
When d is odd, each constituent must itself be regular of valency d− 1. Because d− 1
is even, there is no restriction on the order N of the constituent other than it must be at
least d. If N is odd, then for each of the d distinct colors, there must be at least one edge
of that color belonging to the edges of MF incident with vertices of the constituent. So
the corresponding vertex of X is incident with edges of precisely d different colors. When
N is even there is no restriction on the number of colors on edges of MF incident with
vertices of the constituent other than it is at most d.
For the other direction, when d is even, every constituent has even order and by Corol-
lary 3.2 it is easy to obtain regular valency of d− 1 on the constituent. When d is odd, the
result follows from Theorem 3.1.
4 Complete truncations
Let X be a multigraph with maximum valency ∆. If ∆ is odd and X has an edge coloring
with ∆ colors such that the edges incident with every vertex of valency ∆ have distinct
colors, then we say that X is edge-feasible. The next result characterizes graphs whose
complete truncations are class I. Of course, a complete truncation is a semi-regular trunca-
tion.
Theorem 4.1. The complete truncation of a multigraph X is class I if and only if either
the maximum valency ∆ of X is even, or ∆ is odd and X is edge-feasible.
Proof. This theorem is an improvement on Theorem 1.2 as the latter does not include
multigraphs as part of the hypotheses. Because a complete truncation is a semiregular
truncation, Corollary 3.3 implies that the coloring of the edges in MF must correspond to
a parity-balanced coloring of X . When ∆ is even, coloring all the edges of MF with a
single color corresponds to a parity-balanced coloring of X . Any constituent of order ∆
can be properly edge-colored with ∆ − 1 colors because ∆ is even. Any constituent of
order less than ∆ can be properly edge-colored with at most ∆ − 1 colors. Hence, the
complete truncation of X is class I.
For the remainder of the proof we assume that ∆ is odd. First suppose that the complete
truncation TR(X) is class I. If u ∈ V (X) has valency ∆, then con(u) = K∆ the complete
graph of order ∆. We conclude that the edges of MF incident with con(u) all have different
colors by Lemma 2.1. So if we contract each constituent to a single vertex, delete all the
loops formed and keep the colors of the edges of MF , we obtain an edge coloring of X .
Clearly, all the edges incident to any vertex of valency ∆ in X have distinct colors. Thus,
X is edge-feasible.
B. Alspach and A. Joshi: On the chromatic index of generalized truncations 409
Now let X be edge-feasible and choose an edge coloring of X which is edge-feasible.
Let TR(X) be the complete truncation of X . Color the edges of MF with the same color
they had in the edge coloring of X . These are the edges between the constituents all of
which are complete subgraphs. At this point we have used ∆ colors. It suffices to show
that we can color the edges of the constituents without introducing any new colors so that
the resulting edge coloring of TR(X) is proper.
Any constituent con(u) of order ∆ corresponds to a vertex u of X of valency ∆. This
implies that the edges of MF incident with the vertices of con(u) all have distinct colors
because the coloring of X was edge-feasible. From Lemma 2.1 it is clear that we may color
the edges of con(u) with ∆ colors so that the missing color at each vertex is the color of
the edge of MF at the vertex. This coloring of the edges does not violate the definition of
a proper edge coloring.
Now consider any constituent con(u) of order r ≤ ∆−2. Because each edge of con(u)
has one edge of MF at each of its end vertices, the number of possible colors for the edge
that do not violate the proper edge coloring condition is ∆ − 2. So each edge has a list
of ∆− 2 possible colors, and Theorem 2.2 implies that we may color the edges of con(u)
without violating the proper edge coloring condition because r ≤ ∆− 2.
This leaves us with the case that con(u) has order ∆−1 and this is the most complicated
case. The first observation we make is that the coloring pattern of the edges of MF incident
with the vertices of con(u) can vary all the way from having ∆ − 1 distinct colors to
every color being the same. So we introduce a sequence describing the color pattern. Let
(s1, s2, . . . , st) satisfy s1 ≤ s2 ≤ · · · ≤ st and s1 + s2 + · · ·+ st = ∆− 1. The sequence
means there are t distinct colors on the edges of MF incident with vertices of con(u) and
si such edges have the same color c(i) for i = 1, 2, . . . , t.
We need to show that no matter what the color sequence is we may color the edges of
con(u) so that the sun centered at con(u) is properly edge colored with ∆ colors. As a first
step, label the vertices of con(u) with v0, v1, . . . , va, where a = ∆ − 2. Let the vertices
v1, v2, . . . , vs1 be incident with the s1 edges of MF of color c(1). Let the next s2 vertices
be incident with the s2 edges of MF of color c(2). Continue labelling the vertices in the
obvious manner and let the edge of MF incident with v0 have color c(t).
Carry out an initial coloring of the edges of con(u) using the canonical edge coloring
described in Section 2 with v0 acting as the fixed vertex and ρ = (v0)(v1 v2 · · · va).
The strategy now is to choose the colors for the color classes in such a way that we may
re-color some edges to obtain a proper edge coloring for the sun centered at con(u).
The first observation we make is that only ∆ − 2 colors are required for a canonical
edge coloring of con(u). So we do not use the colors c(t−1) or c(t) for the canonical edge
coloring of con(u). Hence, if t = 1 or t = 2, we already have an edge coloring of con(u)
that does not violate the conditions for a proper edge coloring. Thus, we assume that t ≥ 3.
The anchor for a color class plays an active role as follows. Suppose we require two
edges of a color class so that the two edges use four successive vertices under the cyclic
labelling of {v1, v2, . . . , va}. If the anchor is [vi, vi+1], then adding the edge [vi−1, vi+2]
from the same color class easily does the job. It is now easy to see how we may obtain
k edges from the same color class so that they cover 2k successive vertices. With this
in mind, we now describe an iterative process for determining the colors of certain color
classes.
If s1 is odd, then we color the color class for which [v(s1+1)/2, v(s1+3)/2] is the anchor
with c(1). If s1 is even, then we color the color class for which [vs1/2, v(s1+2)/2] is the
410 Ars Math. Contemp. 22 (2022) #P3.03 / 403–413
anchor with c(1). There are two points to observe about the preceding choices. When s1 is
odd, the edge from v1 to vs1+1 has color c(1) and note that the edge of MF incident with
vs1+1 has color c(2). When s1 is even, the edge from v1 to vs1 has color c(1) and vertex
vs1 is the last vertex for which the edge of MF incident with it has color c(1).
We continue in the manner suggested by the preceding paragraph, but discuss it further
to make it clearer. When si is odd and the first vertex incident with an edge of MF of color
c(i) is vd, then the anchor is the edge [vd+(si−1)/2, vd+(si+1)/2] and we color this color
class with c(i). Note that the edge [vd, vd+si ] is in this color class, but the edge of MF
incident with vd+si has color c(i+ 1).
When si is even and the first vertex incident with an edge of MF of color c(i) is vd,
then the anchor is [vd+(si−2)/2, vd+si/2] and we color this color class with c(i). In this
case, the edge from vd to vd+si−1 is colored c(i) and vd+si−1 is the last vertex incident
with an edge of MF of color c(i).
The preceding procedure is carried out for the colors c(1) through c(t − 2) at which
point it stops because colors c(t− 1) and c(t) are not used for the canonical edge coloring
of con(u). The edges of con(u) that need to be re-colored are those that are adjacent with
edges of MF having the same color. We have seen that when si is odd, there is an edge
in con(u) of color c(i) with one end vertex incident with an edge of MF of color c(i) and
the other end vertex incident with an edge of MF of color c(i + 1). So at the end vertex
incident with an edge of MF of color c(i + 1), the procedure gives another edge of color
c(i+ 1) which also needs to be re-colored.
Thus, the edges that need to be recolored are isolated and possibly paths. Luckily we
have two colors to use for the re-coloring and we arbitrarily re-color isolated edges with
either c(t− 1) or c(t), and alternately re-color the edges of the paths making certain that if
one of the paths terminates with a vertex whose incident edge from MF has color c(t− 1),
we color the edge of the path terminating there with c(t). This removes all potential color
conflicts for con(u) and completes the proof of the theorem.
Corollary 4.2. Let X be a class I graph and TR(X) a generalized truncation.
If ∆(X) = ∆(TR(X)), then TR(X) is class I.
Proof. Let TR(X) be a generalized truncation of X satisfying ∆(TR(X)) = ∆(X).
Then a proper edge coloring of TR(X) requires at least ∆ colors. We know the complete
truncation Y of X is class I by Theorem 4.1, that is, it has a proper edge coloring using
∆ colors. Remove any edges of Y not belonging to TR(X) and we are left with a proper
edge coloring of TR(X) using ∆ colors. So TR(X) is class I.
It is well known that both the Petersen graph and its complete truncation are class II
graphs. The extension to a regular multigraph is an immediate corollary of Theorem 4.1.
Corollary 4.3. A regular multigraph of odd valency is class I if and only if its complete
truncation is class I.
5 Cyclic truncations
Complete truncations have been used by various authors, and there is another generalized
truncation that has been employed frequently. Namely, the generalized truncation obtained
by letting each constituent graph be a cycle. We shall call these cyclic truncations. Probably
the best known example of this is the cube-connected cycles graph first introduced in [3].
B. Alspach and A. Joshi: On the chromatic index of generalized truncations 411
Of course, the ancient Greeks studied truncations of Platonic and Archimedian solids, and
these resulted in cyclic truncations.
When moving from a multigraph X to a generalized truncation Y , we frequently wish
Y to inherit properties of X . This can be a problem for cyclic truncations. For example,
poorly chosen cyclic truncations can play havoc with automorphisms.
We are interested in determining conditions for which a cyclic truncation is class I. Of
course, a cyclic truncation is a regular truncation so that we may use Theorem 3.1. We use
the same vector describing the numbers of colors used on the edges of MF belonging to a
sun centered at a constituent. In this case the vector has length 3 as we are looking at cyclic
truncations all of which are 3-valent. There is a new term not used before, namely, a vector
(x1, x2, x3) is universal if the sun centered at the corresponding constituent is class I for
every cycle on the vertices of the constituent.
Corollary 5.1. If (x1, x2, x3) satisfies x1 + x2 + x3 = d ≥ 3, then (x1, x2, x3) is ad-
missible if and only x1, x2, x3 and d all have the same parity. Otherwise, the vector is
totally inadmissible. Moreover, if just one of x1, x2 and x3 is non-zero, then (x1, x2, x3) is
universal when d is even.
Proof. The portion of the statement prior to the sentence about universality is simply The-
orem 3.1 restricted to d = 3. When the vector has the form (x1, 0, 0) and x1 = d is even,
this corresponds to all the edges of MF incident with the vertices of the constituent having
the same color. Clearly, no matter which even length cycle we form on the vertices of the
constituent, the resulting sun is class I.
Corollary 5.1 gives us an easy way to construct a class I cyclic truncation of a multi-
graph X based on parity conditions for the colors on the edges of MF . Thus, we need to
concentrate on coloring the edges in the source multigraph.
Corollary 5.2. If every vertex of the multigraph X has even valency, then every cyclic
truncation of X is class I.
Proof. This follows from Corollary 5.1 by coloring all edges of MF with a single color.
Corollary 5.3. If X is a regular multigraph of odd valency d > 1 and is class I, then there
are class I cyclic truncations of X .
Proof. Let X be a class I regular multigraph of odd valency d ≥ 3. Choose a proper edge
coloring of X using d colors. In forming a cyclic truncation Y of X , color the edges of
MF according to the colors c(1), c(2), . . . , c(d) the edges have in the proper edge coloring
of X . Now change the color of any edge of colors c(4), c(5), . . . , c(d) to c(3). The vector
for each constituent becomes (1, 1, d − 2) all of which are odd. We now may find a cycle
for each constituent such that the cyclic truncation is class I by Corollary 5.1.
We now give a sufficient condition for a multigraph to have a class I cyclic truncation. A
definition is required. Let X be an arbitrary multigraph and V0, V1, V2 and V3 be a partition
of V (X), where Vi contains the vertices whose valencies are congruent to i modulo 4.
Given a submultigraph Y of X , let X \ Y be the submultigraph obtained by removing the
edges of Y from X . Moreover, let V ′0 , V
′
1 , V
′
2 and V
′
3 denote the vertices of V (X) whose
valencies in X \ Y are congruent to i modulo 4. A submultigraph Y of X is called an
enabling submultigraph if it satisfies:
412 Ars Math. Contemp. 22 (2022) #P3.03 / 403–413
• if v ∈ V0, then v ∈ V ′0 ;
• if v ∈ V1, then v ∈ V ′2 ;
• if v ∈ V2, then v ∈ V ′0 ; and
• if v ∈ V3, then v ∈ V ′2 .
The preceding conditions are not as complicated as they may look at first. The first
thing to notice is that the components of X \ Y are Eulerian. Second, for many graphs
the conditions are simple. For example, if X is 3-regular, then a perfect matching is an
enabling subgraph.
Corollary 5.4. Let X be a multigraph with an enabling submultigraph Y . If every compo-
nent of X \ Y has even size, then there is a class I cyclic truncation of X .
Proof. Because each component of X\Y has even size, we may alternately color the edges
of an Euler tour of the component with two colors so that we finish with same number of
colors on the edges incident with every vertex. Doing this for each component yields a
2-coloring so that each vertex of X \ Y has the same number of colors incident with it.
If we now color all the edges of Y with a third color, it is easy to verify that the con-
ditions of Corollary 5.1 are met for X . We check one possibility for illustrative purposes.
If v ∈ V3, it belongs to V ′2 in X \ Y . Thus, the number of edges of Y incident with v is
congruent to 1 modulo 4, that is, it is incident to an odd number of edges of the third color
in X . Because it is in V ′2 , it is incident with an odd number of edges of each of the first two
colors. Thus, the vector for v has three odd components.
Proposition 5.5. If a trivalent graph X has a cut edge, then X is class II.
The proof of the preceding proposition is immediate and leads to examples such as the
following. Let X be the graph of order 10 obtained by taking two vertex-disjoint copies of
K5 and joining the two copies with a single edge from a vertex of one copy to a vertex of the
other copy. Lemma 2.1 implies that X is class I. If we take any cyclic truncation TR(X)
of X , then TR(X) is class II by Proposition 5.5 because the edge of MF connecting the
two copies still is a cut edge in TR(X).
6 Arboreal truncations
We now examine another generalized truncation. An arboreal truncation is a generalized
truncation for which every constituent graph is a forest. The following result is useful for
arboreal truncations.
Theorem 6.1. Let TR(X) be a generalized truncation of a multigraph X . If the maximum
valency of TR(X) is ∆ and every constituent of TR(X) having a vertex of valency ∆ is
class I, then TR(X) is class I.
Proof. Let con(v) have a vertex of valency ∆ in TR(X). Then the maximum valency in
the subgraph con(v) is ∆ − 1. Its edges may be properly edge-colored with ∆ − 1 colors
because it is class I. Any constituent not having a vertex of valency ∆ may have its edges
properly colored with at most ∆−1 colors because its maximum valency is ∆−2. Then the
edges of MF may be colored with a new color yielding a proper edge coloring of TR(X)
with ∆ colors. The conclusion now follows.
B. Alspach and A. Joshi: On the chromatic index of generalized truncations 413
Corollary 6.2. Every arboreal truncation of a multigraph X is class I.
Proof. This follows immediately from Theorem 6.1 because forests are class I.
ORCID iDs
Brian Alspach https://orcid.org/0000-0002-1034-3993
References
[1] B. Alspach and J. B. Connor, Some graph theoretical aspects of generalized truncations, Aus-
tralas. J. Comb. 79 (2021), 476–494, https://ajc.maths.uq.edu.au/?page=get_
volumes&volume=79.
[2] R. Häggkvist and J. Janssen, New bounds on the list-chromatic index of the complete
graph and other simple graphs, Comb. Probab. Comput. 6 (1997), 295–313, doi:10.1017/
s0963548397002927.
[3] F. P. Preparata and J. Vuillemin, The cube-connected cycles: a versatile network for parallel
computation, Comm. ACM 24 (1981), 300–309, doi:10.1145/358645.358660.
[4] V. G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz (1964), 25–30.