ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 20 (2021) 187–194
https://doi.org/10.26493/1855-3974.2435.3db
(Also available at http://amc-journal.eu)
The chromatic index of strongly regular graphs
Sebastian M. Cioabă *
Department of Mathematical Sciences, University of Delaware, United States
Krystal Guo †
Korteweg-De Vries Institute, University of Amsterdam, The Netherlands
Willem H. Haemers
Department of Econometrics and Operations Research, Tilburg University,
The Netherlands
Received 16 September 2020, accepted 20 January 2021, published online 27 October 2021
Abstract
We determine (partly by computer search) the chromatic index (edge-chromatic num-
ber) of many strongly regular graphs (SRGs), including the SRGs of degree k ≤ 18 and
their complements, the Latin square graphs and their complements, and the triangular
graphs and their complements. Moreover, using a recent result of Ferber and Jain, we
prove that an SRG of even order n, which is not the block graph of a Steiner 2-design or its
complement, has chromatic index k, when n is big enough. Except for the Petersen graph,
all investigated connected SRGs of even order have chromatic index equal to k, i.e., they
are class 1, and we conjecture that this is the case for all connected SRGs of even order.
Keywords: Strongly regular graph, chromatic index, edge coloring, 1-factorization.
Math. Subj. Class. (2020): 05C15, 05E30
1 Introduction
An edge-coloring of a graph G is a coloring of its edges such that intersecting edges have
different colors. Thus a set of edges with the same colors (called a color class) is a match-
ing. The edge-chromatic number χ′(G) (also known as the chromatic index) of G is the
*Research supported by NSF grants DMS-1600768 and CIF-1815922.
†This research was done while K. Guo was a postdoctoral fellow at Université Libre de Bruxelles, supported
by ERC Consolidator Grant 615640-ForEFront.
E-mail addresses: cioaba@udel.edu (Sebastian M. Cioabă), k.guo@uva.nl (Krystal Guo), haemers@uvt.nl
(Willem H. Haemers)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
188 Ars Math. Contemp. 20 (2021) 187–194
minimum number of colors in an edge-coloring. By Vizing’s famous theorem [24], the
chromatic index of a graph G of maximum degree ∆ is ∆ or ∆ + 1. A graph with maxi-
mum degree ∆ is called class 1 if χ′(G) = ∆ and is called class 2 if χ′(G) = ∆ + 1. It is
also known that determining whether a graph G is class 1 is an NP-complete problem [18].
If G is regular of degree k, then G is class 1 if and only if G has an edge coloring such that
each color class is a perfect matching. A perfect matching is also called a 1-factor, and a
partition of the edge set into perfect matchings is called a 1-factorization. So being regular
and class 1 is the same as having a 1-factorization (being 1-factorable), and requires that
the graph has even order.
A graph G is called a strongly regular graph (SRG) with parameters (n, k, λ, µ) if it
has n vertices, is k-regular (0 < k < n− 1), any two adjacent vertices of G have exactly λ
common neighbors and any two distinct non-adjacent vertices of G have exactly µ common
neighbors. The complement of a strongly regular graph with parameters (n, k, λ, µ) is
again strongly regular, and has parameters (n, n − k − 1, n − 2k + µ − 2, n − 2k + λ).
An SRG G is called imprimitive if G or its complement is disconnected, and primitive
otherwise. A disconnected SRG is ℓKm (ℓ,m ≥ 2), the disjoint union of ℓ cliques of
order m (indeed, µ = 0 implies that no two vertices have distance two, so every connected
component is a clique). It is well-known that Km (m ≥ 2), and hence also ℓKm, is class 1
if and only if m is even. The complement of ℓKm is a regular complete multipartite graph
which is known to be class 1 if and only if the order is even [17].
A vertex coloring of G is a coloring of the vertices of G such that adjacent vertices have
different colors. The chromatic number χ(G) of G is the minimum number of colors in a
vertex coloring. For the chromatic number there exist bounds in terms of the eigenvalues
of the adjacency matrix, which turn out to be especially useful for strongly regular graphs
(see for example [6]). These bounds imply that there exist only finitely many primitive
SRGs with a given chromatic number, and made it possible to determine all SRGs with
chromatic number at most four (see [15]). Motivated by these results, Alex Rosá asked the
third author whether eigenvalue techniques can give information on the chromatic index
of an SRG. There exist useful spectral conditions for the existence of a perfect matching
(see [5, 9]), and Brouwer and Haemers [5] have shown that every regular graph of even
order, degree k and second largest eigenvalue ϑ2 contains at least ⌊(k − ϑ2 + 1)/2⌋ edge
disjoint perfect matchings. From this it follows that every connected SRG of even order has
a perfect matching. Moreover, Cioabă and Li [10] proved that any matching of order k/4
of a primitive SRG of valency k and even order, is contained in a perfect matching. These
authors conjectured that k/4 can be replaced by ⌈k/2⌉ − 1 which would be best possible.
Unfortunately, we found no useful eigenvalue tools for determining the chromatic index.
However, the following recent result of Ferber and Jain [13] gives an asymptotic condition
for being class 1 in terms of the eigenvalues.
Theorem 1.1. There exist universal constants n0 and k0, such that the following holds. If G
is a connected k-regular graph of even order n with eigenvalues k = ϑ1 > ϑ2 ≥ · · · ≥ ϑn,
and n > n0, k > k0 and max{ϑ2,−ϑn} < k0.9, then G is class 1.
If the maximum distance in G is 2 (as is the case for a connected SRG), then n ≤
1 + k + k(k − 1) = k2 + 1. This implies that for an SRG we do not need to require
that k > k0 when we take n0 ≥ k20 + 1. Theorem 1.1 enables us to show that, except for
one family of SRGs, all connected SRGs of even order n are class 1, provided n is large
enough. In addition, we present a number of sufficient conditions for an SRG to be class 1.
S. M. Cioabă, K. Guo and W. H. Haemers: The chromatic index of strongly regular graphs 189
By computer, using SageMath [22], we verified that all primitive SRGs of even order and
degree k ≤ 18 and their complements are class 1, except for the Petersen graph, which has
parameters (10, 3, 0, 1) and edge-chromatic number 4 (see [20, 25] for example). We also
determine the chromatic index of several other primitive SRGs of even order, and all are
class 1. Therefore we believe:
Conjecture 1.2. Except for the Petersen graph, every connected SRG of even order is
class 1.
2 Sufficient conditions for being class 1
A well known conjecture (first stated by Chetwynd and Hilton [8], but attributed to Dirac)
states that every k-regular graph of even order n with k ≥ n/2 is 1-factorable. Cariolaro
and Hilton [7] proved that the conclusion holds when k ≥ 0.823n, and Csaba, Kühn, Lo,
Osthus, and Treglown [11], proved the following result.
Theorem 2.1. There exists a universal constant n0, such that if n is even, n > n0 and if
k ≥ 2⌈n/4⌉ − 1, then every k-regular graph of order n has chromatic index k.
König [19] proved that every regular bipartite graph of positive degree has a 1-factor-
ization. We need the following generalization of König’s result.
Lemma 2.2. Let G = (V,E) be a connected regular graph of even order n, and let
{V1, V2} be a partition of V such that |V1| = |V2| = n/2.
(i) If the graphs induced by V1 and V2 are 1-factorable, then so is G.
(ii) If V1 (and hence V2) is a clique or a coclique, then G is class 1.
Proof. Partition the edge set E into two classes E1 and E2, where E1 contains all edges
with both endpoints in the same vertex set V1 or V2, and the edges of E2 have one endpoint
in V1 and the other endpoint in V2.
(i): If the graphs induced by V1 and V2 are 1-factorable, then both have the same degree,
and therefore also (V,E1) is 1-factorable. By König’s theorem (V,E2) is 1-factorable,
therefore G is class 1.
(ii): If V1 is a coclique, then so is V2 and we have the theorem of König. If V1 is a
clique, then so is V2. If n/2 is even, then the result is proved in (i). If n/2 is odd, then we
choose a 1-factor F in (V,E2) (here we use that G is connected), and define E′2 = E2 \ F
and E′1 = E1 ∪ F . Then (V,E′2) is 1-factorable (or has no edges), and (V,E′1) consists of
two cliques of order n/2 and the 1-factor F . Thus F gives a bijection ϕ (say) between V1
and V2. By Vizing’s theorem the edges of both cliques can be colored with n/2 colors. We
do this coloring such that ϕ preserves colors, which means that {v, w} and {ϕ(v), ϕ(w)}
get the same color. Then for each edge {v, ϕ(v)} of F , the two sets of colored edges that
intersect at v and ϕ(v) use the same n/2 − 1 colors. So we can color {v, ϕ(v)} with the
remaining color.
There exist several SRGs that have the partition of case (i). The Gewirtz graph is the
unique SRG with parameters (56, 10, 0, 2), and admits a partition into two Coxeter graphs
(see [4]). The Coxeter graph is known to be 1-factorable (see [3]), therefore the Gewirtz
graph is class 1. The same holds for the point graph of the generalized quadrangle GQ(3, 9)
(the unique SRG(112, 30, 2, 10)), which admits a partition into two Gewirtz graphs, and for
190 Ars Math. Contemp. 20 (2021) 187–194
the Higman-Sims graph (the unique SRG(100, 22, 0, 6)), which can be partitioned into two
copies of the Hoffman-Singleton graph (the unique strongly regular graph with parameters
(50, 7, 0, 1)), which has chromatic index 7 (see Section 4).
Suppose ϑ1 ≥ ϑ2 ≥ · · · ≥ ϑn are the eigenvalues of a graph G of order n. Hoffman
(see [6, Theorem 3.6.2] for example) proved that the chromatic number of G is at least
1 − ϑ1/ϑn. A vertex coloring that meets this bound is called a Hoffman coloring. For
k-regular graphs, the color classes of a Hoffman coloring are cocliques of which the size
meets Hoffman’s coclique bound nϑn/(ϑn−k). This implies (see [6] for example) that all
the color classes have equal size, and any vertex v of G has exactly −ϑn neighbors in each
color class different from the color class of v.
Theorem 2.3. Suppose G = (V,E) is a k-regular graph with an even chromatic number
2t (say) that meets Hoffman’s bound. Then both G and its complement G are class 1, or G
is a disjoint union of cliques of odd order.
Proof. Let S1, . . . , S2t be the color classes in a Hoffman coloring of G. Since G is regular,
this implies that each Si is a coclique attaining equality in the Hoffman ratio bound, which
means that each vertex outside Si has exactly −ϑn neighbors in Si. Hence, each subgraph
induced by two distinct cocliques Si and Sj is a bipartite regular graph of valency −ϑn.
A 1-factorization of K2t corresponds to a partition E1, . . . , E2t−1 of E, such that each
(V,Ei) consists of t disjoint regular bipartite graphs of degree −ϑn = k/(2t − 1). By
König’s theorem it follows that each (V,Ei) is 1-factorable, and therefore G is class 1.
For the complement G = (V, F ) of G, a similar approach works. We can partition the
edge set F into the subsets F0, F1, . . . , F2t−1, such that for i = 1, . . . , 2t − 1 the graph
(V, Fi) is the disjoint union of t regular bipartite graphs of the same positive degree (if the
degree is 0, then G is a disjoint union of cliques). But now there is an additional graph
(V, F0) consisting of 2t disjoint cliques. We combine F0 and F1. Then (V, F0 ∪ F1) is
the disjoint union of t complements of regular incomplete bipartite graphs with the same
positive degree, and therefore has a 1-factorization by Lemma 2.2. Since (V, Fi) has a
1-factorization for i = 2, . . . , 2t− 1, it follows that G is 1-factorable.
For an SRG the color partition of a Hoffman coloring corresponds to a so-called spread
in the complement (see [16]). As a consequence of this result, it follows that any primitive
strongly regular graph with a spread with an even number of cliques, or a Hoffman coloring
with an even number of colors is class 1. Among such SRGs are the Latin square graphs.
Consider a set of t (t ≥ 0) mutually orthogonal Latin squares of order m (m ≥ 2). The
vertices of the Latin square graph are the m2 entries of the Latin squares, and two distinct
entries are adjacent if they lie in the same row, the same column, or have the same symbol
in one of the squares. If t = m− 1 we obtain the complete graph Km2 , and if t = m− 2
we have a complete multipartite graph. Otherwise the Latin square graph is a primitive
SRG with parameters (m2, (t+ 2)(m− 1),m− 2 + t(t+ 1), (t+ 1)(t+ 2)). If t = 0 we
only have the rows and columns, then the Latin square graph is better known as the Lattice
graph L(m). If m ̸= 4, the Lattice graph is determined by the parameters. The m rows of a
Latin square give a partition of the vertex set of the Latin square graph into cliques, which
is a spread. Thus we have:
Corollary 2.4. If G is a Latin square graph of even order, then both G and its complement
are 1-factorable.
S. M. Cioabă, K. Guo and W. H. Haemers: The chromatic index of strongly regular graphs 191
3 Asymptotic results
A Steiner 2-design (or 2-(m, ℓ, 1) design) consists of a point set P of cardinality m, to-
gether with a collection of subsets of P of size ℓ (ℓ ≥ 2), called blocks, such that every pair
of points from P is contained in exactly one of the blocks. The block graph of a Steiner
2-design is defined as follows. The blocks are the vertices, and two vertices are adjacent if
the blocks intersect in one point. If m = ℓ2 − ℓ + 1, the Steiner 2-design is a projective
plane, and the block graph is Km. Otherwise the block graph is an SRG with parameters
(m(m− 1)/ℓ(ℓ− 1), ℓ(m− ℓ)/(ℓ− 1), (ℓ− 1)2 + (m− 2ℓ+ 1)/(ℓ− 1), ℓ2).
Theorem 3.1. There exists an integer n0, such that every primitive strongly regular graph
of even order n > n0, which is not the block graph of a Steiner 2-design or its complement,
is class 1.
Proof. Suppose G is a primitive (n, k, λ, µ)-SRG of even order n. Then it is well-known
(see for example [6, Chapter 9]) that G has exactly three distinct eigenvalues k = ϑ1,
ϑ2 and ϑn. Moreover, the eigenvalues are nonzero integers and satisfy k + ϑ2ϑn = µ.
Assume that G nor its complement G is the block graph of a Steiner 2-design or a Latin
square graph. Using a result of Neumaier [21] (known as the claw bound), we get that
ϑ2 ≤ ϑn(ϑn + 1)(µ+ 1)/2− 1.
Another result of Neumaier [21] (the µ-bound) gives µ ≤ ϑ3n(2ϑn + 3). Combining these
inequalities, after some straightforward calculations, we obtain that ϑ2 < (−ϑn)6. Since
k + ϑ2ϑn = µ > 0, we deduce that
k6 > (−ϑ2ϑn)6 > ϑ62ϑ2 = ϑ72, so ϑ2 < k6/7.
Next we apply the same result to G, and obtain −1 − ϑn < (1 + ϑ2)6, which yields
−ϑn ≤ (2ϑ2)6 (since ϑ2 is a positive integer). Hence
k6 > (−ϑ2ϑn)6 > 2−6(−ϑn)(−ϑn)6 = 2−6(−ϑn)7, so − ϑn < (2k)6/7 < k0.9,
when k is large enough. Thus we get max{ϑ2,−ϑn} ≤ k0.9. Now we apply the result of
Ferber and Jain and conclude that G is class 1 when n is large enough.
If G is a Latin square graph of even order then by Corollary 2.4 both G and its comple-
ment G are class 1.
In many cases the complement of the block graph of a Steiner 2-design has k > n/2,
so it will have a 1-factorization by Theorem 2.1, provided n is even and large enough.
The following result follows straightforwardly from the mentioned result of Cariolaro and
Hilton [7].
Proposition 3.2. If G is the complement of the block graph of a 2-(m, ℓ, 1) design with
6ℓ2 ≤ m, then G is class 1, provided G has even order.
For every m ≥ 2 there is a unique 2-(m, 2, 1) design, and its block graph is the triangu-
lar graph T (m). It is isomorphic to the line graph of the complete graph Km, and if m ≥ 4
T (m) is an SRG with parameters (m(m− 1)/2, 2(m− 2),m− 2, 4). The triangular graph
is uniquely determined by its parameters if m ̸= 8. Alspach [1] has proved that T (m) has
192 Ars Math. Contemp. 20 (2021) 187–194
a 1-factorization if the order is even, which is the case if m ≡ 0, or 1 (mod 4). Proposi-
tion 3.2 implies that the complement of T (m) is class 1 if m ≥ 24 and the order is even.
The complement of T (5) is the Petersen graph, which is class 2. For 5 < m < 24 and
m ≡ 0, or 1 (mod 4) we found a 1-factorization in the complement of T (m) by computer
(see next section for more about the computer search). Thus we can conclude:
Theorem 3.3. For m ≡ 0, or 1 (mod 4) the triangular graph T (m) is class 1, and if
m ̸= 5 so is its complement.
If the block size equals 3, the design is better known as a Steiner triple system. The
chromatic index of the block graph of a Steiner triple system is investigated in [12]. The
paper contains several sufficient conditions for such a graph to be class 1, and the authors
conjecture that all these graphs are class 1 when the order is even. One of the results from
[12] (Theorem 2.2) can be generalized to arbitrary Steiner 2-designs. A set of m/ℓ disjoint
blocks of a 2-(m, ℓ, 1) design is called a parallel class, and a partition of the block graph
into parallel classes is a parallelism. A parallelism of a Steiner 2-design gives a Hoffman
coloring in the block graph, so we have:
Proposition 3.4. If a Steiner 2-design has a parallelism with an even number of parallel
classes, then the block graph and its complement are class 1.
4 SRGs of degree at most 18
According to the list of Brouwer [2] all primitive SRGs of even order and degree at most
18 are known (one only has to check the parameter sets up to n = 182 + 1 = 325). The
parameters together with the number of nonisomorphic SRGs with k < n/2 are given in
Table 1 (the ones with k ≥ n/2 are the complements of a to e). The graph with parameter
Table 1: Primitive SRGs with n even and k ≤ 18, k < n/2.
a (10, 3, 0, 1) 1 f (36, 10, 4, 2) 1 k (50, 7, 0, 1) 1
b (16, 5, 0, 2) 1 g (36, 14, 4, 6) 180 l (56, 10, 0, 2) 1
c (16, 6, 2, 2) 2 h (36, 14, 7, 4) 1 m (64, 14, 6, 2) 1
d (26, 10, 3, 4) 10 i (36, 15, 6, 6) 32548 n (64, 18, 2, 6) 167
e (28, 12, 6, 4) 4 j (40, 12, 2, 4) 28 o (100, 18, 8, 2) 1
set a is the Petersen graph, which is class 2. The complement of the Petersen graph is the
triangular graph T (5) which is class 1 by Alspach’s result [1]. Also Case h and one of the
graphs of Case e is a triangular graph and therefore class 1. For the parameter sets f , m
and o there is a unique SRG, the so called Lattice graph. This SRG belongs to the Latin
square graphs, and by Corollary 2.4 the graph is class 1, and so is its complement. Case l is
the Gewirtz graph, which is class 1 by Lemma 2.2, as we saw in Section 2. All other graphs
are tested by computer (we actually tested all graphs in Table 1 and their complements).
Using SageMath [22], we wrote a computer program that searches for an edge coloring in
a k-regular graph with k colors. In each step we look (randomly) for a perfect matching,
remove all its edges and continue until the remaining graph has no perfect matching. If
there are still edges left we start again. We run this algorithm repeatedly until an edge
coloring is found. The code for this project is made freely available in a public GitHub
repository which can be found at [14]. By use of this approach we found a 1-factorization
S. M. Cioabă, K. Guo and W. H. Haemers: The chromatic index of strongly regular graphs 193
in all graphs of Table 1, and in their complements, except for the Petersen graph. Thus we
found:
Theorem 4.1. With the single exception of the Petersen graph, a primitive SRG of even
order and degree at most 18 is class 1 and so is its complement.
For the description of the graphs we used the website of Spence [23]. This website
also contains several SRGs with parameters (50, 21, 8, 9). We also ran the search for these
graphs. All are class 1.
It is surprising that in all cases our straightforward heuristic finds a 1-factorization. The
heuristic is fast. It took about one hour to find a 1-factorization in each of the 32548 SRGs
with parameter set i.
ORCID iDs
Sebastian M. Cioabă https://orcid.org/0000-0001-9983-0212
Krystal Guo https://orcid.org/0000-0001-8776-537X
Willem H. Haemers https://orcid.org/0000-0001-7308-8355
References
[1] B. Alspach, A 1-factorization of the line graphs of complete graphs, J. Graph Theory 6 (1982),
441–445, doi:10.1002/jgt.3190060408.
[2] A. E. Brouwer, Parameters of strongly regular graphs, http://www.win.tue.nl/˜aeb/
graphs/srg/srgtab.html.
[3] A. E. Brouwer, A slowly growing collection of graph descriptions, http://www.win.tue.
nl/˜aeb/graphs/index.html.
[4] A. E. Brouwer and W. H. Haemers, The gewirtz graph – an exercise in the theory of graph
spectra, European J. Combin. 14 (1993), 397–407, doi:10.1006/eujc.1993.1044.
[5] A. E. Brouwer and W. H. Haemers, Eigenvalues and perfect matchings, Linear Algebra Appl.
395 (2005), 155–162, doi:10.1016/j.laa.2004.08.014.
[6] A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, New York, NY, 2012, doi:
10.1007/978-1-4614-1939-6.
[7] D. Cariolaro and A. J. W. Hilton, An application of Tutte’s theorem to 1-factorization of regular
graphs of high degree, Discrete Math. 309 (2009), 4736–4745, doi:10.1016/j.disc.2008.05.046.
[8] A. G. Chetwynd and A. J. W. Hilton, Regular graphs of high degree are 1-factorizable, Proc.
London Math. Soc. 50 (1985), 193–206, doi:10.1112/plms/s3-50.2.193.
[9] S. M. Cioabă, D. A. Gregory and W. H. Haemers, Matchings in regular graphs from eigenval-
ues, J. Comb. Theory Ser. B 99 (2009), 287–297, doi:10.1016/j.jctb.2008.06.008.
[10] S. M. Cioabă and W. Li, The extendability of matchings in strongly regular graphs, Electron.
J. Combin. 21 (2014), #P2.34 (23 pages), doi:10.37236/4142.
[11] B. Csaba, D. Kühn, A. Lo, D. Osthus and A. Treglown, Proof of the 1-factorization and Hamil-
ton Decomposition Conjectures, volume 244 of Memoirs of the American Mathematical Soci-
ety, American Mathematical Society, Providence, RI, 2016, doi:10.1090/memo/1154.
[12] I. Darijani, D. A. Pike and J. Poulin, The chromatic index of block intersection graphs of
Kirkman triple systems and cyclic Steiner triple systems, Australas. J. Combin. 69 (2017),
145–158, https://ajc.maths.uq.edu.au/pdf/69/ajc_v69_p145.pdf.
194 Ars Math. Contemp. 20 (2021) 187–194
[13] A. Ferber and V. Jain, 1-factorizations of pseudorandom graphs, Random Structures Algorithms
57 (2020), 259–278, doi:10.1002/rsa.20927.
[14] K. Guo, kguo-sagecode/srg-edge-coloring: Determining if a k-regular graph is k-edge-
colorable, Version v1.0.0, Zenodo, 2020, doi:10.5281/zenodo.4031224.
[15] W. H. Haemers, Eigenvalue techniques in design and graph theory, Ph.D. thesis, Eindhoven
University of Technology, The Netherlands, 1979, doi:10.6100/ir41103.
[16] W. H. Haemers and V. Tonchev, Spreads in strongly regular graphs, Des. Codes Cryptogr. 8
(1996), 145–157, doi:10.1007/bf00130574.
[17] D. G. Hoffman and C. A. Rodger, The chromatic index of complete multipartite graphs, J.
Graph Theory 16 (1992), 159–163, doi:10.1002/jgt.3190160207.
[18] I. Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 10 (1981), 718–720, doi:
10.1137/0210055.
[19] D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre,
Math. Ann. 77 (1916), 453–465, doi:10.1007/bf01456961.
[20] R. Naserasr and R. Škrekovski, The Petersen graph is not 3-edge-colorable – a new proof,
Discrete Math. 268 (2003), 325–326, doi:10.1016/s0012-365x(03)00138-9.
[21] A. Neumaier, Strongly regular graphs with smallest eigenvalue −m, Arch. Math. 33 (1979),
392–400, doi:10.1007/bf01222774.
[22] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.3),
http://www.sagemath.org.
[23] E. Spence, Strongly regular graphs on at most 64 vertices, http:/www.maths.gla.ac.
uk/˜es/srgraphs.php.
[24] V. G. Vizing, Critical graphs with given chromatic class, Diskret. Analiz 5 (1965), 9–17.
[25] L. Volkmann, The Petersen graph is not 1-factorable: postscript to ‘The Petersen graph is not
3-edge-colorable – a new proof’ [Discrete Math. 268 (2003), 325–326], Discrete Math. 287
(2004), 193–194, doi:10.1016/j.disc.2004.07.008.