1 Introduction
In this paper, we consider finite, undirected graphs. They do not contain loops, though they may contain parallel edges. We also consider pseudographs, which may contain both loops and parallel edges, and simple graphs, which contain neither loops nor parallel edges. As usual, a loop contributes to the degree of a vertex by two.
Within the frames of this paper, we assume that graphs, pseudographs and simple graphs are considered up to isomorphisms. This implies that the equality means that and are isomorphic.
For a graph , let and be the set of vertices and edges of , respectively. Moreover, let be the set of edges of that are incident to the vertex of . A matching of is a set of edges of such that any two of them do not share a vertex. A matching of is perfect, if it contains edges. A block of is a maximal connected subgraph of . An endblock is a block of containing at most one vertex that is a cutvertex of . A subgraph of is even, if every vertex of has even degree in . A subgraph
is odd, if every vertex of
has odd degree in . Sometime, we will refer to odd subgraphs as joins. Observe that a perfect matching is a join of a cubic graph. A subgraph is a parity subgraph if for every vertex of and have the same parity. Observe that is a parity subgraph of if is an even subgraph of .If is a cubic graph, and is a triangle in , then one can obtain a cubic pseudograph by contracting . We will denote this pseudograph by . If is a graph, we will say that is contractible. Observe that if is not contractible, two vertices of are joined with two parallel edges, and the third vertex is incident to a bridge (see the endblocks of the graph from Figure 2). If is a contractible triangle, and is an edge of , then let be the edge of that is incident to a vertex of and is not adjacent to . and will be called opposite edges.
Let and be two cubic graphs. An coloring of is a mapping , such that for each vertex of there is a vertex of , such that . If admits an coloring, then we will write . It can be easily seen that if and , then . In other words, is a transitive relation defined on the set of cubic graphs.
If and is an coloring of , then for any adjacent edges , of , the edges , of are adjacent. Moreover, if the graph contains no triangle, then the converse is also true, that is, if a mapping has a property that for any two adjacent edges and of , the edges and of are adjacent, then is an coloring of .
Let be the wellknown Petersen graph (Figure 2) and let be the graph from Figure 2. is called the Sylvester graph Schrijver . We would like to point out that usually the name “Sylvester graph” is used for a particular strongly regular graph on vertices, and this graph should not be confused with , which has vertices.
The Petersen coloring conjecture of Jaeger states:
Conjecture 1
(Jaeger, 1988 Jaeger ) For any bridgeless cubic graph .
Sometimes, we will call this conjecture as conjecture. The conjecture is difficult to prove, since it can be seen that it implies the following classical conjectures:
Conjecture 2
(Berge, unpublished) For any bridgeless cubic graph .
Here is the smallest number of perfect matchings that are needed to cover the edgeset of
Conjecture 3
This list of six perfect matchings usually is called a BergeFulkerson cover of .
Conjecture 4
((5, 2)evensubgraphcover conjecture, Celmins1984 ; Preiss1981 ) Any bridgeless graph (not necessarily cubic) contains five even subgraphs such that any edge of belongs to exactly two of them.
Related with the Jaeger conjecture, the following conjecture has been introduced in PetersenRemark :
Conjecture 5
(V. V. Mkrtchyan, 2012 PetersenRemark ) For any cubic graph .
In direct analogy with the Jaeger conjecture, we call Conjecture 5 the Sylvester coloring conjecture or just conjecture.
A edgecoloring is an assignment of colors to edges of a graph from a set of colors such that adjacent edges receive different colors. The smallest for which a graph admits a edgecoloring is called a chromatic index of and is denoted by . If is a edgecoloring of a cubic graph , then an edge is called poor (rich) in , if the five edges of incident to or are colored with three (five) colors. is called a normal edgecoloring of if any edge of is either poor or rich in . Observe that not all cubic graphs admit a normal edgecoloring for some . An example of such a graph is the Sylvester graph (Figure 2). On the positive side, all simple cubic graphs admit a normal edgecoloring NormalCubics7 . The smallest (if it exists) for which a cubic graph admits a normal edgecoloring is called a normal chromatic index of and is denoted by .
Normal colorings were introduced by Jaeger in Jaeger1985 , where among other results, he showed that for a cubic graph if and only if admits a coloring. This allowed him to obtain a reformulation of Conjecture 1, which states that for any bridgeless cubic graph .
In this paper, we introduce two new conjectures that are related to Conjectures 1 and 5. In section 2, we discuss some auxiliary results that will be useful later in the paper. In section 3, we briefly discuss socalled hereditary classes of cubic graphs that allowed us to come up with these two new conjectures. Then in section 4, we present our main results. Finally, in section 5, we discuss some open problems. Terms and concepts that we do not define in the paper can be found in West ; Zhang1997 .
2 Auxiliary results
In this section, we present some auxiliary results that will be useful later. Our first result is a lemma about some properties of colorings of cubic graphs. Though all these properties are known before, for the sake of completeness we give complete proofs.
Lemma 1
Suppose that and are cubic graphs with , and let be an coloring of . Then:

