ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 19 (2020) 209-229
https://doi.org/10.26493/1855-3974.2039.efc
(Also available at http://amc-journal.eu)
A Mobius-type gluing technique for obtaining edge-critical graphs*
Simona Bonvicini t ©
Dipartimento di Scienze Fisiche, Informatiche e Matematiche, Universita di Modena e Reggio Emilia, via Campi 213/b, 41126 Modena, Italy
Andrea Vietri ©
Dipartimento di Scienze di Base eApplicate per l'Ingegneria, Sapienza Universita di Roma, via Scarpa 16, 00161 Rome, Italy
Received 7 July 2019, accepted 15 May 2020, published online 14 November 2020
Using a technique which is inspired by topology, we construct original examples of 3-and 4-edge critical graphs. The 3-critical graphs cover all even orders starting from 26; the 4-critical graphs cover all even orders starting from 20 and all the odd orders. In particular, the 3-critical graphs are not isomorphic to the graphs provided by Goldberg for disproving the Critical Graph Conjecture. Using the same approach we also revisit the construction of some fundamental critical graphs, such as Goldberg's infinite family of 3-critical graphs, Chetwynd's 4-critical graph of order 16 and Fiol's 4-critical graph of order 18.
Keywords: Edge-colouring, critical graph, Mobius strip. Math. Subj. Class. (2020): 05C10, 05C15
1 Introduction
In the present paper, we deal with graphs that are not necessarily simple, so multiple (or parallel) edges are allowed but loops are excluded. We denote by x'(G) the chromatic index of a graph G, namely, the minimum number of colours that are needed for an edge-colouring of G. Vizing, in [12], proved that A(G) < x'(G) < A(G) + ^(G), where
*The authors are grateful to the referees, with particular regard to the constructive comments of one referee which resulted in an improved version of the manuscript. This manuscript was prepared with the funding support of Progetti di Ateneo, Sapienza Universita di Roma. i Corresponding author.
E-mail addresses: simona.bonvicini@unimore.it (Simona Bonvicini), andrea.vietri@uniroma1.it (Andrea Vietri)
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
210
Ars Math. Contemp. 19 (2020) 189-208
A(G) and ^(G) are the maximum degree and the maximum multiplicity (the number of parallel edges for two fixed vertices) respectively. A simple graph G is said to be class 1 or 2 according to whether x'(G) is A(G) or A(G) + 1, respectively. We will restrict our attention to graphs whose chromatic index is at most A + 1. Edge-critical graphs will be our main object of study:
Definition 1.1. For a given graph G, let G - e denote the graph obtained by removing an edge e; G is A-(edge)-critical if x'(G) = A + 1 and x'(G - e) = A for any edge e.
In the literature, three small critical graphs of considerable importance appeared respectively in [9, 7] and [6]. The first graph (see the left side of Figure 10) was constructed by Goldberg as the first counterexample related to the "Critical Graph Conjecture" according to which all critical graphs should have an odd number of vertices (see [6]); such a graph had the smallest number of vertices (22) in an infinite family of graphs of even order constructed by Goldberg. The second graph - see the left side of Figure 1 - was found by Fiol as an example of critical, simple graph of smaller order, namely 18; the last graph - see the right side of the figure - is due to Chetwynd; it has order 16 but it is not simple because of one multiple edge.
It is still unknown whether a simple, critical graph of order 16 exists. As to smaller orders, such a question was settled by a number of contributions over the years. In details, Jacobsen's work (see [10]) ruled out all graphs with 4,6, 8, and 10 vertices; Fiorini and Wilson (see [8]) added the case 12 to the above list of non-admissible values; Bokal, Brinkmann, and Griinewald (see [2]) proved that also 14 is non-admissible.
In this paper, we push forward the analogy between non-orientable manifolds and class 2 graphs which was introduced in [11] and describe a new method for constructing critical graphs. We show the effectiveness of this method by constructing infinite families of critical simple graphs. The constructions cover all odd and even orders for 4-critical graphs, the odd order starting from 5, the even orders starting from 20, as well as all even orders for 3-critical graphs, including the orders of Goldberg's infinite family starting from 28
(a)
(b)
Figure 1: Two remarkable 4-critical graphs.
S. Bonvicini and A. Vietri: A Mobius-type gluing technique for obtaining edge-critical graphs 211
(the orders of Goldberg's graphs are all those numbers congruent to 8 (mod 16), and the further value 22). The 3-critical graphs of even order that we construct are not isomorphic to the graphs of Goldberg's infinite family; the graphs are simple, except the 4-critical graph of order 16. According to the literature, our constructions provide in particular the first example of an infinite family of A-critical graphs for degree 4. The present approach is expected to yield infinite families also for larger degrees, in the next future, because the key definitions can be easily exported to the general case.
Our method allows to build up critical graphs starting from class 1 graphs with an elementary and "nice" shape (see for instance Figure 2). This is innovative with respect to well-know methods that construct A-critical graphs starting from critical graphs with maximum degree not exceeding A - see Theorem 4.6 and 4.9 in [ ].
Following the mentioned approach in [11], we also show that the infinite family of Goldberg's graphs disproving the "Critical Graph Conjecture" and the other two counterx-amples constructed by Fiol and Chetwynd can be obtained by a suitable identification of vertices which is pretty analogous to the topological identification yielding the Mobius strip from a rectangular strip. Details about the change of language - from topology to graph theory - can be found in [ ].
Some additional terminology is required; in particular, certain distinguished vertices that play a basic role in the constructions shall be emphasised by suitable adjectives. Leaving details to the next sections, we anticipate that all the constructions will rely on particular pairs of vertices which are analogous to the extremes of a rectangular strip before the identification that leads to a Mobius strip. In our setting, any such pair will undergo a transformation which is similar to the topological identification of the extremes of the rectangular strip. The change from orientability to non-orientability, caused by the identification, is rephrased as the change from class 1 to class 2 as a consequence of the prescribed transformation.
Many standard definitions in this paper are in accordance with the textbook [3] by Bondy and Murty. As a further source, we mention the textbook [5] by Bryant. Edges like {u, v} are simply denoted by uv. We use the term t-colouring if the colour set has size t. Given a vertex v of a graph G, the palette of v, in symbols PY(v) or simply P(v), is the set of colours that a colouring 7 of G assigns to the edges containing v. In some cases, we will need to write yg so as to specify the graph we are colouring. The complementary set PY (v) or P(v) is the complementary palette of v with respect to the colour set of 7. If a colour is missing at a vertex v, we say that v lacks that colour. Finally, a vertex of degree h is an h-vertex.
For our purposes we also recall Vizing's Adjacency Lemma (VAL), concerning the structure of critical (simple) graphs, and the quite elementary, still very useful, Parity Lemma (PL):
Theorem 1.2 (VAL [13]). If uv is an edge of a A-critical graph, then u is adjacent to at least A — deg(v) + 1 A-vertices (different from v).
Lemma 1.3 (PL [1]). For any colouring of a graph G, the number of vertices that lack a given colour has the same parity as \V(G)|.
Although there exist several generalisations of VAL to multigraphs, for our purposes it suffices to consider the simple graph version (see the lines just above Remark 2.8).
212
Ars Math. Contemp. 19 (2020) 189-208
2 Fertile pairs of vertices
As hinted in the Introduction, the constructions of critical graphs that follow can be thought of as identifications of special pairs of vertices which change the colouring class from 1 to 2. Accordingly, the first step in each construction is the choice of a suitable pair of vertices which we are going to define as fertile pair. There are three kinds of fertile pairs, but after a little thought all of them can be related to the same kind - as we will soon explain. Conversely, given a critical graph, we will show that it is obtained as a suitable identification of a fertile pair which collapses to a unique vertex. In this reconstruction process, it is important to note that the identification could be arbitrarily performed on every vertex, but the choice of a particular vertex is essential both for proving criticality in a comfortable way, and for generating new critical graphs using a pattern which is readily suggested by the fertile pair.
Definition 2.1. Let u, v be vertices of a graph G. Assume that the following conditions hold:
(*) u is not adjacent to v, deg(u) + deg(v) < A and, for every A-colouring, P(u) n
P (v) = 0.
(**) For any edge e, G - e admits a A-colouring such that P(u) n P(v) = 0.
Then, u and v are said to be conflicting. Assume, instead, the following:
(*) deg(u) = deg(v) = A — 1 and, for every A-colouring, P(u) = P(v).
(**) For any edge e which does not contain u nor v, G — e admits a A-colouring such that
P(u) = P(v).
In this case, u and v are same-lacking. Finally, assume the following:
(*) deg(u), deg(v) are smaller than A and, for every A-colouring, |P(u) U P(v)| = A.
(**) For any edge e, G — e admits a A-colouring such that |P(u) U P(v)| < A.
In this last case, u and v are said to be saturating.
In all of the three cases, we say that (u, v) is a fertile pair of vertices.
Remark 2.2. After the removal of e in the same-lacking case, we equivalently require that |P(u) UP(v) | > 2; this is trivial if e contains one or both vertices u, v. Furthermore, notice that in the saturating case condition |P(u) U P(v) | = A is equivalent to P(u) n P(v) = 0.
The following lemma is the basic link between topology and graph theory in the present context, and should be considered the starting point for all the next constructions.
Lemma 2.3. Let (u, v) be a fertile pair of a graph G having x'(G) = A > 2. For each of the following cases, the corresponding operation yields a A-critical graph.
(i)	If u and v are non-adjacent and conflicting, identify u and v.
(ii)	If u and v are same-lacking, add a new vertex w and edges uw, vw.
S. Bonvicini and A. Vietri: A Mobius-type gluing technique for obtaining edge-critical graphs 213
(iii) If u and v are saturating, add the edge uv.
Proof. If we identify a pair of conflicting vertices, we obtain a graph G' having maximum degree A and no proper A-coloring, since the palettes of two conflicting vertices share at least one color; hence G' is class 2. By definition 2.1, if we remove any edge e from G', we find at lest one A-coloring of G' - e such that the two conflicting vertices have disjoint palettes with respect to it; therefore, G' is A-critical. The same-lacking and saturating cases can be managed analogously.	□
Notice that adding two pendant edges uw, vw' when u and v are same-lacking yields conflicting 1-vertices w,w'. Similarly, adding one pendant edge uw when u and v are saturating yields conflicting vertices w, v. Therefore, the above operations can be regarded as identifications of conflicting vertices in all cases. These procedures could be rephrased in terms of atlases and orientability, as explained in [11]; the prototype of this analogy is given by the odd cycle C2n+1 of any fixed length. Such a graph is the result of the identification of two conflicting vertices, namely, the extremes of the path P2n+2 having the same number of edges. The path is "orientable" (i.e. 2-colourable) but the identification of conflicting vertices increases the chromatic index and compromises orientability. More precisely, the orientation of P2n+2 starts from a "local chart" (a colouring of the 2-star containing a non-extremal vertex v), and the local chart is subsequently extended so as to cover as many edges as possible. In the case of the path, we succeed in covering all the graph (so we have a "global atlas", that is, a global 2-colouring) whereas the cycle does not allow for a global 2-colouring because one edge must be excluded (the atlas cannot be extended to the whole graph). Notice that the hypothesis (**) for conflicting vertices is crucial to prove criticality.
Remark 2.4. The 4-critical graphs in Figure 1 can be obtained in the way described in Lemma 2.3, by considering the graphs G17, G19 in Figure 8(b), 9(a), respectively, and identifying the vertices v, v'. Such vertices are conflicting, as we will show in Section 3.
Here follow some examples as a first step towards the main theorems.
Example 2.5. Let us show that the graph G5 in Figure 2(a) has saturating vertices u^ uj, with 1 < i < j < 4. For every 4-colouring the number of vertices that lack a fixed colour is odd, according to PL, whence every 3-vertex lacks a different colour; on the other hand, one can easily verify that the removal of any edge allows for a 4-colouring such that |P(uj) U P(uj)| = 3 for any pair of 3-vertices.
Example 2.6. The graphs G7 and G9 in Figure 2(c)-(d) have saturating vertices u1, u2, because PL implies that these vertices have disjoint palettes for any 4-colouring, and it remains to make routine checks after the removal of any arbitrary edge.
Example 2.7. The graph G6 in Figure 2(b) has same-lacking vertices v1, v2, because PL forces the palettes to be equal and this is no longer true if we remove any edge not containing one or both vertices v1 , v2 .
Notice that graphs with same-lacking vertices can be replicated so as to form a chain along which a color is "transmitted". Such a transmission of colour is a fundamental concept in this paper and will be described more thoroughly in the next section.
In the following remark, we consider critical graphs having at least three vertices of maximum degree. VAL implies that this property holds for every simple graph, but in the
214
Ars Math. Contemp. 19 (2020) 189-208
Figure 2: Fertile pairs of vertices: u1 and u2 are saturating, v1 and v2 are same-lacking.
presence of multiple edges the number of vertices of maximum degree might be smaller than 3. For instance, the complete graph K3 with A -1 parallel edges connecting two fixed vertices is A-critical and has only two vertices of maximum degree.
Remark 2.8. Let G be a A-critical graph having at least three vertices of maximum degree. Let u, v be adjacent vertices that are connected by h parallel edges (possibly h = 1). After deleting one of the parallel edges, u and v become saturating and the degree remains equal to A.
According to the above remark, Chetwynd's 4-critical graph can also be obtained by inserting an additional edge between the saturating vertices ui, u2.
3 Construction of graphs with fertile pairs
Graphs with fertile pairs of vertices can be obtained in several ways from smaller graphs with the same property. The methods we present here will be applied to prove the main theorems.
Lemma 3.1. Let H1 and H2 be vertex-disjoint graphs of degree A > 2 and such that x'(H1) = x'(H2) = A. Assume that v1, v2 are same-lacking in H1 and u1,u2 are same-lacking (resp. saturating) in H2. The graph H obtained from H1 and H2 by adding the edge u2v2 has again maximum degree A, chromatic index A, and has same-lacking (resp. saturating) vertices u1,v1.
Proof. Let us analyse the same-lacking case. A colouring of H can be obtained by assuming that u2 and v2 lack the same colour in two given A-colourings of H1 and H2; by the hypothesis, u1 and v1 lack that colour. If we now remove any edge, say in H1, u2v2 can be coloured with a colour which is present at u1. Such a colour is instead missing at v1. A similar argument applies to the saturating case.	□
S. Bonvicini and A. Vietri: A Mobius-type gluing technique for obtaining edge-critical graphs 215
Example 3.2. We consider two copies of G6 - see Figure 2(b) - as the graphs H1 and H2. We can actually iterate the gluing process m times, m > 1, so as to obtain a graph of order 6m, of maximum degree 4, whose 3-vertices are still fertile (same-lacking). Let us denote this graph by G™ - see Figure 3. This graph will play a basic role in the proofs of Theorem 5.1 and 5.2.
Figure 3: The graph G^ in Example 3.2 is a concatenation of graphs with same-lacking pairs.
The purpose of the next couple of definitions is twofold. On one hand, they allow to recover Chetwynd and Fiol's counterexamples in the light of our approach via transmission of colours along the edges of a graph. On the other hand, they play an important role in the construction of critical graphs of even order that will follow in the next pages. These definitions involve graphs with maximum degree 4, although they can be extended to graphs with A > 4.
Before providing the definitions, some further observations are in order. What we refer to as transmitting vertices should be regarded as terminal nodes which lend themselves to being connected to other graphs so as to yield a global graph with conflicting vertices and, eventually, a critical graph. The fundamental property of 2- or 3-colour transmitting vertices concerns the complementary palettes, that is, the colours actually missing at each vertex. For, the missing colours can be seen as the admissible colours of any edge which is added to the graph and contains that vertex. In the two definitions, it is the interplay between the colours missing at each distinguished vertex to ensure that the connecting edges, when added, will transmit some prescribed colour across the whole graph, and will eventually increase the chromatic index. Indeed, the vertices we are going to introduce are the first step towards the construction of graphs with conflicting vertices (see Propositions 3.8 and 3.12).
Let S © T denote the symmetric difference between the sets S and T.
Definition 3.3. Let G be a graph having x (G) = A = 4, and u,v,u^u2 be distinct vertices of G, where deg(u) = deg(v) = 2, deg(u1) = deg(u2) = 3. We say that G is 3-colour transmitting with respect to u, v, u1, u2 if the following conditions hold:
(1)	there exists a 4-colouring such that u1 and u2 lack distinct colours A and B, exactly one colour is missing simultaneously in u, v and this colour is either A or B;
(2)	for every 4-colouring such that u1 and u2 lack distinct colours A and B, |{A, B} U (P(u) © P(v))| = 3 (in particular, in the colouring in (1) the two other colours missing at u and v are different from A and B);
(3)	for every edge e there exists a 4-colouring of G-e with colours A, B, C, D satisfying
A € P(ui), B € P(u2), C € P(u) n P(V) and the set {A, D} or {B, D} is contained in P(u) © P(v).
216
Ars Math. Contemp. 19 (2020) 189-208
If we slightly alter the above definition by setting « = u2 and deg(ui) = 2, the resulting graph is said 3-colour transmitting with respect to w, v, u1. In this case, the first requirement in (1) and (2) clearly becomes "u1 lacks colours A and B", in symbols A, B e
PR).
Definition 3.4. Let G be a graph of maximum degree A = 4 and x'(G) = 4. Let w, w1, w2 be distinct vertices of G, where deg(w) = 2, deg(w1) = deg(w2) = 3. We say that G is 2-colour transmitting with respect to w, w1, w2, if the following conditions hold:
(1)	for every 4-colouring of G the set |P(w1) U P(w2)| contains exactly two colours and coincides with P (w);
(2)	for every edge e there exists a 4-colouring of G - e with colours A, B, C such that
A e P(W1), B e P(W2) and P(w) contains {A, C} or {B, C}.
Similarly as above, if the vertices w1,w2 coincide and deg(w1) = 2, we say that the graph is 2-colour transmitting with respect to w, w1; the requirement in condition (2) becomes "w1 lacks colours A and B".
Example 3.5. The graph G12 in Figure 4(a) is 3-colour transmitting with respect to w, v, u1, u2, as we are going to explain by testing the conditions of Definition 3.3. Condition (1) holds as shown in Figure 4(a). Condition (3) can be checked by setting: P(w) C {2,3}, P(v) C {2,4}, and P(z1) C {1,4}. In the graph G12 - e, the palettes of the vertices W1,u2 take the following values: P(«1) C {1,2,3} and P(«2) C {1,3,4}; P(«1) C {2, 3,4} and P(«2) C {1,2, 3}; P(«1) C {2, 3,4} and P(«2) C {1,2,4}. Notice that P(«) C {2,3}, P(v) C {2,4} mean that 1 e P(«) n P(v) and {3,4} C P(«) © P(v), that is, colour 1 corresponds to colour C in Condition (3) and {3, 4} corresponds to one of the sets {A, D} or {B, D}, where A e P(«1), B e P(«2). Thus, for instance, if P(«1) C {1,2, 3} and P(«2) C {1,3,4}, then A = 4, B = 2 and D = 3.
It remains to prove Condition (2). By PL, the number of vertices that lack a given colour is even, and there are 6 vertices of degree smaller than 4. However, a color missing in all these vertices would make the two palettes of degree 3 equal, which is not allowed by assumption. Now let us partition the 2 • 3 + 4 • 2 colours on the above 6 vertices either as 2 + 2 + 4 + 6 or as 2 + 4 + 4 + 4, where each part counts the occurrences of a fixed colour (0 is missing, by the above discussion). Up to permutations of colours there are two colourings of the first type and three of the second type (in the table, palettes of size 4 are not present and we assume that palettes of size 3 are the same in all cases):
{1, 2, 3}	{1, 2, 3}
{1, 2,4}	{l, 2, 4}
{1, 2}	{1, 3}
{1, 2}	{1, 3}
{1, 3}	{1, 3}
{1, 4}	{1, 4}
{1, 2, 3}	{1, 2, 3}	{1, 2, 3}
{1, 2, 4}	{1, 2, 4}	{1, 2, 4}
{1, 2}	{1, 4}	{1, 3}
{1, 4}	{1, 4}	{1, 4}
{2, 4}	{2, 3}	{3, 4}
{3, 4}	{2, 4}	{3, 4}
Whatever the assignments of palettes to the 2-vertices, column 2 and column 4 satisfy (2). For the colouring 71 in the 1st column, condition |P(wi) U P(w2) U (P(w) © P(v))| = 3 is not satisfied if we choose {P(u),P(v)} = {{1, 2}, {1, 3}} or {P(w),P(v)} = {{1, 2}, {1,4}}. The permutation of colours 3 and 4 leaves y1 invariant and switches the sets {{1,2}, {1,3}}, {{1, 2}, {1,4}}. Therefore, in order to show that Condition (2)
S. Bonvicini and A. Vietri: A Mobius-type gluing technique for obtaining edge-critical graphs 217
is satisfied for the colouring 71, it suffices to show that the graph G12 cannot be coloured according to 71 by setting {P(u), P(v)} = {{1, 2}, {1, 3}}.
Suppose, on the contrary, that G12 can be coloured according to y1 by setting {P(u), P(v)} = {{1,2}, {1,3}}. The set of palettes of y1 shows that colour 1 induces a perfect matching of the graph G12. As shown in Figure 5, there are exactly four perfect matchings of G12. By the symmetry of the graph and by the fact that the sets {{1,2}, {1,3}}, {{1, 2}, {1,4}} can be obtained one from the other by a permutation of colours 3 and 4, we can consider the first two perfect matchings of Figure 5. The set of palettes of y1 also shows that colour 2 induces a matching of cardinality 5, where exactly one of the vertices u, v (respectively, z1, z2) is unmatched since we are supposing {P(u), P(v)} = {{1, 2}, {1, 3}} and {P(z1),P(z2)} = {{1,2}, {1,4}}. Figure 6 shows how to colour the edges of G12 with 1 and 2. In each of the four cases represented in Figure 6, one can see that is not possible to colour to edges of G12 according to the colouring y1 by setting {P(u), P(v)} = {{1, 2}, {1,3}}. Therefore, if G12 can be coloured by y1, then y1 satisfies Condition (2). The same can be repeated for the remaining colourings in the 3rd and 5th column. It is thus proved that every 4-colouring of G12 with |P(u1) © P(u2)| = 2 satisfies Condition (2).
U\
G12 3
(a)
U
He
, w c/ \d
w1	w2
(b)
3
Figure 4: (a): A 4-colouring of the graph Gi2 in Example 3.5 that satisfies Conditions (1) and (2) of Definition 3.3. (b): A 4-colouring of the graph H6 in Example 3.7.
ui	U1	U1	U1
Figure 5: Perfect matchings of the graph G12 that are considered in Example 3.5.
There are several methods for obtaining a 3-colour transmitting graph starting from a smaller one. For instance, in the graph G12 of Figure 4(a), we can delete the edge u1u2 and connect the remaining graph to the graph G™ in Figure 3 by adding the edges u1v1, u2v2. The resulting graph is 3-colour transmitting with respect to u, v, u1, u2. In the next example, we show a more elaborate method for obtaining a 3-colour transmitting graph starting
218
Ars Math. Contemp. 19 (2020) 189-208
ui	ui	ui	ui
Figure 6: The edges of the graph G12 are coloured according to the palettes
{1, 2,3,4}, {1,2,3}, {1,2,4}, {1, 2}, {1,2}, {1,3}, {1,4} by setting {P(u),P(v)} = {{1, 2}, {1, 3}} and {P(zi), P(z2)} = {{1,2}, {1,4}}; colour 1 induces a perfect matching, colour 2 induces a matching of cardinality 5, where exactly one of the vertices u, v (respectively, z1, z2) is unmatched (see Example 3.5).
from a smaller one. This method allows to find a graph that will be used to construct Fiol's 4-critical graph of order 18.
Example 3.6. Consider the graph N in Figure 7(a). Notice that P(w) = P(w1) © P(w2) for every 4-colouring of the graph N, as a straightforward consequence of PL. We denote by L the graph obtained from G12 in Figure 4 by deleting the edge m1m2. Let G16 be the graph resulting from the identification of the vertices w1 G V(N) with u1 G V(L) and of w2 G V(N) with u2 G V(L). We have that x'(L) = A = 4 (see the colouring in Figure 7(b)).
Let us show that G16 is 3-colour transmitting with respect to u, v, w by testing Definition 3.3 with u1 = u2. Condition (1) follows from the colouring in Figure 7(b). _
Condition (2) is satisfied if every 4-coloring of G16 satisfies the relation |P(w) U (P(u) © P(v))| = 3. Suppose that there exists a 4-colouring 7 of G16 such that |PY(w) U
(p7(u) © P7(v))| = 3, that is, P7(w) = {A,B}, P7(u) © P7(v) = {A, C} or {B,C}. The colouring 7 induces a colouring 7' of G12 such that Py (u1) © Py (u2) = {A, B} and P7' (u) © P7/ (v) = {A, C} or {B, C}, that is, 7' does not satisfies Condition (2) of Definition 3.3. That yields a contradiction, since G12 is 3-colour transmitting with respect
to u, v, u1, u2.
Condition (3) holds if for every edge e G E(G16) there exists a 4-colouring of G16 - e such that {A, B} Ç P (w), C G P (u) n P (v) and {A, D} Ç P (u) © P(v) where A, B, D are distinct. Assume e G E(G12). Since G12 is 3-colour transmitting with respect to u,v,u1,u2, there exists a suitable colouring which can be easily extended to the whole graph G16.
If e G E(N), we colour the edges of G16 belonging to G12 by the 4-colouring in Figure 4(a), so that P(u) = {2, 3} and P(v) = {2,4}. One can verify that the edges of N - e can be coloured in such a way that P (w) Ç {2,4}. Therefore, {1,3} Ç P (w), 1 G P (u) n P (v) and {3,4} Ç P (u) © P (v), that is, Condition (3) is satisfied if e G E(N ).
Example 3.7. The graph H6 in Figure 4(b) is 2-colour transmitting with respect to w, w1, w2. The conditions of Definition 3.4 are satisfied: Condition (1) follows from Parity Lemma; Condition (2) can be verified by coluring the edges with A, B, C, D and setting
P (w1) Ç {B, C, D}, P (w2 ) Ç {A, C, D}, P (w) Ç {A, D}.
S. Bonvicini and A. Vietri: A Mobius-type gluing technique for obtaining edge-critical graphs 219
w
(a)
4
wy 1
G
16
(b)
Figure 7: (a): The graph N. (b): A 4-colouring of the graph G16 that satisfies Conditions (1) and (2) of Definition 3.3; as proved in Example 3.6, the graph G16 is 3-colour transmitting with respect to u, v, w.
Definitions 3.3 and 3.4 are used to construct graphs having fertile vertices. The next result is a construction of graphs having fertile vertices and whose maximum degree A is 4. The construction can be extended to graphs whose maximum degree is larger than 4 and having multiple edges. In this context, we limit ourselves to consider A = 4.
We recall that a bowtie is the graph obtained by identifying two vertices belonging to two distinct 3-cycles, thus obtaining a centre of degree 4 and four 2-vertices. If the 3-cycle are (x, y1, y2) and (x', y'1 ,y'2), then we denote by B(x, y1,y2 ,y[ ,y'2) the bowtie resulting from the identification of the vertices x and x'.
Proposition 3.8. Let B = B(x, u', v', w, y) be a bowtie with centre x and 2-vertices u', v', w, y. Let K and M be graphs of maximum degree 4 and x'(K) = x'(M) = 4, with the following features. The graph K is 3-colour transmitting with respect to u, v, u1,u2, where degK(u) = degK(v) = 2, degK(u1) = degK(u2) = 3; either M is 2-colour transmitting with respect to w,wi,w2, where degM(w) = 2,degM(wj) = degM(w2) = 3, or M is 2-colour transmitting with respect to w, w1, where degM (w) = degM (w1) = 2.
Let H be the graph obtained from B, K and M by identifying the vertices u' with u, w' with w and by adding the edges u1w1,u2w2 or u1w1,u2w1 according to whether M is 2-colour transmitting with respect to w, w1, w2 or with respect to w, w1, respectively. The graph H has maximum degree 4, x'(H) = 4 and the vertices v, v' are conflicting.
Proof. We identify the edge u2w2 with the edge u2w1 if w1 = w2, that is, if M is 2-colour transmitting with respect to w, w1. Since the identification of the vertices u, u' and w, w' does not increase the maximum degree of K, M and of the bowtie, the maximum degree of H is still 4. We show that x'(H) — 4. By Condition (1) of Definition 3.4, there exists a 4-colouring yM such that w1,w2 lack distinct colours A, B and these colours are missing in w (if w1 = w2, then w1 lacks both colours A, B). By Condition (1) and (2) of Definition 3.3, there exists a 4-colouring yK such that u1, u2 lack distinct colours A, B and exactly one of these two colours, say A, is missing simultaneously in u and v; the other two missing colours are different from B, that is, Py*k (u) = {A, C} Py*k (v) = {A, D}. We define a 4-colouring y* of H such that the restriction of y* to the edges of M (respectively, of K) coincides with yM (respectively, with y*k); the edges of the bowtie and u1w1,u2w2 are coloured as follows: {y*(u1wv1),Y*(u2wv2)} = {A, B}; Y*(wx) = A; y*(wy) = B; Y* (ux) = C; Y*(uv') = A; y(v'x) = B; and Y*(xy) = D. In conclusion x'(H) = 4.
220
Ars Math. Contemp. 19 (2020) 189-208
We prove that the vertices v, v' g V(H) are conflicting. Firstly, we show that for every 4-colouring of H, the palettes of v and v' share at least one colour. Suppose, on the contrary, that there exists a 4-colouring yi. of H such that v and v' have disjoint palettes. The restriction of yi to the edges of K (respectively, of M) is a 4-colouring yk (respectively, ym). The following relations hold: PYK(ux) = PYM(wx) = Yi(uiwi) = A; P7K (u2) = P7M (W2) = Yi(U2W2) = B (if wi = W2 then A = B and P7M (wi) = {A, B}). Moreover, PYK(v) = PY1 (v) = PY1 (v') = {y1(uv'), Y^v'x)} since we are supposing that v and v' have disjoint palettes with respect to y^ Therefore PYK (u) © P7K (v) = {Yi(uv'), Yi(ux)} © {Yi(uv'), Yi(v'x)} = {Yi(ux), Yi(v'x)}. By Condition (1) of Definition 3.4, the colours A, B are distinct and PYM (w) = {A, B}. It follows that {y1(wi), Y^wy)} = {A, B} and yi.(xy) = A, B, Y^ux), Y^v'x). Therefore, exactly one of the colours y^ux^yi.(v'x) is in {A, B}. Consequently, the set PYK (u) © PYK (v) = {yi. (ux), Y^v'x)} contains exactly one of the colours A, B. It follows that |PYK(ux) U Pyk(u2) U (PYK(u) © PYK(v))| = 3, a contradiction since K is 3-colour transmitting with respect to u, v, ux, vx. Hence, for every 4-colouring of H the palettes of the vertices v, v' share at least one colour.
We show that for every edge e g E(H) there exists a 4-colouring y' of H - e such that v and v' have disjoint palettes. We distinguish the cases: e g E(K); e g E(M); e g E(B); and e g {uxwx, u2w2}.
Case e e E(K).
By Condition (3) of Definition 3.3, there exists a 4-colouring 7 of K - e such that
A g Py (ui), B g Py (u2), C g Py (u) 0 Py(v), and the set {A, D} or {B,D} is contained in Py (u) © Py(v), where A, B, D are distinct. Without loss of generality, we can assume {A, D} Ç Py,(u) © Py(v). Now {A, D} can be contained in exactly one of the complementary palettes Py (u), Py ( v ) or in neither of them. The first case occurs only if e contains exactly one of the vertices u, v, and in this case {Py (u), Py (v)} = {{A, D, C}, {B, C}}. If, instead, e does not contain u, v, then {Py (u), Py (v)} = {{A, C}, {D, C}}.
We colour the edges of M according to an arbitrary 4-colouring ym of the graph M. By a permutation of the colours and by Condition (1) of Definition 3.4, we can assume that the colours A, B are missing in w and wx,w2 lack A, B, respectively (if wx = w2, then wx lacks both colours A, B). We define a 4-colouring y' of H - e such that the restriction of y' to K - e (respectively, to M) corresponds to the colouring Y (respectively, ym ) and y '(uxwx) = A; y'(u2w2) = B; y '(uv') = C ; y '(xy) = C. The colouring of the edges ux, v'x, wx, wy depends on the set {Py;(u),P^;(v)}. If {Py/(u),Py (v)} = {{A, C}, {D, C}}, then we set y'(wx) = B, Y'(wy) = A and the edges ux, v'x are coloured by A, D or D, A, respectively, according to whether PY/ (u) = {A, C} or Py (u) = {D, C}, respectively. If {Py (u),Py (v)} = {{A, D, C}, {B, C}}, then we set y'(wx) = A, Y'(wy) = B and the edges ux, v'x are coloured by D, B or B,D, respectively, according to whether Py (u) = {A, D, C} or Py (u) = {B, C}, respectively. Notice that Py (v') Ç PY/ (v), hence v, v' have disjoint palettes with respect to y'.
Case e e E(M).
We define a 4-colouring y' of H - e such that the edges of K are coloured according to the 4-colouring yk of K defined at the beginning of the proof. We have that Py (u) =
P7* (u) = {A, C}, P7/ (v) = P7* (v) = {A, D}. Since ux, u2 lack distinct colours A, B
S. Bonvicini and A. Vietri: A Mobius-type gluing technique for obtaining edge-critical graphs 221
with respect to yK, we can assume that u lacks A and u2 lacks B.
By Condition (2) of Definition 3.4, we can colour the edges of M - e according to the 4-colouring yM of M such that the vertices w1, w2 lack distinct colours, say A, B, and the colours A, C are missing in w, where A, B, C are distinct (if wi = w2, then wi lacks both colours A, B). The remaining edges of H - e are coloured as follows: Y '(uiwi) = A; y' (W2W2) = B; y '(uv') = A; y'(ux) = C ; y '(v' x) = D; y'(wx) = A; Y'(wy) = C; and y'(xy) = B. The vertices v, v' have disjoint palettes with respect to y', since Py (v') = Py (v) = {A, D}.
Case e G E(B).
We define a 4-colouring y' of H - e that corresponds to the 4-colouring y* of H defined at the beginning of the proof, except on the remaining edges of B - e. The edges of B - e are coloured in such a way that Py (v') Ç {A, D}, Py (u) Ç {A, C} and {y'(wx), Y'(wy)} Ç {A, B}. The vertices v, v' have disjoint palettes with respect to y',
since Py (v') Ç Py(v) = {A, D}.
Case e G {u-iw1,u2w2}.
We define a 4-colouring y' of H - e which coincides with yK on the subgraph K. So we have that Py (u) = P7^ (u) = {A, C}, Py(v) = P7^ (v) = {a, D} and {yK(uiwi), Yk(u2w2)} = {A, B}. Without loss of generality, we can assume that the edge e that has been removed is coloured with A. By Condition (1) of Definition 3.4, we can colour the edges of M in such a way that wi, w2 lack two distinct colurs, say B, C, and these two colours are missing in w. The edges of B are coloured as follows: y'(uv') = A; Y'(ux) = C; y'(v'x) = D; y'(wx) = B; Y'(wy) = C; and Y'(xy) = A. The vertices v, v' have disjoint palettes with respect to y', since Py (v') = Py (v) = {A, D}.	□
Remark 3.9. The argument of the above proof is still valid if we assume that K is 3-colour transmitting with respect to u, v, ui, where u, v, ui have degree 2 in K.
Example 3.10. We apply Proposition 3.8 to the graphs K = Gi2 and M = H6 in Figure 4. As remarked in Example 3.5, the graph Gi2 is 3-colour transmitting with respect to u, v, ui, u2. Similarly, in Example 3.7 we have seen that H6 is 2-colour transmitting with respect to w, wi,w2. By Proposition 3.8, we obtain the graph G2i inFigure8(a). The graph G2i has order 21, maximum degree 4, and x'(G2i) = 4. The vertices v, v' G V(G2i) are conflicting. Following the proof of Proposition 3.8 we can colour the edges of G2i according to the 4-colourings yK and yM in Figure 4 by setting a =1, b = 2, c = 3 and d = 4 (or c = 4 and d = 3). This graph will be used in the proof of Theorem 5.2.
Example 3.11 (Chetwynd's counterexample). We can apply Proposition 3.8 to the graph K = Gi2 in Figure 4(a) and to the dipole M = D2 with two parallel edges even thought the dipole D2 is not 2-colour transmitting with respect to its vertices. More precisely, as remarked in Example 3.5, the graph Gi2 is 3-colour transmitting with respect to u, v, ui, u2. It is easy to see that every 4-colouring of the graph D2 satisfies conditions (1) and (2) of Definition 3.4 with wi = w2. Therefore, we can repeat the proof of Proposition 3.8 and obtain the graph Gi7 in Figure 8(b) having order 17, maximum degree 4 and x'(Gi7) = 4. The vertices v, v' G V(Gi7) are conflicting. By Lemma 2.3, the identification of the vertices v, v' yields a 4-critical graph, namely, Chetwynd's 4-critical graph in Figure 1(b).
222
Ars Math. Contemp. 19 (2020) 189-208
u
G21
u
G17
(b)
w1
Figure 8: (a): The graph G21 constructed in Example 3.10. (b): The graph G17 constructed in Example 3.11.
Proposition 3.12. Let B = B(x,u',v',w,y) be a bowtie with centre x and 2-vertices u', v', w, y. Let K and M be graphs of maximum degree 4 and x'(K ) = x' (M ) = 4 with the following features. The graph K is 3-colour transmitting with respect to u, v, ui where degK(u) = degK(v) = degK(u1) = 2. The 2-vertices w, w1 e V(M) are saturating and for every e e E (M ) not containing w nor w1 there exists a 4-colouring of M — e such that w, w1 lack exactly one colour simultaneously.
Let H be the graph obtained from B, K and M by identifying the vertices u' with u; w' with w; and u1 with w1. The graph H has maximum degree 4, x'(H) = 4 and the vertices v,v' are conflicting.
Proof. The argument is the same as in the proof of Proposition 3.8. It is different in the case e e E(M). We show that if we remove an edge e e E(M), then there exists a 4-colouring 7' of H — e such that v, v' have disjoint palettes with respect to it. As in the proof of Proposition 3.8, the restriction of 7' to the edges of K corresponds to a 4-colouring YK of K such that PyK K) = {A, B}, PyK (u) = {A, C}, P7^ (v) = {A, D}. We set Y'(uv') = A, y'(ux) = C, y'(v'x) = D. The restriction of 7' to the edges of M — e corresponds to a 4-colouring y'm of M — e. Since u1 and w1 are identified, the palette of w1 with respect to y'm is contained in {A, B}. We define y'm on the other edges of M — e as follows.
If e e E(M) does not contain w nor w1, then P7^ (w1) = {A, B}. By the assumptions, there exists a 4-colouring of M — e such that w, w1 lack exactly one colour simultaneously. By a permutation of the colours, we can set P7^ (w) = {A, C}. We can colour the remaining edges of H — e as follow: 7'(wx) = B, 7'(wy) = D, Y'(xy) = A. The colouring 7' of H — e is thus defined and v, v' have disjoint palettes with respect to it, since Py (v') = Py (v) = {A, D}. We can repeat similar arguments if the edge e e E(M) contains w but not w1 .
If e e E(M) contains w1, then we can assume that P7^ (w1) = {A}. We can permute the colours in M — e so that P7^ (w) Ç {B, C} or P7^ (w) Ç {B, D}. The remaining edges of H — e are coloured as follows: 7'(wx) = A, 7'(xy) = B and Y'(wy) = D or C according to whether Py (w) Ç {B, C} or Py (w) Ç {B, D}, respectively. The
S. Bonvicini and A. Vietri: A Mobius-type gluing technique for obtaining edge-critical graphs 223
colouring 7' of H - e is thus defined and v, v' have disjoint palettes with respect to it, since
Py (v') = Py (v) = {A,D}.	□
Example 3.13. The graph G25 in Figure 9(b) has order 25, maximum degree 4 and x'(G25) = 4. The vertices v, v' are conflicting. It is obtained by applying Proposition 3.12 to the graphs K = G16 in Figure 7(b) and M = G7 in Figure 2(c). The vertices w1 are identified. As remarked in Example 3.6, the graph G16 is 3-colour transmitting with respect to w, v, u1. As remarked in Example 2.6, the 2-vertices w, w1 G V(G16) are saturating. Moreover, for every e G G7 not containing w nor w1 there exists a colouring of G7 - e such that P(w1) Ç {A, B} and P(w) Ç {A, C}, that is, the assumption in Proposition 3.12 is satisfied. By Lemma 2.3, the identification of the conflicting vertices v, v' yields a 4-critical graph of order 24.
Example 3.14 (Fiol's counterexample). Proposition 3.12 is still true if we assume that M consists of exactly one vertex. For instance, consider the graph G19 in Figure 9(a) obtained from the graph G16 in Figure 7(b) and M consisting of exactly one vertex. The vertices u1 and w1 are identified. The vertices v, v' G V(G19) are conflicting (we can repeat the proof of Proposition 3.8 without considering the case e G E(M)). By Lemma 2.3, the identification of the vertices v, v' yields a 4-critical graph, namely, Fiol's 4-critical graph in Figure 1(a).
Figure 9: u1 and w should be identified in both graphs. (a): The graph G19 has order 19, maximum degree 4 and x'(G19) = 4. (b): The graph G25 has order 25, maximum degree 4 and x'(G25) = 4. As shown in Example 3.14, the vertices v, v' are conflicting.
4 Counterexamples to the Critical Graph Conjecture
In 1971, Jacobsen showed that there are no 3-critical graphs of order < 10 and no 3-critical multigraphs of order < 8. This led him to formulate the Critical Graph Conjecture. As we already mentioned, the first counterexamples to the conjecture were constructed by Goldberg [9], and afterwards by Chetwynd [6] and Fiol [7]. In this section we show that
224
Ars Math. Contemp. 19 (2020) 189-208
also Goldberg's counterexample can be obtained by a Mobius-type technique. Furthermore, combining our technique with Goldberg's construction we show that for every even value value of n, n > 22, there exists a 3-critical graph of order n.
Goldberg was the first to disprove the Critical Graph Conjecture by constructing an infinite family of 3-critical graphs of even order, the smallest of which has order 22 [9]. The graph of order 22 is represented in Figure 10(a). A 3-critical graph of the infinite family can be obtained from the 3-critical graph of order 22 in Figure 10(a) by adding in pairs the graph H7 of order 7 in Figure 10(b). The result is the graph in Figure 11(a). A 3-critical graph of the infinite family has order n = 8 (mod 16), n > 24.
H
Xi	X2
Figure 10: (a): The 3-critical graph of order 22 constructed by Goldberg. (b): The graph H7 which is used to construct 3-critical graphs of order n = 8 (mod 16), n > 24.
Figure 11: (a): The infinite family of 3-critical graphs of order 8m, m > 3, m odd, constructed by Goldberg. (b): The graph H23 that yields the 3-critical graph of order 22 constructed by Goldberg by identifying the conflicting vertices u, v.
In what follows, we show that the 3-critical graphs constructed by Goldberg can be obtained by a Mobius type technique, namely, by identifying a pair of conflicting vertices in the case of the graph in Figure 10(a), or by connecting a pair of saturating vertices in
S. Bonvicini and A. Vietri: A Mobius-type gluing technique for obtaining edge-critical graphs 225
the case of the graph in Figure 11(a). In Lemma 4.2, we will show that the vertices u, v of the graph H23 in Figure 11(b) are conflicting. We give a proof of the fact that u, v are conflicting showing that the structure of the graph H7 forces to colour the edges of the graph in Figure 10(a) in a prescribed way, thus determining which vertex has to be split into two conflicting vertices. Analogously, for the proof of Lemma 4.3. The proofs of Lemmas 4.2 and 4.3 are based on the following result.
Lemma 4.1. Every 3-colouring of the graph H7 in Figure 10(b) satisfies the following condition:
\P(xo) U P(x) U P(xi+2)\ = 3 and P(xm) = P(xi+s) = P(xr) where i = 1 or i = 2, r G {0, i, i + 2} and the subscripts are (mod 4).
Proof. Since the colour set has cardinality 3 and PL holds, exactly three vertices of H7 lack the same colour A and the remaining 2-vertices of H7 lack distinct colours B, C, both different from A. A direct inspection on the graph shows that the vertices lacking the same colours are xi+1, xi+3 and xr, where i = 1 or i = 2 and r G {0, i, i + 2}.	□
Lemma 4.2. The graph H23 in Figure 11(b) is class 1 and the vertices u, v G V(H23) are conflicting.
The 3-critical graph of order 22 in Figure 10(a) constructed by Goldberg can be obtained from the graph H23 by identifying the conflicting vertices u, v G V(H23).
Proof. It is easy to see that H23 is class 1. We show that the vertices u, v G V(H23) are conflicting. Firstly, we prove that P(u) n P(v) = 0 for every 3-colouring of the the graph H23.
Let 7 be a 3-colouring of H23. Since 7 induces a 3-colouring of the subgraphs of H23 that are isomorphic to H7 andLemma4.1 holds, it is either \{y(x1y2), 7(x3y4), y(x0v)}\ = 3 or \{7(x2Zi),7(x4Z3),7(xov)}\ = 3. If \{y(xi^2),7(x3y4),7(xov)}\ = 3, then 7(xov) = 7(yov), by virtue of Lemma 4.1 on the subgraph of H23 which is isomorphic to H7 and contains the vertices y», 0 < i < 4. That yields a contradiction, hence \{7(x2z1), 7(x4z3), y(x0v)}\ = 3. Since Lemma 4.1 holds on the subgraph of H23 which is isomorphic to H7 and contains the vertices z, 0 < i < 4, we have 7(xov) = 7(zou). It is thus proved that P(u) n P(v) = 0 for every 3-colouring of H23.
It remains to prove that for every edge e G E(H23) there exists a 3-colouring 7' of H23 — e such that the vertices u, v have disjoint palettes with respect to it. The existence is straightforward if e is incident to u, since u has degree 1. Let {1,2, 3} be the colour set of 7'. To define 7', it suffices to define 7' on the edges in {xov, yov, zou, xjyj+1, xi+1zj : i =1, 3} and colour the remaining edges according to Lemma 4.1. For instance, if e is incident to the vertices in {xj, y» : 0 < i < 4}, e G {xov, yov, zou, xjyi+1, xi+1Zj : i = 1,3}, then we set 7'(x^) = 7'(zou) = 1; 7'(x3y4) = 7'(xov) = 2; 7'(yov) = 3; 7'(x2z1) = 7'(x4z3) = a G {1,2}. The remaining cases can be managed in a similar way. It is thus proved that u, v are conflicting. Now the assertion follows from Lemma 2.3 by identifying the vertices u, v.	□
Lemma 4.3. Let H8m, m > 3, m odd, be the graph obtained from the graph in Figure 11(a) by deleting the edge u1um. The graph is class 1 and the vertices u1,um are saturating. The 3-critical graphs of the infinite family constructed by Goldberg can be obtained by connecting a pair ofsaturating vertices.
226
Ars Math. Contemp. 19 (2020) 189-208
Proof. One can easily verify that the graph H8m is class 1. We prove that u1,um are saturating. Firstly, we show that |P(u1) U P(um)| = 3 for every 3-colouring of the graph H8m. For 1 < j < m, let Hj be the subgraph of H8m which is isomorphic to the graph H7 in Figure 10(b) and contains the vertices xj, 0 < i < 4. Every 3-colouring y of H8m induces a 3-colouring y' of the graph H7, that is, Lemma 4.1 holds. By the symmetry of the graph, we can assume that |Py (x1) U P7> (x2) U P7> (x1 )| = 3 and P7> (x1) = P7> (x1). Consequently, P7>(x2) = P7'(xj) and |P7/(x0) U P7> (x1) U P7>(x§)| = 3. From this we deduce that |Py (x0) U P7, (x{) U P7, (xj)| = 3 and P7> (x{) = Py (x{) if j is odd, 1 < j < m; |Py (x0) U Py (x1) U P7/ (x|)| = 3 and P7> (x{) = P7> (xj) if j is even, 1 < j < m. It follows that 7(xj0uj) = Y(xj0+1uj+1) for every 2 < j < m - 1, j even. We colour the edges of H8m by {1,2,3} and set 7(x0u2) = y(x0u3) = 3. Without loss of generality we can set j(u2u3) = 1, whence y(u1u2) = 2. One can see that {Y(x^uj),Y(ujuj+1)} = {y(x0uj+1),Y(ujuj+{)} = {1, 3} for every 2 < j < m - 1, j even. As a consequence, P(um) = {1,3}. It is thus proved that |P(u1) U P(um) | =3 for every 3-colouring of H8m, since 2 G P(u1).
We omit the routine proof that for every e G E (H8m) there exists a colouring of H8m such that |P (u1)UP (um)| < 3. It is thus proved that u1,um are saturating and the assertion follows from Lemma 2.3.	□
It is known that the 3-critical graph of order 22 constructed by Goldberg is the smallest 3-critical graph [4]. Combining our construction with that one of Goldberg, we can prove the following result.
Theorem 4.4. For every even value of n, n > 22, there exists a 3-critical graph of order n.
Proof. A critical graph of the infinite family constructed by Goldberg has order n = 8 (mod 16), n > 24. We construct a 3-critical graph of order n = 2 (mod 4), n > 26; and n = 0 (mod 4), n > 28. We define the auxiliary graphs H', K' and H'' that will be used in the construction. The graph H' is defined as follows. Consider m > 1 copies of the complete graph K4 - e; the 2-vertices of K4 - e are same-lacking. For 1 < i < m - 1, connect the ith copy of K4 - e to the (i + 1)th by adding exactly one edge joining a 2-vertex in the ith copy to a 2-vertex in the (i + 1)th copy. The resulting graph H' has exactly two 2-vertices, say v1 ,v2. By Lemma 3.1, the graph H' has maximum degree 3, x'(H') = 3 and the vertices v1 , v2 are same-lacking. Let K' be the graph of order 6 that can be obtained from the graph G6 in Figure 2(b) by deleting the edges v1v2,v3v5,v4v6. The graph K' has maximum degree 3, x'(K') = 3 and the vertices v1, v2 are same-lacking. The graph H'' is obtained from the graphs H' and K' by connecting the vertex v2 G V(K') to the vertex v1 G V(H'). By Lemma 3.1, the graph H'' has maximum degree 3, x'(H'') = 3 and the vertices v1 , v2 are same-lacking. Let H be the graph obtained from the graph H23 in Figure 11(b) and the graph r, where r g {H', K', H''}, by deleting the edge z0u G E(H23) and adding the edges z0v1,uv2. As remarked in Example 2.7, a graph with same-lacking vertices is able to transmit a color, therefore the graph H has maximum degree 3, x'(H) = 3 and the vertices u,v G V(H) are conflicting. Notice the following: |V(H)| = 23 + 4m > 27if r = H'; |V(H)| = 29 if r = K'; |V(H)| = 29 + 4m > 33 if r = H''. By Lemma 2.3, the identification of the conflicting vertices u,v G V(H) yields a 3-critical graph of order | V(H) | - 1. Hence, the assertion follows.	□
S. Bonvicini and A. Vietri: A Mobius-type gluing technique for obtaining edge-critical graphs 227
The 3-critical graphs of order n = 0 (mod 4), n > 28, that are constructed in the proof of Theorem 4.4, include the orders of Goldberg's infinte family but are not isomorphic to them. In fact, Goldberg's graphs have girth larger than 3; the 3-critical graphs in the proof of Theorem 4.4 have girth 3 as K' contains a 3-cycle.
5 From graphs with fertile vertices to 4-critical graphs
We show that it is possible to obtain 4-critical graphs of order n, for every n > 5, starting from the four graphs in Figure 2, the two graphs in Figure 1 and the graph G21 in Figure 8(a); these graphs have a pair of fertile vertices.
Theorem 5.1. For every odd integer n > 5 there exists a 4-critical simple graph of order n.
Proof. For every odd integer n > 5, we exhibit a graph H of maximum degree 4, x'(H) = 4 and order n having a pair of saturating vertices u^v^ The assertion follows from Lemma 2.3 by adding the edge u1v1.
The graph H is obtained from Lemma 3.1 as follows. We take the graph G™ in Figure 3 as the graph H1 in Lemma 3.1, where m > 1. As remarked in Example 3.2, it has order 6m > 6, maximum degree 4 and the vertices v1,v2 G V(G™) are same-lacking. We define the graph H2 in Lemma 3.1 as follows: if n = 1 (mod 6), then H2 is the graph G7 in Figure 2(c); if n = 3 (mod 6), then H2 is the graph G9 in Figure 2(d); if n = 5 (mod 6), then H2 is the graph G5 in Figure 2(a). By the remarks in Examples 2.5 and 2.6, the vertices u1,u2 G V(H2) are saturating. By Lemma 3.1, the graph H obtained from H1 = G™ and H2 by adding the edge u2v2 has maximum degree 4, x'(H) = 4 and the vertices u1, v1 G V(H) are saturating. Notice that |V(H)| = 6m + |V(H2)| > 11, where m > 1 and |V(H2)| G {5,7,9}. The graph G obtained from H by adding the edge u1v1 is 4-critical, since Lemma 2.3 holds. By construction, the graph G is simple. Since |V(G)| = |V(H)|, for every odd integer n > 11 there exists a 4-critical simple graph of order n. For n = 5, 7, 9, the assertion follows from Lemma 2.3 by setting H = G5, G7, G9, respectively, and by adding the edge u 1 u2.	□
Theorem 5.2. For every even integer n > 16 there exists a 4-critical graph of order n. The graph is simple unless n is equal to 16.
Proof. For n = 16,18, we resort to the well known graphs in Figure 1. For n = 20 we consider the graph G21 in Figure 8(a). As remarked in Example 3.10, the vertices v, v' G G21 are conflicting. The existence of a 4-critical graph of order 20 follows from Lemma 2.3 by identifying the vertices v and v'. Notice that the graph is simple.
For every even integer n > 22, we exhibit a graph H of maximum degree 4, x' (H) = 4 and order n having a pair of saturating vertices u1, v1. The assertion follows from Lemma 2.3 by adding the edge u1v1. The graph H is obtained from Lemma 3.1 as follows. We take G™ in Figure 3 as the graph H1 in Lemma 3.1, where m > 1. The graph H2 in Lemma 3.1 has even order and its definition depends on the congruence class of n modulo 6.
Case n = 0 (mod 6), n > 18.
The graph H2 is obtained from the 4-critical graph of order 18 in Figure 1(a) by the deletion of the edge u1u2. Alternatively, we can consider the 4-critical graph arising from the graph G25 in Figure 9(b) by identifying the vertices v, v' (see Example 3.13); H2 can be obtained by deleting one of the two edges containing u1 .
228
Ars Math. Contemp. 19 (2020) 189-208
Case n = 2 (mod 6), n > 20.
Consider the 4-critical graph G2o of order 20 obtained from the graph G2i in Figure 8(a) by identifying the vertices v, v'. Let H2 be the graph obtained from G20 by deleting the edge uiu2.
Case n = 4 (mod 6), n > 16.
The graph H2 is obtained from the 4-critical graph of order 16 in Figure 1(b) by the deletion of one parallel edge connecting the vertices u1, u2. For each congruence class of n, the vertices u1,u2 G V(H2) are saturating, since Remark 2.8 holds. Moreover, H2 is a simple graph of maximum degree 4, x'(H2) = 4 and |V(H2)| = 18, 20,16 according to whether n = 0,2,4 (mod 6), respectively. By Lemma 3.1, the graph H obtained from H1 = Gm and H2 by adding the edge u2v2 has maximum degree 4, x'(H) = 4 and the vertices u1, v1 G V(H) are saturating. Notice that |V(H)| = 6m + |V(H2)| > 22, where m > 1 and |V(H2)| G {16,18, 20}. By Lemma 2.3, the graph G obtained from H by adding the edge u1v1 is 4-critical. Since | V(G) | = | V(H) |, for every even integer n > 22 there exists a 4-critical graph of order n. Notice that these graphs are simple. Combining this result with the remarks on the existence of 4-critical graphs of order 16,18 and 20, the assertion follows.	□
There are alternative methods for constructing 4-critical graphs. For instance, consider the 4-critical graph G of order 20 obtained from the graph G21 in Figure 8(a) by identifying the vertices v, v'. Delete the edge u1u2 g E(G) and connect the remaining graph to the graph Gm in Figure 3. For every m > 1 we obtain a 4-critical graph of order 6m + 20.
6 A concluding remark
We are confident that the present work will provide suggestions and tools for constructing infinite families of critical graphs even beyond degree 4. The next step should be inevitably the degree 5. The key definitions are compatible with the general case, and we believe that the method is versatile enough. With some effort and further investigation, new infinite families are expected to be found in the near future.
ORCID iDs
Simona Bonvicini © https://orcid.org/0000-0001-5318-7866 Andrea Vietri E> https://orcid.org/0000-0002-6064-7987
References
[1]	D. Blanusa, Problem ceteriju boja (The problem of four colors), Glasnik Mat.-Fiz. Astr. Ser. II 1 (1946), 31-42.
[2]	D. Bokal, G. Brinkmann and S. Griinewald, Chromatic-index-critical graphs of orders 13 and 14, Discrete Math 300 (2005), 16-29, doi:10.1016/j.disc.2005.06.010.
[3]	J. A. Bondy and U. S. R. Murty, Graph Theory, volume 244 of Graduate Texts in Mathematics, Springer, New York, 2008, doi:10.1007/978-1-84628-970-5.
[4]	G. Brinkmann and E. Steffen, 3- and 4-critical graphs of small even order, Discrete Math. 169 (1997), 193-197, doi:10.1016/s0012-365x(96)00105-7.
[5]	V. Bryant, Aspects of Combinatorics: A Wide-Ranging Introduction, Cambridge University Press, Cambridge, 1993.
S. Bonvicini and A. Vietri: A Mobius-type gluing technique for obtaining edge-critical graphs 229
[6]	A. G. Chetwynd and R. J. Wilson, The rise and fall of the critical graph conjecture, J. Graph Theory 7 (1983), 153-157, doi:10.1002/jgt.3190070202.
[7]	M. A. Fiol, 3-grafos criticos, Ph.D. thesis, Barcelona University, Spain, 1980.
[8]	S. Fiorini and R. J. Wilson, Edge-Colourings of Graphs, volume 16 of Research Notes in Mathematics, Pitman, London, 1977.
[9]	M. K. Goldberg, Construction of class 2 graphs with maximum vertex degree 3, J. Comb. Theory Ser. B 31 (1981), 282-291, doi:10.1016/0095-8956(81)90030-7.
[10]	I. T. Jakobsen, On critical graphs with chromatic index 4, Discrete Math. 9 (1974), 265-276, doi:10.1016/0012-365x(74)90009-0.
[11]	A. Vietri, An analogy between edge colourings and differentiable manifolds, with a new perspective on 3-critical graphs, Graphs Combin. 31 (2015), 2425-2435, doi:10.1007/ s00373-014-1512-3.
[12]	V. G. Vizing, On an estimate of the chromatic class of a p-graph (in Russian), Diskret. Analiz 3 (1964), 25-30.
[13]	V. G. Vizing, Critical graphs with a given chromatic class (in Russian), Diskret. Analiz 5 (1965), 9-17.
[14]	H. P. Yap, Some Topics in Graph Theory, volume 108 of London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, 1986, doi:10.1017/cbo9780511662065.