Snarks, that is 2-connected cubic graphs admitting no 3-edge-colouring, provide a promising family of cubic graphs with respect to many widely-open conjectures. They are often constructed by joining several building blocks which can be regarded as cubic “graphs” with dangling edges allowed, formally called multipoles. Colouring properties of multipoles with at most ifve dangling edges relevant for constructions of snarks are almost completely characterised. The remaining uncharacterised class of such multipoles are so-called proper (2,3)-poles that can be obtained by severing an edge and removing a vertex from a snark. Therefore, in our work, we analyse the colouring properties of proper (2,3)-poles. To conduct our analysis, we explore using a computer all proper (2,3)-poles resulting from nontrivial snarks with at most 28 vertices. This encompasses a total of 3,247 snarks and 3,476,400 proper (2,3)-poles. In our research, we provide various structures that can be utilized to expand the colourability of proper (2,3)-poles. In the core of our work, we provide theorems regarding the colouring properties of proper (2,3)-poles, specifically necessary and suficient conditions for these properties. Additionally, we present the data and observations from the analysis.
[4], or the infinite family of flower snarks discovered by R. Isaacs [5]. The Isaacs snarks are denoted by , where The study of snarks, that is 2-connected cubic graphs is an odd integer ≥ 3. that are not 3-edge-colourable, is important since they Determining whether a given graph is a snark is an are smallest possible counterexamples for several open NP-complete problem [6]. However, when creating a problems. One such conjecture is the Cycle Double Cover cubic graph from some smaller building blocks, of which Conjecture stating that each bridgeless graph has a family we know their colouring properties, we also know the of cycles, such that each edge appears in exactly two colouring properties of the result. This may also include of the cycles. To exclude trivial cases, some additional if it is a snark or not. These building blocks are called mulproperties are required from snarks like the following. tipoles (e.g. see [2]) and can be described as an extended
Let be a cubic graph and an edge-cut of size . If at type of a graph that allows dangling edges. Multipoles least two components of − contain a cycle, is said to are useful for various constructions of snarks [3, 7] or be an n-edge-c-cut. Generally, these edge-cuts are called also for their structural analysis [8, 9]. c-cuts. A cubic graph is cyclically n-edge-connected This paper is structured as follows. First, we develop if there is no c-cut with less than edges. Cyclic edge- the theory needed for our work. In Section 2, we define connectivity of a cubic graph having at least one c-cut multipoles and all notions related to them, and in Secis the smallest number of edges of a c-cut of . Another tion 3, we develop the theory for describing colouring measurement of nontriviality is the girth of a graph properties of multipoles. Section 4 is specifically devoted which is the minimum length of a cycle in . If does to multipoles with five dangling edges while it explains not contain a cycle, we set the girth to ∞. the relation of proper (2,3)-poles to them. In Section 5,
Many authors (e.g. [1, 2]) require that snarks have we introduce several classes of proper (2,3)-poles with regirth at least 5 and are cyclically 4-edge-connected. We spect to their colouring properties. The rest of the paper call such snarks non-trivial and the remaining ones trivial. focuses on our results. Section 6 describes methods of On the other hand, some authors allow snarks to contain our computer-assisted analysis of proper (2,3)-poles conbridges [3]. structed from small non-trivial snarks. In Section 7, we
According to our definition, the Petersen graph is the provide multipoles that can be used to change colouring smallest snark and it satisfies every standard definition classes of proper (2,3)-poles. Section 8 contains theoretiof a snark. Other notable snarks are the Blanuša snarks cal results on colouring properties of proper (2,3)-poles. ITAT’23: Information technologies – Applications and Theory, Septem- At the end, in Section 9, we summarise the results of our ber 22–26, 2023, Tatranské Matliare, Slovakia computer-assisted analysis and in Section 10 we provide $ rehulka3@uniba.sk (E. Řehulka); jozef.rajnik@fmph.uniba.sk problems for further research. (J. Rajník) Definitions not provided in our work can be found in © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License [10]. We only clarify that all graphs considered in this CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) to . The partial junction of and is a junction of some semiedges (1 , · · · , ) and (1 , · · · , ), where ≤ and ≤ . In contrast to a normal junction of multipoles, which results in a graph, the partial junction can still result in a multipole.
Let be a graph, its edge, and its vertex. By severing the edge in , we mean removing and adding a dangling edge to the vertices and . Similarly, removing the vertex involves the removal of along with all of its incident edges, followed by adding a dangling edge to all of the formerly neighbouring vertices of . If we obtain a multipole by removing some vertices and severing some edges in a graph, there is a default way to divide the resulting semiedges into connectors. When we remove a vertex, all semiedges formerly incident with the vertex are in a new connector. Similarly, when we sever an edge, the two new semiedges are in a new connector.
To properly denote the multipoles resulting from a graph by removing some vertices and severing some edges, we will denote such multipoles as (; ; ), where is the former graph, is the set of removed vertices, and is the set of severed edges. For example, a multipole resulting from a snark by removing vertex and severing edge is denoted by (; {}; {}) and consists of two connectors, one with two semiedges and one with three. In the case where a set contains only one element, we can represent it without brackets, resulting in this case in the notation (; ; ). 1 3 2 work are undirected, and while we permit multiple edges, loops are not allowed. The distance between two vertices and in a graph , denoted by (, ), is defined as the length of a shortest path between and in . If no such path exists, we set (, ) = ∞. The distance (, ) between a vertex and an edge is defined as the smallest value between (, ) and (, ).
A multipole is a pair = (, ) of distinct finite sets of vertices and edges , where every edge ∈ has two edge ends, which may or need not be incident with a vertex. The concept of multipoles was introduced in [11].
A link is an edge incident with two distinct vertices and a dangling edge is an edge with only one end incident with a vertex. An illustration showcasing both types of edges can be seen in Figure 1: there is a link 12 and a dangling edge from 1. We do not consider other types 3. Multipole Colouring of edges. The edge ends not incident with any vertex are called semiedges. The semiedges in a multipole are When considering 3-edge-colourings it is convenient to endowed with a linear order and we denote the tuple of regard the colours 1, 2, 3 as (0, 1), (1, 0), (1, 1), respecits semiedges as ( ). tively. In other words, we use the set of non-zero ele
A multipole with ( ) = (1, · · · , ) can also ments of the group Z2 × Z2, which we will denote as K. be denoted as (1, · · · , ). In our work, we will con- Using the colours from K, it is easy to see that each 3sider cubic multipoles, i.e. multipoles where every vertex edge-colouring of cubic graphs corresponds to a nowhere is incident with precisely three edges. A multipole with zero (Z2 × Z2)-flow and vice versa. Since each non-zero semiedges is also called a n-pole. element from this group is self-inverse, we need not as
Usually, it is convenient to partite ( ) into pair- sign an orientation to the edges. wise disjoint tuples 1, · · · , called connectors. A These colourings are also called Tait colourings. These multipole with connectors 1, · · · , , where are widely used in many articles about snarks and 3has semiedges for each from 1 to , is denoted by edge-colourability in general mainly because of their (1, · · · , ) and is also called a (1, · · · , )-pole. relation to nowhere zero flows. From now on, we only
Now, we describe the process of joining two multipoles say colouring or colourable instead of 3-edge-colouring together. The junction of two distinct semiedges and or 3-edge-colourable. corresponding to edges ′ and ′, respectively, is a new When discussing multipoles, the definition of edgelink joining the remaining two edge ends of ′ and ′ colouring is the same. The colour of an edge end is the diferent from and . The junction of two connectors colour of its respective edge. The colouring set of a -pole = (1, · · · , ) and = (1, · · · , ) consists of (1, · · · , ) is the set Col( ) defined as individual junctions of semiedges and for from 1 {((1), · · · , ()) | is a Tait colouring of }. to . Similarly, the junction of two (1, · · · , )-poles (1, · · · , ) and (1, · · · , ) consists of individual junctions of connectors and , for from 1
For a connector = (1, · · · , ) of , the flow through is the value * () = ∑︀
=1 (). A connector of a multipole is called proper if * () ̸= 0 for each Tait colouring of . A multipole is called proper must have pairwise diferent colours. Also, the colouring if each of its connectors is proper. properties of 4-poles are already widely explored since
In general, for any tuple of semiedges = their colouring properties are limited as well [8]. The (1, · · · , ) and colouring , we use the notation () analysis of the colouring properties of 5-pole comes from to represent the tuple ((1), · · · , ()). the following ideas of P. J. Cameron, A. G. Chetwynd and
The fact that we can regard a colouring of a multi- J. J. Watkins [13]. pole as a flow has a valuable consequence that will be By the Parity Lemma, in each colouring of a 5-pole indispensable in our work. It is commonly known as the , three semiedges of have the same colour. We call Parity Lemma, introduced and proved by B. Descartes in these edges sociable in . The remaining two semiedges 1948. of , called solitary in , are coloured by the remaining two colours. Because the colouring set of is closed Lemma 1 (Parity Lemma [12]). Let be a -pole, and under a permutation of colours, it only matters which let 1, 2 and 3 be the numbers of semiedges of colour semiedges of may be solitary. Using this, we can (0, 1), (1, 0) and (1, 1), respectively. Then 1 ≡ 2 ≡ 3 visualize the colouring set of any 5-pole in the following mod 2. way.
For a 5-pole (1, 2, 3, 4, 5) we denote by a graph with the vertex set = {1, 2, 3, 4, 5}, in which for each , ∈ , the graph contains an edge if and only if the semiedges and are solitary in some colouring of . The graph is called the colouring graph of . The colouring graph of any 5-pole has no vertex of degree one [1]. We say that a 5-pole allows solitary cycle 12 · · · if its colouring graph contains the cycle 12 · · · .
From a case analysis in [1], it follows that if is a 5-pole that can be completed to a snark by performing a junction with some colourable 5-pole, then colouring graph of is a subgraph of:
By applying the Parity Lemma, we can conclude that any cubic graph with a bridge is not colourable. Another corollary of this lemma is that the minimum number of vertices that must be removed from a snark to obtain a colourable multipole is two [9]. The same applies to severing edges. The smallest number of edges to be severed in a snark to obtain a colourable multipole is two. If only one edge is severed, the resulting multipole contains two semiedges, both of which must have the same colour for it to be colourable because of the Parity Lemma. That would mean the former graph resulting from the junction of these two semiedges is not a snark since the colouring of the multipole could be extended to the colouring of the graph. • a 5-cycle, or
A key aspect when studying the colouring properties of multipoles derived from snarks is the removabil- • the graph formed by two disjoint triangles sharity of pairs of vertices or edges. Let be a snark. A ing a single vertex, or pair of its distinct vertices {, } is called removable if (; {, }; ∅) is not colourable; otherwise, it is called • the complement of 3. unremovable. Similarly, for edges, a pair of distinct Accordingly, 5-poles whose colouring graphs are subedges {, } is called removable if (; ∅; {, }) graphs of the mentioned graphs are called superpentagons, is colourable. Otherwise, it is called unremovable. negators and proper (2, 3)-poles, respectively. Note that
If we sever two adjacent edges, it is equivalent to the the introduced three classes of the 5-poles are not disremoval of a single vertex with regard to colourability. joint.
Therefore these pairs of edges are trivially removable because at least two vertices are needed to be removed from a snark to obtain a colourable multipole.
empty or the 5-cycle. The colouring graph of a negator is empty, consists of one triangle or consists of two edge-disjoint triangles with a common vertex. 4. Colouring properties of 5-poles Máčajová and Škoviera characterised which negators have which colouring graphs [3]. For proper (2, 3)-poles, To explore multipoles efectively, it is best to start with the situation is more diverse and their colouring graphs the simplest ones and gradually move towards more com- have not been studied yet. plex ones. That’s why we begin by examining the -poles starting from the smallest . Specifically, the smallest 5. Proper (2,3)-poles for which it is interesting to explore the colourability of -poles arising from snarks with -edge-cuts is 4. As it follows from the definitions in Section 2, a proper The 1-poles are trivially uncolourable. For a 2-pole to (2, 3)-pole (, ) is a multipole having two proper be colourable, both of its semiedges must have the same colour. Similarly, for a 3-pole, all three of its semiedges connectors = (1, 2) and = (1, 2, 3). Therefore, the colouring set of each proper (2,3)-pole is a subset of the set
colourable and therefore not a snark, which contradicts
We will refer to this set only as from now on. Note the assumption. tchoalotuirns othfitshederefinsiptieocnti,vtehsee mteiremdgses.T1hteono3n-deeqnuoatleitythtoe of Tphroispemre(a2n,3s)-tphoerleesa,rwehoinclhyc1a2ndbieferdeinvtidceodloiunrtiongclsaestsses zero is evident because they are proper, and the equality in the following way. We denote the classes by a numof flow through both connectors follows from the Parity ber representing how many vertices from {1, 2, 3} lemma. are connected to {1, 2} with an edge in the colouring
This property implies that each proper (2, 3)-pole graph, followed by A if the colouring allows an edge can be completed to a snark by the junction of the between 1 and 2, or B otherwise. Resulting are six semiedges in the connector of size two and joining the colouring classes: 0B (uncolourable), 1A, 2B, 2A, 3B and semiedges from the connector of size three to a new ver- 3A. Proper (2,3)-poles from Class 3A, that is those whose tex. Conversely, for each snark, the result after removing colouring set coincides with , are also called perfect. a vertex and severing an edge not incident with it will For each of them we have found an example, in this aralways be a proper (2,3)-pole [9]. ticle we provide an example of an uncolourable proper A visualisation of this process can be seen in Figure 2. (2,3)-pole in Figure 3 resulting from the second Blanuša Now, we describe all possible colouring sets of proper snark and a perfect one in Figure 4 resulting from the (2,3)-poles on their colouring graphs. Since there is no Petersen graph.
The colouring graphs for each class can be observed rule on which semiedges are labelled 1, 2, 3 after removing a vertex from a snark, we will divide the colour- in Figure 5. ing sets into classes, in which the colouring sets represent colourings up to a permutation of colours and a permu- 6. Methods of Analysis tation of labels 1, 2, 3.
However, not each graph on these vertices represents All of the results in this chapter come from our analysis a possible colouring set. First, the colouring graph must conducted on several proper (2,3)-poles. For this reason, have no pendant vertex, as mentioned above. The second we have created a simple program in C++ that helps us restriction is that no edge is between two vertices from get the desired results. The logic behind representing {1, 2, 3}. Suppose there was an edge between 1 and graphs in the program and some basic operations on 2 in some proper (2,3)-pole . This would mean that them is done by the ba_graph library [14]. As input, allows a colouring such that 1, 2 and 3 have pairwise our program receives a list of snarks in graph6 format diferent colours and 1, 2 have the same colour. Thus [15], parses them, and performs the following operations could be extended to the former graph, which would be on each. 2 2 1 1 1 2 2 1 1 1 2 2 1 1 1 1 1 1 3 3 2 2
from a snark by removing one vertex and severing one edge, this is exactly what the program does: for each vertex and edge , where is not incident with , it It may be convenient to modify some proper (2,3)-poles removes , severes , and thus creates a proper (2,3)-pole. by adding some vertices and edges to obtain perfect Thus, we have multiple proper (2,3)-poles from one snark. proper (2,3)-pole. If we know in which colouring class
Let be the proper (2,3)-pole resulting from snark , the proper (2,3)-pole is, then we can make a junction after removing the vertex and severing the edge , with the specific constructions provided in this chapter ̸= ̸= ̸= . We compute or observe the following to obtain perfect colouring, of course, only if the former properties for each proper (2,3)-pole: (2,3)-pole is colourable. 7. Obtaining perfect proper (2,3)-poles • the resulting multipole in graph6 format; • which edge and vertex were removed from the
former snark; • in which colouring class it is (see Section 5); • the distance between the removed vertex and sev
ered edge; • how many pairs of vertices from {, }, {, }
are removable; • how many pairs of edges {, }, {, }, {, } are removable, where , and are neighbours of .
tipole permits four colourings: those in which the solitary semiedges are 1 and 1, 1 and 2, 1 and 3, and 1 and 2, respectively. For instance, if it allows a colouring where the solitary semiedges are 1 and 1, it also allows a colouring with the solitary semiedges 2 and 1.
The sets of removable pairs of edges and vertices are computed for the original snark, and then for the resulting multipole it is simply checked whether those pairs are contained in the respective sets.
For each graph on input, these results are then saved in a separate file containing a row for each proper (2,3)-pole originating from it.
The source code of the program can be found at [16].
Let (, ) be a proper (2,3)-pole, whose colouring class is 1A and let it allow a solitary cycle 12 for some ∈ . Now let ′(, ′), ′ = (′1, ′2, ′3) be a proper (2,3)-pole obtained by the partial junction of with the 6-pole shown in Figure 6. In this partial junction we connect the connector and the connector (1, 2, 3) such that it contains a junction of and 1. We prove that the result is a proper (2,3)-pole from colouring class 2B, which allows solitary cycle ′21′32.
Without loss of generality, let the semiedge be 1. Let this colouring of be . Using a colouring 1 of where 1(′1, ′2, ′3) = (3, 3, 2) and a colouring 2 of where 2(′1, ′2, ′3) = (3, 2, 3), in both cases 1(1, 2, 3) = 2(1, 2, 3) = (2, 1, 1). After the mentioned partial junction of and , we can colour the rest of ′ by the colouring . We can see that the colouring graph of ′ allows a solitary cycle ′21′32. No more colourings can be obtained since, as it can be seen, ′2 and ′3 must have diferent colours, so one of them is always solitary and we cannot obtain classes 2, 3, and perfect.
It is the smallest such 6-pole, considering the number of vertices, which extends class 1A to 2B. 1 2 3 ′ 1 ′ 2
is a submultipole of , denoted by ⊆ if a multipole exists such that is a partial junction of and .
It must be noted that this construction produces proper (2,3)-poles which may not be contained in a nontrivial snark, since it contains a quadrilateral. If we would need to extend some proper (2,3)-pole to obtain a specific colouring class and require the extended proper (2,3)-pole to be contained in a nontrivial snark, we would need to use other, more complex constructions.
To extend a proper (2,3)-pole from the colouring class 2A to a perfect one, the same 6-pole can be used as before, just with a diferent junction. Let (, ) be a proper (2,3)-pole whose colouring class is 2B. Let , , ̸= be the two semiedges from , for which there exists a solitary cycle 121 2. Now let ′(, ′), ′ = {′1, ′2, ′3} be a proper (2,3)-pole obtained by the junction of with the 6-pole in Figure 7 by the junction of semiedges to 2, to 3 and the last semiedge to 1. The result ′ is a perfect proper (2,3)-pole, which can be proved similarly to before.
extended to it by adding vertices, edges and semiedges and connecting them. The following lemma applies to the colourings of submultipoles; thus is essential when proving some propositions in this chapter.
Proof. Since ⊆ , so is a result of the junction of and some multipole , there is an edge cut splitting into and . Let be the colouring of . After removing the edge cut , the exact colouring can be applied to colour .
colourable as well.
Let and be multipoles, both constructed from a snark . Since we often consider the intersection ( ) ∩ ( ), we clarify that: • A link of is included in the intersection if and only if it is present in both multipoles. • A dangling edge originating from a vertex which originated from an edge of is included in the intersection if and only if it is present in both multipoles.
Since when creating a proper (2,3)-pole from a snark, we are removing a vertex and severing an edge, we cannot look at the removable vertices per se since only one vertex is removed. However, we may look at the end vertices of the severed edge. {, } is removable, is uncolourable, leading to a contradiction.
Proposition 1. Let be a snark, its vertex, its edge where ̸= and ̸= and (, ) a proper (2,3)-pole (; ; ). If at least one of the pairs {, } and {, } is removable, then (, ) is uncolourable.
Proof. Let the removable pair be {, }, meaning that (; {, }; ∅) is uncolourable. We see that (; {, }; ∅) ⊆ (, ), so because of Lemma 2 the proper (2,3)-pole (, ) is uncolourable.
Lemma 3. Let be a snark, its vertex, its edge where ̸= and ̸= . Let , , be the neighbouring vertices of in . It is not possible that exactly two of the pairs
It must be noted, though, that the converse impli- {, }, {, }, {, } are removable. cation does not hold. There are several uncolourable proper (2,3)-poles, resulting from a snark, in which both of the pairs of vertices are unremovable. One of them is the mentioned example in Figure 3.
Another interesting attribute in the question of colourability is the edge removability. Since the removed vertex in the creation of a proper (2, 3)-pole has three neighbours, we can look at the removability of all three in pairs, along with the severed edge in the creation.
One interesting proposition is also connected to the uncolourable proper (2,3)-poles.
then at least one of the remaining pairs is unremovable as well. Let {, } be unremovable, meaning that = (; ∅; {, }) is colourable, let the colouring be .
Let 1, 2 be the semiedges resulting from severing the edge and 1, 2 from severing , such that 1 is part of the edge from and 2 of the edge from . Because of the Parity Lemma and the fact that is a snark, 1 must have a diferent colour than 2, and 1, 2 must be coloured with the same colours as them, also diferent from each other. The colours in of edges incident with Proposition 2. Let be a snark, its vertex, its edge are all diferent, meaning that one of the edges, say , where ̸= and ̸= and (, ) a proper (2,3)-pole is coloured by the same colour as 1. It cannot be the (; ; ). Let , , be the neighbouring vertices of dangling edge, since (1) ̸= (2). in . (, ) is uncolourable if and only if all three pairs Now we can colour ′ = (; ∅; {, }) with a {, }, {, }, {, } are removable. colouring ′. For each edge ∈ () ∩ (′), ′() = (). The only edges from ′ not in this intersection are Proof. Suppose on the contrary that (, ) is un- the edge , the dangling edge from and the dangling colourable and at least one pair from {, }, {, }, edge from . Let us denote the dangling edges by , , {, } is unremovable, say {, }. This means that respectively. We will colour them the following way: (; ∅; {, }) is colourable. However, (, ) is ′() = (1), ′() = (), ′() = (2). Since a submultipole of (; ∅; {, }) and since (, ) (1) ̸= (2), all three colours of edges incident with is uncolourable, (; ∅; {, }) must also be un- in ′ will indeed be diferent. This means, that the pair colourable because of Lemma 2, leading to a contradic- {, } is also unremovable. tion. Therefore, if (, ) is uncolourable, all three The statement that exactly two of the pairs pairs {, }, {, }, {, } are removable. {, }, {, }, {, } are removable is equivalent
Now for the proof of the second implication, suppose to the statement that exactly one of them is unremovable. that all three edge pairs are removable and (, ) is However, we have proved that this is impossible, colourable. Let the semiedge 1 be from the dangling since the presence of an unremovable pair implies the edge from , 2 from and 3 from . By the defi- existence of another unremovable pair. nition of colouring classes, it is evident that (, ) must allow a colouring, among others, where the soli- Proposition 3. Let be a snark, its vertex, its tary semiedges are 1 and some semiedge , say 1. It edge where ̸= and ̸= and (, ) a proper is now possible to use this colouring, say , to colour (2, 3)-pole (; ; ). Let , , be the neighbouring (; ∅; {, }). Let us denote (; ∅; {, }) by vertices of in . The proper (2,3)-pole (, ) is . We define a colouring ′ of as follows: For each from the class 1A if and only if exactly one of the pairs edge ∈ () ∩ ( (, )), the colour ′() is equal {, }, {, }, {, } is removable. to (). The only edges not in this intersection are , and the dangling edge from , let us denote it by . We Proof. Suppose that (, ) is from the class 1 and can set ′() = (1), ′() = (3). These two not exactly one of the pairs {, }, {, }, {, } colours are diferent, since in , the semiedge 1 is soli- is removable. If all three pairs were removable, then tary and 3 sociable. Thus we can colour the last edge, , by Proposition 2, (, ) would be uncolourable. Also, with the colour diferent from ′() and ′(). Since there cannot be exactly two removable, as we have proved in Lemma 3. That means we can only explore the cases where none of the pairs is removable. Let the semiedge and the dangling edge from , let us denote it as . We 1 be from the dangling edge from , 2 from and 3 can then set () = 3(2), () = 3(3) and from . () as the other colour from the two colours already
Let (, ) allow a solitary cycle 112, implying set for and . Since {, } is removable, the asit allows a colouring where the solitary semiedges are 1 sumption that 3 is in the solitary cycle also leads to a and 1. Therefore (, ) does not allow a colouring contradiction. where one of the solitary semiedges is 2 or 3. Because (, ) is colourable and as we have shown,
Let = (; ∅; {, }) and let us denote the 2 and 3 cannot be in its solitary cycle, it must contain semiedges resulting from severing the edge by 1, 2, 1, implying the existence of colouring where the solitary such that 1 is part of the dangling edge from and 2 of pairs are 1, 2; 1, 1; 2, 2; which coincides with the the dangling edge from . Since each pair is unremovable, colouring class 1A. a colouring of exists. We see that () ̸= () and (, ) is a submultipole of . We can now con- Based on this we can provide an interesting corollary struct a colouring ′ of (, ) the following way. For for the other classes, implied by Proposition 2, Lemma 3 each edge ∈ ( (, )) ∩ (), ′() = (). The and Proposition 3. only edges from (, ) not in this intersection are the Corollary 1. Let be a snark, its vertex, its edge dangling edges containing 2 and 3. We will colour where ̸= and ̸= and (, ) a proper (2, 3)-pole them with ′(2) = () and ′(3) = (). How- (; ; ). Let , , be the neighbouring vertices of in ever, since () ̸= (), the colour of 2 is diferent . (, ) is perfect or from the class 2A, 2B or 3B, if and from the colour of 3, thus one of them is solitary in this only if all three of the pairs {, }, {, }, {, } colouring along with 1 or 2. This leads to a contra- are unremovable. diction, since we suppose that (, ) does not allow a colouring where one of the solitary semiedges is 2 or 3.
Proposition 4. Let be a snark, its vertex, its edge where ̸= , ̸= and the distance between and is 1, that means or is a neighbour of . Let (, ) be a proper (2, 3)-pole (; ; ). Then (, ) is either uncolourable or its colouring set is from the class 1A.
Now we can prove the second implication. Assume that exactly one of the pairs {, }, {, }, {, } is removable, let it be {, }, meaning that the pairs {, } and {, } are unremovable. As in the proof of the previous implication, let the semiedge 1 be from Proof. Since the distance between and is 1, at least the dangling edge from , 2 from and 3 from . Based one of the vertices , is the neighbour of ; let it be on Proposition 2, (, ) is colourable, so we can ex- . Now there are two dangling edges from the vertex plore which semiedges from 1, 2, 3 can be in its soli- ; let their semiedges be 1 and 1. Because of this, tary cycle. in each colouring of (, ), the colours of 1 and 1
Suppose 2 is in the solitary cycle of (, ), imply- are diferent. This means that (, ) does not allow ing the existence of a colouring 2 in which the soli- colourings where the solitary semiedges are 2 with 2, tary semiedges are 1 and 2. This would mean that or 2 with 3. It is evident that the only possible colouring 2(2) ̸= 2(1), 2(2) ̸= 2(3), 2(1) = 2(3). classes are 1A and uncolourable.
From this colouring we can now construct a colouring of = (; ∅; {, }): for each edge ∈ 9. Data and observations () ∩ ( (, )) the colour will be () = 2().
The only edges from not included in the intersection To clarify how we got the propositions or how the data are , and the dangling edge from , let us denote it as looks, we provide statistics about the explored snarks . We can then set () = 2(2), () = 2(3) and their resulting proper (2,3)-poles. In Table 1 is an and () as the remaining colour, diferent from the two example of the output table for the Petersen graph. colours already set for and . Since {, } is re- As an input, we have used all non-trivial snarks with movable, the assumption that 2 is in the solitary cycle at most 28 vertices, which is 3,247 snarks. There are leads to a contradiction. precisely 3,476,400 proper (2,3)-poles resulting from them.
Now suppose 3 is in the solitary cycle of (, ), Most of these results are perfect proper (2,3)-poles. The implying the existence of a colouring 3 in which the proportions are in Table 2. solitary semiedges are 1 and 3. This would mean that By analyzing proper (2,3)-poles, we found that 8.59% 3(3) ̸= 3(1), 3(3) ̸= 3(2), 3(1) = 3(2). of them are uncolourable, while 91.41% are colourable. From this colouring we can now also construct a colour- Based on Corollary 1 and its converse implication, we ing of as before: for each edge ∈ () ∩ examined the distribution of colouring classes when all of ( (, )) the colour will be () = 3(). The only the mentioned pairs are unremovable. This analysis led edges from not included in the intersection are , to the observations presented in Table 3. We see that most ... of the proper (2,3)-poles are perfect, but the numbers are also the same as in Table 2. The equivalence between all proper (2,3)-poles from the classes perfect, 2B, 3B and 2A; and having all three pairs of edges unremovable is proved in Corollary 1. no pair of removable vertices. Such snarks are called bicritical.
Since removable pair of vertices afect colouring properties, we have explored all bicritical snarks with at most 32 vertices – precisely 278 of them. There are 306,396 proper (2,3)-poles resulting from them. The proportions of their colouring classes is in Table 5.
class perfect
1A uncolourable 2A 3B 2B percentage
total number
ing classes, but only for the proper (2,3)-poles with all three of the mentioned edge pairs unremovable. The Table 3 results are in Table 6. We see, that almost every such Proportion of colouring classes for all three unremovable pairs proper (2,3)-pole is perfect, however there is a small numof edges. ber of ones from the classes 2A, 3B, 2B. This may be an interesting observation for the further research about the suficient conditions for a proper (2,3)-pole resulting
Another interesting observation is that no proper (2,3)- from a bicritical snark to be perfect. However, a proper pole from the explored ones has precisely two of the (2,3)-pole constructed from a bicritical snark is not always mentioned pair of edges removable. We have proved this perfect. in Lemma 3. The proportions can be seen in Table 4 removable edges percentage
total number
only colourable proper (2,3)-poles. One is the Petersen graph, then one with 20 vertices, two with 22 and one with 28 vertices. The ones with 20 and 28 vertices are the Isaacs snarks 5 and 7 respectively. The two snarks with 22 vertices are the Loupekine snarks. Because of Proposition 1, each of the five mentioned snarks contains class perfect 2A 3B 2B percentage
total number 99.6% 0.4% < 0.01% < 0.01% 10. Problems
Problem 1. Suppose we only consider multipoles re- [3] E. Máčajová, M. Škoviera, Irreducible snarks of sulting from snarks by severing an edge and removing given order and cyclic connectivity, Discrete Matha vertex with a distance of more than 1, since adjacent ematics 306 (2006). doi:10.1016/j.disc.2006. edges are trivially removable. Is a proper (2,3)-pole con- 02.003. structed from a snark without any removable pair of [4] D. Blanuša, Problem četiriju boja, Glasnik Mat. edges always perfect? Fiz. Astr. Ser. II (Hrvatsko Prirodoslovno Društvo) 1 (1946).
There are only four such snarks from the ones we have [5] R. Isaacs, Infinite families of nontrivial trivalent explored: the Petersen graph, the Isaacs snarks 5 and 7, graphs which are not tait colorable, The Ameriand the Double Star snark. All of the proper (2,3)-poles can Mathematical Monthly 82 (1975). doi:10.2307/ resulting from these graphs, with the distance between 2319844. the removed vertex and the severed edge more than 1 [6] I. Holyer, The NP-completeness of edge-coloring, are indeed perfect. However we have not proved this SIAM Journal on Computing 10 (1981). URL: https: statement, thus it can be explored in further research. //doi.org/10.1137/0210055. doi:10.1137/0210055. Problem 2. Construct multipoles used to extend colour- arXiv:https://doi.org/10.1137/0210055. ings of proper (2,3)-poles, which allow the resulting [7] R. Lukoťka, E. Máčajová, J. Mazák, M. Škoviera, proper (2,3)-poles to be contained in a nontrivial snark. Small snarks with large oddness, Electron. J. Comb. 22 (2015) 1. URL: https://doi.org/10.37236/
As mentioned in Section 7, one of the 6-poles contains 3969. doi:10.37236/3969. a quadrilateral, so each snark of which it is a part of is [8] M. Chladný, M. Škoviera, Factorisation of snarks, trivial. Electronic Journal of Combinatorics 17 (2010). doi:10.37236/304.
Problem 3. Construct an infinite family of snarks, that [9] J. Mazák, J. Rajník, M. Škoviera, Morphology of produce only colourable proper (2,3)-poles. small snarks, Electronic Journal of Combinatorics
We have found several snarks producing only 29 (2022). doi:10.37236/10917. colourable proper (2,3)-poles: the Petersen graph, the [10] R. Diestel, Graph Theory, volume 173 of Graduate Isaacs snarks 5 and 7 and the two Loupekine snarks Texts in Mathematics, fourth ed., Springer, Heidelof order 22. This may be helpful when exploring infi- berg; New York, 2010. nite families of snarks producing only colourable proper [11] M. A. Fiol, A boolean algebra approach to the (2,3)-poles. construction of snarks, Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, Problem 4. If we construct a proper (2,3)-pole from a 1988) (1991). bicritical snark in such a way, that the distance between [12] B. Descartes, Network-colourings, The Mathematithe severed edge and the removed vertex is more than cal Gazette 32 (1948). doi:10.2307/3610702. one, and both are a part of a 5-cycle (not necessarily the [13] P. J. Cameron, A. G. Chetwynd, J. J. Watkins, Desame), is the result always perfect? composition of snarks, Journal of Graph Theory 11 (1987). doi:10.1002/jgt.3190110104.
If a counterexample is found, an additional require- [14] R. Lukoťka, Ba-graph, Bitbucket, 2022. URL: https: ment of being cyclically 5-edge-connected could be im- //bitbucket.org/relatko/ba-graph/src/master/, reposed for the snark. trieved March 28, 2023, available at: https:// bitbucket.org/relatko/ba-graph/src/master/.
References [15] B. McKay, Description of graph6, sparse6 and digraph6 encodings, Online, 2015. Retrieved April [1] M. Preissmann, C-minimal snarks, in: C. Berge, 13, 2023, available at: http://users.cecs.anu.edu.au/ D. Bresson, P. Camion, J. F. Maurras, F. Sterboul ~bdm/data/formats.txt. (Eds.), Combinatorial Mathematics, volume 75 of [16] E. Řehulka, Proper (2,3)-poles analysis, Github, North-Holland Mathematics Studies, North-Holland, 2023. URL: https://github.com/erehulka/ 1983. URL: https://www.sciencedirect.com/science/ proper-2-3-poles, retrieved August 9, 2023, article/pii/S0304020808734340. doi:https://doi. available at: https://github.com/erehulka/ org/10.1016/S0304-0208(08)73434-0. proper-2-3-poles. [2] R. Nedela, M. Škoviera, Decompositions and reductions of snarks, Journal of Graph Theory 22 (1996). doi:10.1002/(SICI)1097-0118(199607)22: 3<253::AID-JGT6>3.0.CO;2-L.