If is any matching of , then is a matching of ;

;

If is a perfect matching of , then is a perfect matching of ;

;

If admits a BergeFulkerson cover, then also admits a BergeFulkerson cover;

For every even subgraph of , is an even subgraph of ;

For every bridge of , the edge is a bridge of .

If is bridgeless, then is bridgeless as well;

.
Proof: (a) The proof of this statement follows from the definition of coloring: as adjacent edges of must be colored with adjacent edges of , then clearly the preimage of a matching in must be a matching in .
(b) Assume that and let be the color classes of in an edgecoloring. Consider ,…,. Observe that due to (a), they are forming matchings covering the edgeset of . Thus, .
(c) Let be a perfect matching of . Then by (a), is a matching of . Let us show that it covers all vertices of . Let be a vertex of . Then the three edges incident to are colored by a similar three edges of . Since is a perfect matching of , one of these three edges must belong to , hence . Thus, is a perfect matching of .
(d) The proof of this is similar to that of (b): let and let be the perfect matchings of covering . Consider ,…,. Observe that due to (c), they are forming perfect matchings covering the edgeset of . Thus, .
(e) Let be a BergeFulkerson cover of . Consider the list . Observe that due to (c) they are forming a list of six perfect matchings of . Moreover, every edge of belongs to at least two of these perfect matchings. Hence is a BergeFulkerson cover of .
(f) Let be an even subgraph of . Let us show that any vertex of has even degree in . Since is cubic, is a disjoint union of cycles. Assume that in the three edges incident to are colored with three edges incident to a vertex of . Then if is isolated in , then clearly is isolated in . On the other hand, if has degree two in , then is of degree two in . Thus, always has even degree in , or is an even subgraph of .
(g) Let be a bridge of and let be a partition of , such that . Assume that the edge is not a bridge in . Then there is a cycle in that contains the edge . By (f) is an even subgraph of that has nonempty intersection with . Since the intersection of an even subgraph with always contains an even number of edges, we have that contains at least two edges which contradicts our assumption.
(h) This follows from (g): if has no a bridge, then any edge of cannot be a bridge, as otherwise its color in will be a bridge in .
(i) Assume that , and let be a normal edgecoloring of . Consider a mapping defined on the edgeset of as follows: for any edge of , let . Let us show that is a normal edgecoloring of . Let be any edge of . Assume that in the three edges incident to are colored by the three edges incident to a vertex of , the three edges incident to are colored by the three edges incident to a vertex of .
If , then the edge is poor in . Thus, we can assume that . Since , we have that and . Now, observe that since is a normal edgecoloring, we have that if is a poor edge in , then is a poor edge in , and if is a rich edge in , then is a rich edge in . Thus, is a normal edgecoloring of . Hence . The proof of the lemma is complete.
We will need some results on clawfree bridgeless cubic graphs. Recall that a graph is clawfree, if it does not contain vertices, such that the subgraph of induced on these vertices is isomorphic to . In ChudSeyClawFreeChar , arbitrary clawfree graphs are characterized. In sangil_oum:2011 , Oum has characterized simple, clawfree bridgeless cubic graphs. In order to formulate Oum’s result, we need some definitions. In a clawfree simple cubic graph any vertex belongs to , , or triangles. If a vertex belongs to triangles of , then the component of containing is isomorphic to (Figure 3). An induced subgraph of that is isomorphic to is called a diamond sangil_oum:2011 . It can be easily checked that in a clawfree cubic graph no diamonds intersect.
A string of diamonds of is a maximal sequence of diamonds, in which has a vertex adjacent to a vertex of , . A string of diamonds has exactly vertices of degree , which are called the head and the tail of the string. Replacing an edge with a string of diamonds with the head and the tail is to remove and add edges and .
If is a connected clawfree simple cubic graph such that each vertex lies in a diamond, then is called a ring of diamonds. It can be easily checked that each vertex of a ring of diamonds lies in exactly diamonds. As in sangil_oum:2011 , we require that a ring of diamonds contains at least diamonds.
Proposition 1
(Oum, sangil_oum:2011 ) is a connected clawfree simple bridgeless cubic graph, if and only if

is isomorphic to , or

is a ring of diamonds, or

there is a connected bridgeless cubic graph , such that can be obtained from by replacing some edges of with strings of diamonds, and by replacing any vertex of with a triangle.
The next auxiliary result allows us to relate coverings with even subgraphs to coverings with specific parity subgraphs.
Theorem 1
(Theorem 3.3 in CQJoins ) For a graph , the following two conditions are equivalent:

contains five even subgraphs such that any edge of belongs to exactly two of them;

contains four parity subgraphs such that each edge belongs to either one or two of the parity subgraphs.
Conjecture 2 implies that for any clawfree bridgeless cubic graph . We are unable to find an example attaining this bound. We suspect that:
Conjecture 6
For any clawfree bridgeless cubic graph .
Our final auxiliary result is a theorem proved by Giuseppe Mazzuoccolo which offers a new reformulation of Conjecture 4.
Proof: Assume that Conjecture 6 is true. Let us show that Conjecture 4 is also true. It is known that it suffices to prove Conjecture 4 for cubic graphs Zhang1997 . Let be an arbitrary bridgeless cubic graph. Consider the cubic graph obtained from by replacing every vertex of with a triangle. Observe that is a clawfree bridgeless cubic graph. By Conjecture 6, the edgeset of can be covered with four perfect matchings. Observe that perfect matchings are parity subgraphs in cubic graphs, hence by Theorem 1, admits a list of even subgraphs covering each edge exactly twice.
In order to complete the proof, let us observe that if a cubic graph admits a list of even subgraphs covering each edge exactly twice and it contains a triangle , then the graph also admits a list of even subgraphs covering each edge exactly twice. In order to see this, let be the list of even subgraphs covering the edges of twice. Then it is easy to see that the edges of the cut are covered as follows: first edge belongs to and , the second edge belongs to and , and finally the third edge belongs to and . Moreover, and do not intersect the cut. One can always achieve this by renaming the even subgraphs. Now, if we consider the restrictions of to , we will have that they are forming a list of even subgraphs covering each edge of exactly twice.
Applying this observation times to , we will get the statement for the original cubic graph .
For the proof of the converse statement, let us assume that Conjecture 4 is true, and show that any clawfree bridgeless cubic graph can be covered with four perfect matchings. We prove the latter statement by induction on . If , the the statement is trivially true. Assume that it is true for all clawfree bridgeless cubic graphs with less vertices and let us consider a clawfree bridgeless cubic graph with vertices.
Clearly, we can assume that is connected. Let us show that we can assume that is simple. On the opposite assumption, consider the vertices and that are joined with two edges. Let and be the the other neighbors of and , respectively. Consider a cubic graph obtained from by adding a possibly parallel edge . Observe that is a bridgeless cubic graph with . Moreover, it is clawfree. Thus, by induction hypothesis, can be covered with four perfect matchings. Now, it is easy to see that using these list of four perfect matchings of we can construct a list of four perfect matchings of covering .
Thus, without loss of generality, we can assume that is simple. Hence, we can apply Proposition 1. If meets the first or the second condition of the proposition, then it is easy to see that is edgecolorable, hence it can be covered with three perfect matchings. Thus, we can assume that there is a connected bridgeless cubic graph such that can be obtained from by replacing some edges of with strings of diamonds and every vertex of with a triangle.
Let us show that we can also assume that has no string of diamonds. Assume it has one. Let it be whose head and tails are and , respectively. Let and be the neighbors of and , respectively, that lie outside . Consider a graph obtained from by adding a possibly parallel edge . Observe that is a bridgeless cubic graph with . Moreover, it is clawfree. Thus, by induction hypothesis, can be covered with four perfect matchings. Now, it is easy to see that using these list of four perfect matchings of we can construct a list of four perfect matchings of covering .
Thus, without loss of generality, we can assume that can be obtained from the connected bridgeless cubic graph by replacing its every vertex with a triangle. By Conjecture 4, has a list of five even subgraphs covering its edges exactly twice. By Theorem 1, we have that admits a cover with four joins such that each edge of is covered once or twice. Let any vertex of and let be the cover of with four joins. Since each edge of is covered once or twice in , we have that there is at most one join in that contains all three edges incident to . Thus, for any vertex we have that either one of joins contains all three edges incident to and the other three joins contain exactly one edge incident to , or all joins contain exactly one edge incident to . Now, it is not hard to see that these four joins covering can be extended to four perfect matchings of so that they cover . The proof of the theorem is complete.
3 Hereditary classes of cubic graphs
In this section, we briefly discuss hereditary classes of cubic graphs. It is these classes that allowed us to come up with more conjectures related to Conjectures 1 and 5.
If and are two cubic graphs with or , then we will say that and are comparable. A (not necessarily finite) set of cubic graphs is said to be an antichain, if any two cubic graphs from the set are not comparable. Let be the class of all connected cubic graphs. If is a class of connected cubic graphs, then we will say that is hereditary, if for any cubic graphs and , if and , then . Assume that is a subset of some hereditary class of cubic graphs. We will say that is a basis for , if is an antichain and for any connected cubic graph we have that if and only if there is a cubic graph , such that .
Our starting question is the following: does every hereditary class of cubic graphs admit a finite basis, that is, a basis with finitely many elements? It turns out that the answer to this question is negative. Let be the infinite antichain of cubic graphs constructed in Samal2017 . Consider the class of connected cubic graphs , such that for any we have: , if and only if there is a cubic graph , such that . It is easy to see that is a hereditary class of cubic graphs without a finite basis.
Despite this, one may still look for interesting hereditary classes arising in Graph theory, that admit a finite basis. Below, we discuss some such classes. The first class is the class of all connected cubic graphs. Clearly, it is hereditary. Observe that any connected cubic graph admitting an coloring belongs to . On the other hand, Conjecture 5 predicts that any cubic graph from admits an coloring. Thus, we can view Conjecture 5 as a statement that forms a basis for .
Let be the class of all connected bridgeless cubic graphs. (h) of Lemma 1 implies that is a hereditary class of cubic graphs. Observe that any connected cubic graph admitting a coloring belongs to . On the other hand, Conjecture 1 predicts that any bridgeless cubic graph from admits a coloring. Thus, we can view Conjecture 1 as a statement that forms a basis for .
Let be the class of all connected 3edgecolorable cubic graphs. (b) of Lemma 1 implies that is a hereditary class of cubic graphs. Let be any connected 3edgecolorable cubic graph. Observe that any cubic graph is 3edgecolorable if and only if . Thus, forms a basis for .
Let be the class of all connected cubic graphs containing a perfect matching. (c) of Lemma 1 implies that is a hereditary class of cubic graphs. Observe that any connected cubic graph admitting an coloring (the graph from Figure 5) belongs to . On the other hand, we suspect that
Conjecture 7
Any cubic graph with a perfect matching admits an coloring.
Conjecture 7 predicts that all cubic graphs from admit an coloring. Thus, we can view Conjecture 7 as a statement that forms a basis for . Let us note that Conjecture 7 has been verified for clawfree cubic graphs in AnushSylvester .
Let be the class of all connected cubic graphs with . (d) of Lemma 1 implies that is a hereditary class of cubic graphs. Observe that any connected cubic graph admitting a coloring (the graph from Figure 5) belongs to . On the other hand, we suspect that
Conjecture 8
Any cubic graph with admits a coloring.
4 The main results
In this section, we obtain our main results. First, we discuss the choice of graphs and in Conjectures 8 and 7, respectively. For this purpose, we recall the following two theorems that are proved in PetersenRemark .
Theorem 3
If is a connected bridgeless cubic graph with , then .
Theorem 4
If is a connected cubic graph with , then .
The first theorem suggests that in Conjecture 1 the graph cannot be replaced with any other connected bridgeless cubic graph. Similarly, the second theorem suggests that in Conjecture 5 the graph cannot be replaced with other connected cubic graph. Now, we are going to obtain similar results for Conjectures 8 and 7.
Theorem 5
Let be a connected bridgeless cubic graph with . Then either or .
Proof: Assume that is a coloring of . Consider the triangle in . Assume that the edges of are . Since these three edges are pairwise adjacent in , we have that the edges are pairwise adjacent in . We have two cases to consider:
Case 1: There is a vertex of , such that . Observe that in this case the edges of the 3edgecut are colored by , respectively. Thus, if we contract in , we will get a coloring of . Hence, by Theorem 3, .
Case 2: The edges form a triangle in . Observe that in this case the edges of the 3edgecut are colored by the edges of the 3edgecut . Thus, induces a coloring of . Hence, by Theorem 3, , which implies that . The proof of the theorem is complete.
Corollary 1
Let be a connected bridgeless cubic graph with and . Then .
Theorem 6
Let be a connected cubic graph with . Then either or .
Proof: Assume that is a coloring of . Consider the central triangle in , that is, the unique triangle such that all edges of are bridges. Assume that the edges of are . Since these three edges are pairwise adjacent in , we have that the edges are pairwise adjacent in . We have two cases to consider:
Case 1: There is a vertex of , such that . Observe that in this case the edges of the 3edgecut are colored by , respectively. Thus, if we contract in , we will get a coloring of . Hence, by Theorem 4, .
Case 2: The edges form a triangle in . Observe that in this case the edges of the 3edgecut are colored by the edges of the 3edgecut . Moreover, since all edges of are bridges, by (g) of Lemma 1, we have that the three edges of are bridges. This, in particular, means that is a contractible triangle in . Observe that induces a coloring of . Hence, by Theorem 4, . Moreover, the new vertex of corresponding to , is incident to three bridges. Hence is the unique cutvertex of that is incident to three bridges. This means that . The proof of the theorem is complete.
Corollary 2
Let be a connected cubic graph with a perfect matching such that . Then .
In the next statement, we discuss the following problem: assume that a bridgeless cubic graph admits a coloring such that one of the edges of is not used. What can we say about ? We discuss the related problem for Conjecture 8 afterwards. Let us note that the following statement is proved by Eckhard Steffen.
Proposition 2
Let be a bridgeless cubic that admits a coloring , such that for an edge of , we have: . Then .
Proof: (SteffenP ) Assume that the edge of is not used in a coloring of . We have that there exist two perfect matchings and of , such that . By (c) of Lemma 1, we have that and are perfect matchings in . Since the edge is not used in , we have that the perfect matchings are edgedisjoint in . Thus . The proof is complete.
Next, we characterize the edges of , which can be fictive in a coloring of a graph with .
Proposition 3
Let be a bridgeless cubic graph and let be the unique triangle of .

If admits a coloring , such that for an edge of , we have that , then .

There exist infinitely many bridgeless cubic graphs with , such that admits a coloring , such that for any edge , we have: .
Proof: (a) We follow the approach of the proof of Proposition 2, that is, we find two perfect matchings of whose intersection is . Assume that .
If , then we have that there exist two perfect matchings and of , such that . Now, these two perfect matchings can be uniquely extended to perfect matchings and of . Observe that .
On the other hand, if , then one can find a perfect matching intersecting in a single edge and a perfect matching intersecting in three edges, such that .
(b) Start with arbitrary 3edgecolorable cubic graph and consider the cubic graph obtained from by replacing every vertex of with . Since is not 3edgecolorable, we have that is not edgecolorable, hence . Let us show that we have equality here. Consider the three edges incident to , and let it be our colors in a 3edgecoloring of . Now, color the remaining copies of in by edges of , so that each edge is colored with its copy. As a result, we get a coloring of . Thus, by (d) of Lemma 1, we have . Hence . Moreover, in the coloring of the edges of are not used. The proof is complete.
In the final part of the paper we establish some connections among the discussed conjectures.
Proof: Assume that Conjecture 7 is true. We claim that any cubic graph admits an coloring. In this proof, we will assume the following notation for the edges of : the three bridges of are denoted by , the edges of the unique contractible triangle of are denoted by , such that and , and , and are opposite edges. Finally, the edges of the endblock containing a vertex incident to have the following labels: the edges incident to are and , and the parallel edges are and . Similarly, we label other edges by and .
Let be a cubic graph. If contains a perfect matching, then it has an coloring. Since has an coloring, we have the statement in this case. Thus, without loss of generality, we can assume that does not contain a perfect matching.
Consider the graph obtained from by replacing all vertices of with triangles. Observe that contains a perfect matching. An example of such a matching would be .
Thus, there exists a smallest subset , such that if we replace all vertices of with triangles, we will get a cubic graph containing a perfect matching.
By Conjecture 7, admits an coloring . Now, we claim that all triangles of corresponding to vertices of are colored with triangles of .
Assume the opposite, that is, there is a triangle corresponding to a vertex of , such that for some vertex of . Consider the graph obtained from by contracting . Observe that the resulting graph still has an coloring, hence by (c) of Lemma 1 it contains a perfect matching. However, this violates the definition of the set , since we found a smaller subset of vertices, whose replacement with triangles was leading to a cubic graph containing a perfect matching.
Now, all triangles of corresponding to vertices of are colored with triangles of . Let us show that all these triangles corresponding to vertices of are colored with the central triangle of , that is the only contractible triangle of .
On the opposite assumption, assume that , one of these triangles, is colored with other triangles of . Without loss of generality, we can assume that the edges of this triangle of are . Thus the set of edges leaving , are colored with and . Two of them are colored with , and one is colored with .
Let be a perfect matching of containing the edges and . By (c) of Lemma 1, we have that is a perfect matching in . Now, observe that . Consider the cubic graph obtained from by contracting . Observe that is a perfect matching of . This violates the definition of the set , since we found a smaller subset of vertices, whose replacement with triangles was leading to a cubic graph containing a perfect matching.
Thus, all triangles of corresponding to are colored with the edges of the central triangle of .
Observe that can be obtained from by contracting all the triangles corresponding to . Now, using the coloring of , we obtain an coloring of . Contract all triangles of corresponding to and the central triangle of to obtain , and recolor the edges of having color with the color , the edges of with color with color and finally, the edges of with color with color , respectively. Since form an even subgraph in , by (f) of Lemma 1, the edges of will form an even subgraph, that is vertexdisjoint union of cycles. Hence, after the recoloring we obtain an coloring of . The proof of the theorem is complete.
Proof: Assume that Conjectures 4 and 8 are true, and let be a bridgeless cubic graph. Let us show that admits a coloring. If , then by Conjecture 8 it has a coloring. Since admits a coloring, we have that admits a coloring. Thus, without loss of generality, we can assume that .
Consider the graph obtained from by replacing all vertices of with triangles. Observe that is a clawfree bridgeless cubic graph. Hence by Conjectures 4 and 6, and Theorem 2, . Thus, by Conjecture 8, admits a coloring. Since admits a coloring, we have that admits a coloring . Observe that since is trianglefree, we have that for any triangle of there is a vertex of , such that . Thus, if we contract all the triangles of that correspond to vertices of , we will obtain a coloring of . The proof of the theorem is complete.
5 Future work
In this section, we discuss some open problems and conjectures that are interesting in our point of view. In the previous section, we established a connection between Conjectures 8 and 1, and Conjectures 7 and 5. We suspect that this relationship can be extended to a linear order among these four conjectures. Related with this, we would like to offer:
All hereditary classes that we discussed up to now either had or are conjectured to have a basis with one element. One may wonder whether there is a hereditary class of cubic graphs arising from an interesting graph theoretic property, such that the basis of the class contains at least two graphs. For a positive integer let be the class of connected cubic graphs with . (i) of Lemma 1 implies that is a hereditary class of cubic graphs. Recently, it was shown that for any simple cubic graph NormalCubics7 . By using this result, a simple inductive proof can be obtained for the following extension of this result:
Theorem 9
Let be a cubic graph admitting a normal edgecoloring for some integer . Then .
Theorem 9 suggests that is meaningful when . Below, we discuss these classes for each of these values. When , represents the class of connected 3edgecolorable cubic graphs. Thus, our notation is consistent with that of Section 3. When , it can be easily seen that a cubic graph admits a normal 4edgecoloring, if and only if it admits a edgecoloring. Thus, . When , Jaeger has shown that a cubic graph admits a coloring if and only if it admits a normal 5edgecoloring. On the other hand, we have that any cubic graph admitting a coloring, has to be bridgeless. Thus, if Conjecture 1 is true, then . Finally, when or , we suspect that the bases of the classes and contain infinitely many cubic graphs. We are able to show that the basis of must contain at least two graphs. Let be any basis of . It can be easily seen that we can assume that it does not contain a 3edgecolorable graph. Moreover, by a simple inductive proof, one can show that all elements of can be assumed to be simple graphs. Now, let be the graph from Figure 6. The following two results are proved in AnushSylvester :
Theorem 10
Let be a simple graph with . Then .
Theorem 11
Let be a simple graph with . Then .
Theorems 10 and 11 suggest that the only way to color the graphs and with simple graphs is to take them in the basis . Thus, must contain at least two graphs.
Finally, we would like to discuss some algorithmic problems. For a fixed connected cubic graph consider a decision problem which we call the problem:
Problem 1
(problem) Given a connected cubic graph , the goal is to decide whether admits an coloring.
Observe that when is edgecolorable, we have that problem is equivalent to testing edgecolorability of the input graph , which is NPcomplete Holyer . When , we have that all instances of problem have a trivial “yes” answer provided that Conjecture 5 is true. Thus, this problem is polynomial time solvable if Conjecture 5 is true. When , Conjecture 7 implies that problem is equivalent to testing the existence of a perfect matching in the input graph . This is known to be polynomialtime solvable. When , Conjecture 1 implies that problem is equivalent to testing bridgelessness of the input graph . This problem is also polynomial time solvable. Finally, when , Conjecture 8 implies that problem is equivalent to testing whether the input graph can be covered with four perfect matchings. The latter problem is proved to be NPcomplete in EsperetGiuseppe . Thus, depending on the choice of , the problem may or may not be NPcomplete. Let be the class of all connected cubic graphs , for which the problem is NPcomplete. We suspect that:
Conjecture 10
is a hereditary class of cubic graphs.
We also would like to offer the following conjecture, which presents a dichotomy for problems:
Conjecture 11
Let be a connected cubic graph. Then:

if admits a coloring, then the problem is NPcomplete;

if does not admit a coloring, then the problem is polynomialtime solvable.
Acknowledgement
We thank Giuseppe Mazzuoccolo for proving Theorem 2.
References
 (1) A. U. Celmins, On cubic graphs that do not have an edgecolouring, Ph.D. Thesis, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada, 1984.
 (2) M. Chudnovsky, P. Seymour. The structure of clawfree graphs. In Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser. 327, pages 153–171. Cambridge Univ. Press, Cambridge, 2005.
 (3) L. Esperet, G. Mazzuoccolo, On cubic bridgeless graphs whose edgeset cannot be covered by four perfect matchings, J. Graph Theory 77(2), (2014), pp. 144–157.
 (4) D.R. Fulkerson, Blocking and antiblocking pairs of polyhedra, Math. Programming 1 (1971), 168–194.
 (5) A. Hakobyan, V. Mkrtchyan, On Sylvester Colorings of Cubic Graphs, submitted (available at https://arxiv.org/abs/1511.02475).
 (6) I. Holyer, The NPcompleteness of edgecoloring, SIAM J. Comput. 10(4), 1981, pp. 718–720.
 (7) X. Hou, H.J. Lai, C.Q. Zhang, On perfect matching coverings and even subgraph coverings, J. Graph Theory 81(1), 2016, pp. 83–91.
 (8) F. Jaeger, On fiveedgecolorings of cubic graphs and nowherezero flow problems, Ars Combinatoria, 20B, (1985), 229–244.
 (9) F. Jaeger, Nowherezero flow problems, Selected topics in graph theory, 3, Academic Press, San Diego, CA, 1988, pp. 71–95.
 (10) G. Mazzuoccolo, V. Mkrtchyan, Normal edgecolorings of cubic graphs, submitted (availabe at https://arxiv.org/abs/1804.09449).
 (11) V. V. Mkrtchyan, A remark on Petersen coloring conjecture of Jaeger, Australasian Journal of Combinatorics 56, (2013), 145–151.
 (12) S.il Oum, Perfect matchings in clawfree cubic graphs, The Electronic Journal of Combinatorics 18(1), 2011.
 (13) M. Preissmann, Sur les colorations des aretes des graphes cubiques, These de eme cycle, Grenoble (1981).
 (14) R. Šámal, Cyclecontinuous mappingsorder structure, J. Graph theory 85(1), 2017, pp. 56–73.

(15)
A. Schrijver, Combinatorial Optimization, Springer, New York, 2003.
 (16) P. D. Seymour, On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc. London Math. Soc. 38 (3), 423–460, 1979.
 (17) E. Steffen, personal communication, 2011.
 (18) D. B. West, Introduction to Graph Theory, PrenticeHall, Englewood Cliffs, 1996.
 (19) C.Q. Zhang, Integer flows and cycle covers of graphs, Marcel Dekker, Inc., New York Basel Hong Kong, 1997.
Comments
There are no comments yet.