ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 17 (2019) 431-445 https://doi.org/10.26493/1855-3974.1758.410 (Also available at http://amc-journal.eu) Si2 and P12-colorings of cubic graphs * Anush Hakobyan Department of Informatics and Applied Mathematics, Yerevan State University, Yerevan, 0025, Armenia Vahan Mkrtchyan t Dipartimento di Informatica, Universita degli Studi di Verona, Strada le Grazie 15, 37134 Verona, Italy Received 21 July 2018, accepted 1 May 2019, published online 6 November 2019 Abstract If G and H are two cubic graphs, then an H-coloring of G is a proper edge-coloring f with the edges of H, such that for each vertex x of G, there is a vertex y of H with f (dG(x)) = dH(y). If G admits an H-coloring, then we will write H -< G. The Petersen coloring conjecture of Jaeger (P10-conjecture) states that for any bridgeless cubic graph G, one has: P10 -< G. The S10-conjecture states that for any cubic graph G, S10 -< G. In this paper, we introduce two new conjectures that are related to these conjectures. The first of them states that any cubic graph with a perfect matching admits an S12-coloring. The second one states that any cubic graph G whose edge-set can be covered with four perfect matchings, admits a P12-coloring. We call these new conjectures S12-conjecture and P12-conjecture, respectively. Our first results justify the choice of graphs in S12-conjecture and P12-conjecture. Next, we characterize the edges of P12 that may be fictive in a P12-coloring of a cubic graph G. Finally, we relate the new conjectures to the already known conjectures by proving that S12-conjecture implies S10-conjecture, and P12-conjecture and (5,2)-Cycle cover conjecture together imply P10--conjecture. Our main tool for proving the latter statement is a new reformulation of (5, 2)-Cycle cover conjecture, which states that the edge-set of any claw-free bridgeless cubic graph can be covered with four perfect matchings. Keywords: Cubic graph, Petersen graph, Petersen coloring conjecture, S10 -conjecture. Math. Subj. Class.: 05C15, 05C70 * We thank Giuseppe Mazzuoccolo for proving Theorem 2.5. We also thank the anonymous referee for her/his valuable comments that helped us to improve the presentation of the paper. t Corresponding author. E-mail addresses: ashunik94@gmail.com (Anush Hakobyan), vahanmkrtchyan2002@ysu.am (Vahan Mkrtchyan) ©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/ 105 Ars Math. Contemp. 17 (2019) 349-368 1 Introduction In this paper, we consider finite, undirected graphs. They do not contain loops, though they may contain parallel edges. We also consider pseudo-graphs, 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, pseudo-graphs and simple graphs are considered up to isomorphisms. This implies that the equality G = G' means that G and G' are isomorphic. For a graph G, let V(G) and E(G) be the set of vertices and edges of G, respectively. Moreover, let dG(x) be the set of edges of G that are incident to the vertex x of G. A matching of G is a set of edges of G such that any two of them do not share a vertex. A matching of G is perfect, if it contains |V(2G)| edges. A block of G is a maximal 2-connected subgraph of G. An end-block is a block of G containing at most one vertex that is a cut-vertex of G. A subgraph H of G is even, if every vertex of H has even degree in H. A subgraph H is odd, if every vertex of G has odd degree in H. Sometime, we will refer to odd subgraphs as joins. Observe that a perfect matching is a join of a cubic graph. A subgraph H is a parity subgraph if for every vertex v of G dG(v) and dH(v) have the same parity. Observe that H is a parity subgraph of G if G - E(H) is an even subgraph of G. Let G is a cubic graph, and let K be a triangle in G such that each of K is of multiplicity one. For an edge e of K, let f be the edge of G that is incident to a vertex of K and is not adjacent to e. Edges e and f will be called opposite edges. Let G and H be two cubic graphs. An H-coloring of G is a mapping f: E(G) ^ E(H), such that for each vertex x of G there is a vertex y of H, such that f (dG(x)) = dH(y). If G admits an H-coloring, then we will write H -< G. It can be easily seen that if H -< G and K -< H, then K -< G. In other words, -< is a transitive relation defined on the set of cubic graphs. If H -< G and f is an H-coloring of G, then for any adjacent edges e, e' of G, the edges f (e), f (e') of H are adjacent. Moreover, if the graph H contains no triangle, then the converse is also true, that is, if a mapping f: E(G) ^ E(H) has a property that for any two adjacent edges e and e' of G, the edges f (e) and f (e') of H are adjacent, then f is an H-coloring of G (see Lemma 2.1). # Figure 1: The graph P10. Figure 2: The graph S10. Let P10 be the well-known Petersen graph (Figure 1) and let S10 be the graph from Figure 2. The Petersen coloring conjecture of Jaeger states: A. Hakobyan and V Mkrtchyan: S12 and P12 -colorings of cubic graphs 437 Conjecture 1.1 (Jaeger, 1988 [9]). For any bridgeless cubic graph G, P10 < G. Sometimes, we will call this conjecture as P10-conjecture. The conjecture is difficult to prove, since it can be seen that it implies the following classical conjectures: Conjecture 1.2 (Berge-Fulkerson, 1972 [4, 15]). Any bridgeless cubic graph G contains six (not necessarily distinct) perfect matchings F\,... such that any edge of G belongs to exactly two of them. This list of six perfect matchings usually is called a Berge-Fulkerson cover of G. If k(G) is the smallest number of perfect matchings that are needed to cover the edge-set of G, then observe that this conjecture implies that k(G) < 5 for any bridgeless cubic graph. This weaker statement is known as Berge conjecture. Conjecture 1.3 ((5, 2)-even-subgraph-cover conjecture [1, 13]). Any bridgeless graph G (not necessarily cubic) contains five even subgraphs such that any edge of G belongs to exactly two of them. Let us note that some of the even subgraphs stated in this conjecture might be empty. Related with the Jaeger conjecture, the following conjecture has been introduced in [11]: Conjecture 1.4 (V. V. Mkrtchyan, 2012 [11]). For any cubic graph G, S10 -< G. We will call this the Si0-conjecture. A k-edge-coloring is an assignment of colors to edges of a graph from a set of k colors such that adjacent edges receive different colors. The smallest k for which a graph G admits a k-edge-coloring is called a chromatic index of G and is denoted by x'(G). If a is a k-edge-coloring of a cubic graph G, then an edge e = uv is called poor (rich) in a, if the five edges of G incident to u or v are colored with three (five) colors. a is called a normal k-edge-coloring of G if any edge of G is either poor or rich in a. Observe that not all cubic graphs admit a normal k-edge-coloring for some k. An example of such a graph is the graph from Figure 2. On the positive side, all simple cubic graphs admit a normal 7-edge-coloring [10]. The smallest k (if it exists) for which a cubic graph G admits a normal k-edge-coloring is called a normal chromatic index of G and is denoted by xN (G). Normal colorings were introduced by Jaeger in [8], where among other results, he showed that for a cubic graph G, xN (G) < 5 if and only if G admits a P10-coloring. This allowed him to obtain a reformulation of Conjecture 1.1, which states that for any bridgeless cubic graph G, xN (G) < 5. In this paper, we introduce two new conjectures that are related to Conjectures 1.1 and 1.4. In Section 2, we discuss some auxiliary results that will be useful later in the paper. In Section 3, we briefly discuss so-called coloring-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 [17, 18]. 2 Auxiliary results In this section, we present some auxiliary results that will be useful later. Our first two results are lemmas about some properties of H-colorings of cubic graphs. Though all these properties are known before, for the sake of completeness we give complete proofs. 107 Ars Math. Contemp. 17 (2019) 349-368 Lemma 2.1. Assume that G and H are two cubic graphs. Moreover, let H be triangle-free. If a mapping f: E (G) ^ E(H) has a property that for any two adjacent edges e and e' of G, the edges f (e) and f (e') of H are adjacent, then f is an H-coloring of G. Proof. In order to see this, assume that f is not an H-coloring of G. Then G contains a vertex w where the definition of an H-coloring is violated. Let e1, e2 and e3 be the three edges incident to w. Assume that the colors of e1 and e2 in f are the edges xy and yz of H. Observe that z = x, as otherwise we will have f (dG(w)) = dH(x) or f (dG(w)) = dH(y) violating the choice of w. Now, the edge f (e3) of H cannot be incident to y. On the other hand, it must be adjacent to xy and yz. Hence f (e3) connects x and z. Observe that the edges x, y and z form a triangle in H. This contradicts our condition on H. □ Note that the condition H is triangle-free is important in the previous lemma. If G is any 3-edge-colorable cubic graph and H contains a triangle with edges h1, h2 and h3, then consider the 3-edge-coloring of G with colors h1, h2 and h3. Observe that for any two adjacent edges of G, their colors are adjacent edges in H. However, the coloring is not an H-coloring as in every vertex of G its definition is violated. Lemma 2.2. Suppose that G and H are cubic graphs with H -< G, and let f be an H-coloring of G. Then: (a) If M is any matching of H, then f-1(M) is a matching of G; (b) x'(G) < x'(H); (c) If M is a perfect matching of H, then f-1(M) is a perfect matching of G; (d) k(G) < k(H); (e) If H admits a Berge-Fulkerson cover, then G also admits a Berge-Fulkerson cover; (f) For every even subgraph C of H, f-1(C) is an even subgraph of G; (g) For every bridge e of G, the edge f (e) is a bridge of H; (h) If H is bridgeless, then G is bridgeless as well; (i) Xn(G) < Xn (H). Proof. (a) and (c): The proof of (a) follows from the definition of H-coloring: as adjacent edges of G must be colored with adjacent edges of H, then clearly the pre-image of a matching in H must be a matching in G. For the proof of (c) let M be a perfect matching of H. Then by (a), f -1(M) is a matching of G. Let us show that it covers all vertices of G. Let v be a vertex of G. Then the three edges incident to v are colored by a similar three edges of H. Since M is a perfect matching of H, one of these three edges must belong to M, hence f-1(M) n dG(v) = 0. Thus, f-1(M) is a perfect matching of G. (b) and (d): For the proof of (b) assume that x' (H) = s and let M1,...,Ms be the color classes of H in an s-edge-coloring. Consider f -1 (M1),..., f -1(Ms). Observe that due to (a), they are forming s matchings covering the edge-set of G. Thus, x'(G) < s = x'(H). The proof of (d) is similar: let k(H) = s and let M1,...,Ms be the s perfect matchings of H covering E(H). Consider f-1(M1),..., f-1(Ms). Observe that due to (c), they are forming s perfect matchings covering the edge-set of G. Thus, k(G) < s = k(H). (e): Let C = (F1,..., F6) be a Berge-Fulkerson cover of H. Consider the list f-1(C) = (f-1(F1),..., f-1(F6)). Observe that due to (c) they are forming a list of A. Hakobyan and V Mkrtchyan: S12 and P12 -colorings of cubic graphs 437 six perfect matchings of G. Moreover, every edge of G belongs to at least two of these perfect matchings. Hence f-1(C) is a Berge-Fulkerson cover of G. (f): Let C be an even subgraph of H. Let us show that any vertex v of G has even degree in f-1(C). Since H is cubic, C is a disjoint union of cycles. Assume that in f the three edges incident to v are colored with three edges incident to a vertex w of H. Then if w is isolated in C, then clearly v is isolated in f-1(C). On the other hand, if w has degree two in C, then v is of degree two in f-1(C). Thus, v always has even degree in f-1 (C), or f -1(C) is an even subgraph of G. (g): Let e be a bridge of G and let (X, V(G) \ X) be a partition of V(G), such that dG(X) = {e}. Assume that the edge f (e) is not a bridge in H. Then there is a cycle C in H that contains the edge f (e). By (f) f-1 (C) is an even subgraph of G that has non-empty intersection with dG(X). Since the intersection of an even subgraph with dG(X) always contains an even number of edges, we have that dG(X) contains at least two edges which contradicts our assumption. (h): This follows from (g): if H has no bridge, then any edge of G cannot be a bridge, as otherwise its color in f will be a bridge in H. (i): Assume that xN (H) = s, and let g be a normal s-edge-coloring of H. Consider a mapping h defined on the edge-set of G as follows: for any edge e of G, let h(e) = g(f (e)). Let us show that h is a normal s-edge-coloring of G. Let e = vw be any edge of G. Assume that in f the three edges incident to v are colored by the three edges incident to a vertex u1 of H, the three edges incident to w are colored by the three edges incident to a vertex u2 If u1 = u2, then the edge e is poor in h. Thus, we can assume that u1 = u2. Since e G dG(v) n dG(w), we have that m1m2 g E(H) and f (e) = u1u2. Now, observe that since g is a normal edge-coloring, we have that if f (e) is a poor edge in g, then e is a poor edge in h, and if f (e) is a rich edge in g, then e is a rich edge in h. Thus, h is a normal s-edge-coloring of G. Hence xN (G) < s = xN(H). The proof of the lemma is complete. □ We will need some results on claw-free bridgeless cubic graphs. Recall that a graph G is claw-free, if it does not contain 4 vertices, such that the subgraph of G induced on these vertices is isomorphic to K13. In [2], arbitrary claw-free graphs are characterized. In [12], Oum has characterized simple, claw-free bridgeless cubic graphs. In order to formulate Oum's result, we need some definitions. In a claw-free simple cubic graph G any vertex belongs to 1, 2, or 3 triangles. If a vertex v belongs to 3 triangles of G, then the component of G containing v is isomorphic to K4 (Figure 3). An induced subgraph of G that is isomorphic to K4 - e is called a diamond [12]. It can be easily checked that in a claw-free cubic graph no 2 diamonds intersect. A string of diamonds of G is a maximal sequence F1,..., of diamonds, in which Fi has a vertex adjacent to a vertex of Fi+1, 1 < i < k — 1. A string of diamonds has exactly of H. Figure 3: The graph K4. 109 Ars Math. Contemp. 17 (2019) 349-368 2 vertices of degree 2, which are called the head and the tail of the string. Replacing an edge e = uv with a string of diamonds with the head x and the tail y is to remove e and add edges (u, x) and (v, y). If G is a connected claw-free simple cubic graph such that each vertex lies in a diamond, then G is called a ring of diamonds. It can be easily checked that each vertex of a ring of diamonds lies in exactly one diamond. As in [12], we require that a ring of diamonds contains at least 2 diamonds. Proposition 2.3 (Oum [12]). G is a connected claw-free simple bridgeless cubic graph, if and only if (1) G is isomorphic to K4, or (2) G is a ring of diamonds, or (3) there is a connected bridgeless cubic graph H, such that G can be obtained from H by replacing some edges of H with strings of diamonds, and by replacing any vertex of H with a triangle. The next auxiliary result allows us to relate coverings with even subgraphs to coverings with specific parity subgraphs. Like we stated in the introduction, some of the even subgraphs here might be empty. Theorem 2.4 ([7, Theorem 3.3]). For a graph G, the following two conditions are equivalent: (1) G contains five even subgraphs such that any edge of G belongs to exactly two of them; (2) G contains four parity subgraphs such that each edge belongs to either one or two of the parity subgraphs. Our final auxiliary result is a theorem proved by Giuseppe Mazzuoccolo which offers a new reformulation of Conjecture 1.3. Theorem 2.5. Conjecture 1.3 is equivalent to the statement that for all bridgeless claw-free cubic graphs we have k(G) < 4. Proof. Assume that for any claw-free bridgeless cubic graph G, we have k(G) < 4. Let us show that Conjecture 1.3 is also true. It is known that it suffices to prove Conjecture 1.3 for cubic graphs [18]. Let G be an arbitrary bridgeless cubic graph. Consider the cubic graph H obtained from G by replacing every vertex of G with a triangle. Observe that H is a claw-free bridgeless cubic graph. By our assumption, the edge-set of H can be covered with four perfect matchings. Observe that perfect matchings are parity subgraphs in cubic graphs, hence by Theorem 2.4, H admits a list of 5 even subgraphs covering each edge exactly twice. In order to complete the proof, let us observe that if a cubic graph K admits a list of 5 even subgraphs covering each edge exactly twice and it contains a triangle T, then the graph K/T also admits a list of 5 even subgraphs covering each edge exactly twice. In order to see this, let C = (Evi,..., Ev5) be the list of 5 even subgraphs covering the edges of K twice. Then it is easy to see that the edges of the 3-cut dK (T) are covered as follows: first edge belongs to Ev i and Ev 2, the second edge belongs to Ev i and Ev3, and finally A. Hakobyan and V Mkrtchyan: S12 and P12 -colorings of cubic graphs 437 the third edge belongs to Ev2 and Ev3. Moreover, Ev4 and Ev5 do not intersect the 3-cut. One can always achieve this by renaming the even subgraphs. Now, if we consider the restrictions of (Ev 1,..., Ev5) to K/T, we will have that they are forming a list of 5 even subgraphs covering each edge of K/T exactly twice. Applying this observation | V(G) | times to H, we will get the statement for the original cubic graph G. For the proof of the converse statement, let us assume that Conjecture 1.3 is true, and show that any claw-free bridgeless cubic graph G can be covered with four perfect match-ings. We prove the latter statement by induction on |V(G)|. If |V(G)| = 2, the the statement is trivially true. Assume that it is true for all claw-free bridgeless cubic graphs with less n vertices and let us consider a claw-free bridgeless cubic graph G with n > 4 vertices. Clearly, we can assume that G is connected. Let us show that we can assume that G is simple. On the opposite assumption, consider the vertices u and v that are joined with two edges. Let u' and v' be the the other neighbors of u and v, respectively. Consider a cubic graph G' obtained from G - {u, v} by adding a possibly parallel edge u'v'. Observe that G' is a bridgeless cubic graph with |V(G')| < n. Moreover, it is claw-free. Thus, by induction hypothesis, G' can be covered with four perfect matchings. Now, it is easy to see that using these list of four perfect matchings of G' we can construct a list of four perfect matchings of G covering E(G). Thus, without loss of generality, we can assume that G is simple. Hence, we can apply Proposition 2.3. If G meets the first or the second condition of the proposition, then it is easy to see that G is 3-edge-colorable, hence it can be covered with three perfect matchings. Thus, we can assume that there is a connected bridgeless cubic graph H such that G can be obtained from H by replacing some edges of H with strings of diamonds and every vertex of H with a triangle. Let us show that we can also assume that G has no string of diamonds. Assume it has one. Let it be S whose head and tails are u and v, respectively. Let u' and v' be the neighbors of u and v, respectively, that lie outside S. Consider a graph G' obtained from G - V(S) by adding a possibly parallel edge u'v'. Observe that G' is a bridgeless cubic graph with |V(G')| < n. Moreover, it is claw-free. Thus, by induction hypothesis, G' can be covered with four perfect matchings. Now, it is easy to see that using these list of four perfect matchings of G' we can construct a list of four perfect matchings of G covering E(G). Thus, without loss of generality, we can assume that G can be obtained from the connected bridgeless cubic graph H by replacing its every vertex with a triangle. By Conjecture 1.3, H has a list of five even subgraphs covering its edges exactly twice. By Theorem 2.4, we have that H admits a cover with four joins such that each edge of H is covered once or twice. Let v any vertex of H and let C = (T\, T2, T3, T4) be the cover of H with four joins. Since each edge of H is covered once or twice in C, we have that there is at most one join in C that contains all three edges incident to v. Thus, for any vertex v we have that either one of joins contains all three edges incident to v and the other three joins contain exactly one edge incident to v, or all joins contain exactly one edge incident to v. Now, it is not hard to see that these four joins covering H can be extended to four perfect matchings of G so that they cover G. The proof of the theorem is complete. □ 111 Ars Math. Contemp. 17 (2019) 349-368 3 Coloring-hereditary classes of cubic graphs In this section, we briefly discuss coloring-hereditary classes of cubic graphs. It is these classes that allowed us to come up with more conjectures related to Conjectures 1.1 and 1.4. If G and H are two cubic graphs with H -< G or G -< H, then we will say that G and H are comparable. A (not necessarily finite) set of cubic graphs is said to be an anti-chain, if any two cubic graphs from the set are not comparable. Let C be the class of all connected cubic graphs. If M CC is a class of connected cubic graphs, then we will say that M is coloring-hereditary, if for any cubic graphs G and H, if H G M and H -< G, then G G M. Assume that B C M is a subset of some coloring-hereditary class M of cubic graphs. We will say that B is a basis for M, if B is an anti-chain and for any connected cubic graph G we have that G G M if and only if there is a cubic graph H gB, such that H -< G. Our starting question is the following: does every coloring-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 I be the infinite anti-chain of cubic graphs constructed in [14]. Consider the class M of connected cubic graphs G, such that for any G we have: G G M, if and only if there is a cubic graph H G I, such that H -< G. It is easy to see that M is a coloring-hereditary class of cubic graphs without a finite basis. Despite this, one may still look for interesting coloring-hereditary classes arising in graph theory, that admit a finite basis. Below, we discuss some such classes. The first class is C-the class of all connected cubic graphs. Clearly, it is coloring-hereditary. Observe that any connected cubic graph admitting an S10-coloring belongs to C. On the other hand, Conjecture 1.4 predicts that any cubic graph from C admits an Slo-coloring. Thus, we can view Conjecture 1.4 as a statement that S10 forms a basis for C. Let Cb be the class of all connected bridgeless cubic graphs. Statement (h) of Lemma 2.2 implies that Cb is a coloring-hereditary class of cubic graphs. Observe that any connected cubic graph admitting a P10-coloring belongs to Cb. On the other hand, Conjecture 1.1 predicts that any bridgeless cubic graph from Cb admits a P10-coloring. Thus, we can view Conjecture 1.1 as a statement that P10 forms a basis for Cb. Let C3 be the class of all connected 3-edge-colorable cubic graphs. Statement (b) of Lemma 2.2 implies that C3 is a coloring-hereditary class of cubic graphs. Let H be any connected 3-edge-colorable cubic graph. Observe that any cubic graph G is 3-edge-colorable if and only if H -< G. Thus, H forms a basis for C3. Figure 4: The graph S12. Figure 5: The graph P12. Let Cp be the class of all connected cubic graphs containing a perfect matching. Statement (c) of Lemma 2.2 implies that Cp is a coloring-hereditary class of cubic graphs. Ob- A. Hakobyan and V Mkrtchyan: S12 and P12 -colorings of cubic graphs 437 serve that any connected cubic graph admitting an S12-coloring (the graph from Figure 4) belongs to Cp. On the other hand, we suspect that Conjecture 3.1. Any cubic graph with a perfect matching admits an S12-coloring. Conjecture 3.1 predicts that all cubic graphs from Cp admit an S12-coloring. Thus, we can view Conjecture 3.1 as a statement that S12 forms a basis for Cp. Let us note that Conjecture 3.1 has been verified for claw-free cubic graphs in [5]. Let C(4) be the class of all connected cubic graphs G with k(G) < 4. Statement (d) of Lemma 2.2 implies that C(4) is a coloring-hereditary class of cubic graphs. Observe that any connected cubic graph admitting a P12 -coloring (the graph from Figure 4) belongs to C(4). On the other hand, we suspect that Conjecture 3.2. Any cubic graph G with k(G) < 4 admits a P12-coloring. Conjecture 3.2 predicts that all cubic graphs from C(4) admit a P12-coloring. Thus, we can view Conjecture 3.2 as a statement that P12 forms a basis for C(4). Also, note that (e) of Lemma 2.2 implies that Conjecture 4.9 from [7] is a consequence of Conjecture 3.2. 4 The main results In this section, we obtain our main results. First, we discuss the choice of graphs P12 and S12 in Conjectures 3.2 and 3.1, respectively. For this purpose, we recall the following two theorems that are proved in [11]. Theorem 4.1. If G is a connected bridgeless cubic graph with G -< P10, then G = P10. Theorem 4.2. If G is a connected cubic graph with G -< S10, then G = S10. The first theorem suggests that in Conjecture 1.1 the graph P10 cannot be replaced with any other connected bridgeless cubic graph. Similarly, the second theorem suggests that in Conjecture 1.4 the graph S10 cannot be replaced with other connected cubic graph. Now, we are going to obtain similar results for Conjectures 3.2 and 3.1. Theorem 4.3. Let G be a connected bridgeless cubic graph with G -< P12. Then either G = P10 or G = P12. Proof. Assume that f is a G-coloring of P12. Consider the triangle T in P12. Assume that the edges of T are e1, e2, e3. Since these three edges are pairwise adjacent in P12, we have that the edges f (e1), f (e2), f (e3) are pairwise adjacent in G. We have two cases to consider: Case 1: There is a vertex v of G, such that dG(v) = {f (e1), f (e2), f (e3)}. Observe that in this case the edges of the 3-edge-cut dPl2(V(T)) are colored by f (e1),f (e2),f (e3), respectively. Thus, if we contract T in P12, we will get a G-coloring of P10. Hence, by Theorem 4.1, G = P10. Case 2: The edges f (e1), f (e2), f (e3) form a triangle T0 in G. Observe that in this case the edges of the 3-edge-cut dPl2 (V(T)) are colored by the edges of the 3-edge-cut dG (V(T0)). Thus, f induces a G/T0-coloring of P12/T = P10. Hence, by Theorem 4.1, G/T0 = P10, which implies that G = P12. The proof of the theorem is complete. □ 113 Ars Math. Contemp. 17 (2019) 349-368 Corollary 4.4. Let G be a connected bridgeless cubic graph with k(G) < 4 and G -< P12. Then G = P12. Theorem 4.5. Let G be a connected cubic graph with G -< S12. Then either G = S10 or G = S12. Proof. Assume that f is a G-coloring of Si2. Consider the central triangle T in Si2, that is, the unique triangle T such that all edges of dSl2 (V(T)) are bridges. Assume that the edges of T are e1, e2, e3. Since these three edges are pairwise adjacent in S12, we have that the edges f (e1), f (e2), f (e3) are pairwise adjacent in G. We have two cases to consider: Case 1: There is a vertex v of G, such that Oa(v) = {f (e1), f (e2), f (e3)}. Observe that in this case the edges of the 3-edge-cut dSl2 (V(T)) are colored by f (e1), f (e2), f (e3), respectively. Thus, if we contract T in S12, we will get a G-coloring of S10. Hence, by Theorem 4.2, G = S10. Case 2: The edges f (e1),f (e2), f (e3) form a triangle T0 in G. Observe that in this case the edges of the 3-edge-cut dSl2 (V(T)) are colored by the edges of the 3-edge-cut dG(V(T0)). Moreover, since all edges of dSl2 (V (T)) are bridges, by (g) ofLemma 2.2, we have that the three edges of dG(V(T0)) are bridges. This, in particular, means that each edge of T0 is of multiplicity one in G. Observe that f induces a G/T0-coloring of S12/T = S10. Hence, by Theorem 4.2, G/T0 = S10. Moreover, the new vertex vTo of G/T0 corresponding to T0, is incident to three bridges. Hence vTo is the unique cut-vertex of G/T0 = S10 that is incident to three bridges. This means that G = S12. The proof of the theorem is complete. □ Corollary 4.6. Let G be a connected cubic graph with a perfect matching such that G -< S12. Then G = Sn. In the next statement, we discuss the following problem: assume that a bridgeless cubic G graph admits a P10-coloring such that one of the edges of P10 is not used. What can we say about G? We discuss the related problem for Conjecture 3.2 afterwards. Let us note that the following statement is proved by Eckhard Steffen. Proposition 4.7. Let G be a bridgeless cubic that admits a P10-coloring f, such that for an edge e of P10, we have: f-1(e) = 0. Then x'(G) = 3. Proof. ([16]) Assume that the edge e of P10 is not used in a P10-coloring f of G. We have that there exist two perfect matchings M1 and M2 of P10, such that M1 n M2 = {e}. By (c) of Lemma 2.2, we have that f -1(M1) and f-1 (M2) are perfect matchings in G. Since the edge e is not used in f, we have that the perfect matchings are edge-disjoint in G. Thus x'(G) = 3. The proof is complete. □ Next, we characterize the edges of P12, which can be fictive in a P12 -coloring of a graph with k(G) < 4. Proposition 4.8. Let G be a bridgeless cubic graph and let T be the unique triangle of P12. (a) If G admits a P12-coloring f, such that for an edge e 4. Let us show that we have equality here. Consider the three edges incident to v, and let it be our colors in a 3-edge-coloring of H. Now, color the remaining copies of P10 - v in G by edges of P10 - v, so that each edge is colored with its copy. As a result, we get a P12-coloring of G. Thus, by (d) of Lemma 2.2, we have k(G) < 4. Hence k(G) = 4. Moreover, in the P12 -coloring of G the edges of T are not used. The proof is complete. □ In the final part of the paper we establish some connections among the discussed conjectures. Theorem 4.9. Conjecture 3.1 implies Conjecture 1.4. Proof. Assume that Conjecture 3.1 is true. We claim that any cubic graph G admits an S10-coloring. In this proof, we will assume the following notation for the edges of S12: the three bridges of S12 are denoted by a, b, c, the edges of the unique contractible triangle of S12 are denoted by x, y, z, such that x and a, y and b, z and c are opposite edges. Finally, the edges of the end-block containing a vertex incident to a have the following labels: the edges incident to a are a1 and a2, and the parallel edges are a3 and a4. Similarly, we label other edges by b1, b2, b3, b4 and c1, c2, c3, c4. Let G be a cubic graph. If G contains a perfect matching, then it has an S12-coloring. Since S12 has an S^o-coloring, we have the statement in this case. Thus, without loss of generality, we can assume that G does not contain a perfect matching. Consider the graph Ga obtained from G by replacing all vertices of G with triangles. Observe that Ga contains a perfect matching. An example of such a matching would be E(G). Thus, there exists a smallest subset U C V(G), such that if we replace all vertices of U with triangles, we will get a cubic graph H containing a perfect matching. By Conjecture 3.1, H admits an S12-coloring f. Now, we claim that all triangles of H corresponding to vertices of U are colored with triangles of S12. Assume the opposite, that is, there is a triangle T corresponding to a vertex of H, such that f (E(T)) = dSl2 (v) for some vertex v of S12. Consider the graph H' obtained from H by contracting T. Observe that the resulting graph H' still has an S12-coloring, hence by (c) of Lemma 2.2 it contains a perfect matching. However, this violates the definition of the set U, 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 H corresponding to vertices of U are colored with triangles of S12. Let us show that all these triangles corresponding to vertices of U are colored with the central triangle of S12, that is the only contractible triangle of S12. 115 Ars Math. Contemp. 17 (2019) 349-368 On the opposite assumption, assume that T, one of these triangles, is colored with other triangles of S12. Without loss of generality, we can assume that the edges of this triangle of S12 are a1, a2, a3. Thus the set of edges leaving T, are colored with a and a4. Two of them are colored with a4, and one is colored with a. Let M be a perfect matching of S12 containing the edges a and a3. By (c) of Lemma 2.2, we have that F = f-1(M) is a perfect matching in H. Now, observe that |F n dH(V(T))| = 1. Consider the cubic graph H" obtained from H by contracting T. Observe that F \ (F n E(T)) is a perfect matching of H". This violates the definition of the set U, 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 H corresponding to U are colored with the edges x, y, z of the central triangle of S12. Observe that G can be obtained from H by contracting all the triangles corresponding to U. Now, using the S12-coloring of H, we obtain an S10-coloring of G. Contract all triangles of H corresponding to U and the central triangle of S12 to obtain S10, and recolor the edges of H having color x with the color a, the edges of H with color y with color b and finally, the edges of H with color z with color c, respectively. Since x, y, z form an even subgraph in S12, by (f) of Lemma 2.2, the edges of f-1({x, y, z}) will form an even subgraph, that is vertex-disjoint union of cycles. Hence, after the re-coloring we obtain an S10-coloring of G. The proof of the theorem is complete. □ Theorem 4.10. Conjectures 1.3 and 3.2 imply Conjecture 1.1. Proof. Assume that Conjectures 1.3 and 3.2 are true, and let G be a bridgeless cubic graph. Let us show that G admits a P10-coloring. If k(G) < 4, then by Conjecture 3.2 it has a P12-coloring. Since P12 admits a P10-coloring, we have that G admits a P10--coloring. Thus, without loss of generality, we can assume that k(G) > 5. Consider the graph H obtained from G by replacing all vertices of G with triangles. Observe that H is a claw-free bridgeless cubic graph. Hence by Conjecture 1.3 and Theorem 2.5, k(H) < 4. Thus, by Conjecture 3.2, H admits a P12-coloring. Since P12 admits a P1o-coloring, we have that H admits a P1o-coloring f. Observe that since P10 is triangle-free, we have that for any triangle T of H there is a vertex v of P10, such that f (E(T)) = dPl0 (v). Thus, if we contract all the triangles of H that correspond to vertices of G, we will obtain a P10-coloring of G. The proof of the theorem is complete. □ The diagram from Figure 6 explains the relationship among the main four conjectures discussed in the paper. The first arrow shows that P12-conjecture implies P10-con-jecture if 5-CDC is true (Conjecture 1.3). The second arrow shows that the statement "P10-conjecture implies S12-conjecture" is the formulation of Conjecture 5.1. Finally, the third arrow shows that in Theorem 4.9 we showed that S12-conjecture implies the S10-conjecture. 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 3.2 and 1.1, and Conjectures 3.1 and 1.4. We suspect that this relationship can be extended to a linear order among these four conjectures. Related with this, we would like to offer: A. Hakobyan and V Mkrtchyan: S12 and P12 -colorings of cubic graphs 437 Figure 6: The relationship among the main conjectures. Conjecture 5.1. Conjecture 1.1 implies Conjecture 3.1. All coloring-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 coloring-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 k let Ck be the class of connected cubic graphs G with xN (G) < k. Statement (i) of Lemma 2.2 implies that Ck is a coloring-hereditary class of cubic graphs. Recently, it was shown that for any simple cubic graph xN (G) < 7 [10]. By using this result, a simple inductive proof can be obtained for the following extension of this result: Theorem 5.2. Let G be a cubic graph admitting a normal k-edge-coloringfor some integer k. Then x'N (G) < 7. Theorem 5.2 suggests that Ck is meaningful when k = 3,4, 5,6,7. Below, we discuss these classes for each of these values. When k = 3, Ck represents the class of connected 3-edge-colorable cubic graphs. Thus, our notation is consistent with that of Section 3. When k = 4, it can be easily seen that a cubic graph admits a normal 4-edge-coloring, if and only if it admits a 3-edge-coloring. Thus, C4 = C3. When k = 5, Jaeger has shown that a cubic graph admits a P10-coloring if and only if it admits a normal 5-edge-coloring. On the other hand, we have that any cubic graph admitting a P10-coloring, has to be bridgeless. Thus, if Conjecture 1.1 is true, then C5 = Cb. Finally, when k = 6 or k = 7, we suspect that the bases of the classes C6 and C7 contain infinitely many cubic graphs. We are able to show that the basis of C7 must contain at least two graphs. Let B be any basis of C7. It can be easily seen that we can assume that it does not contain a 3-edge-colorable graph. Moreover, by a simple inductive proof, one can show that all elements of B can be assumed to be simple graphs. Now, let S16 be the graph from Figure 7. The following two results are proved in [5]: 431 Ars Math. Contemp. 17 (2019) 349-368 Theorem 5.3. Let G be a simple graph with G — S16. Then G = S16. Theorem 5.4. Let G be a simple graph with G — P10. Then G = P10. Theorems 5.3 and 5.4 suggest that the only way to color the graphs Si6 and P10 with simple graphs is to take them in the basis B. Thus, B must contain at least two graphs. Finally, we would like to discuss some algorithmic problems. For a fixed connected cubic graph H consider a decision problem which we call the H-problem: Problem 5.5 (H-problem). Given a connected cubic graph G, the goal is to decide whether G admits an H-coloring. Observe that when H is 3-edge-colorable, we have that H-problem is equivalent to testing 3-edge-colorability of the input graph G, which is NP-complete [6]. When H = S10, we have that all instances of H-problem have a trivial "yes" answer provided that Conjecture 1.4 is true. Thus, this problem is polynomial time solvable if Conjecture 1.4 is true. When H = S12, Conjecture 3.1 implies that H-problem is equivalent to testing the existence of a perfect matching in the input graph G. This is known to be polynomial-time solvable. When H = P10, Conjecture 1.1 implies that H-problem is equivalent to testing bridgelessness of the input graph G. This problem is also polynomial time solvable. Finally, when H = P12, Conjecture 3.2 implies that H-problem is equivalent to testing whether the input graph G can be covered with four perfect matchings. The latter problem is proved to be NP-complete in [3]. Thus, depending on the choice of H, the H-problem may or may not be NP-complete. Let CNP be the class of all connected cubic graphs H, for which the H-problem is NP-complete. We suspect that: Conjecture 5.6. CNP is a coloring-hereditary class of cubic graphs. We also would like to offer the following conjecture, which presents a dichotomy for H-problems: Conjecture 5.7. Let H be a connected cubic graph. Then: • if H admits a P12 -coloring, then the H-problem is NP-complete; • if H does not admit a P12-coloring, then the H -problem is polynomial-time solvable. References [1] A. U. Celmins, On Cubic Graphs That Do Not Have an Edge-3-Colouring, Ph.D. thesis, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada, 1984. A. Hakobyan and V Mkrtchyan: S12 and P12 -colorings of cubic graphs 437 [2] M. Chudnovsky and P. Seymour, The structure of claw-free graphs, in: B. S. Webb (ed.), Surveys in Combinatorics 2005, Cambridge University Press, Cambridge, volume 327 of London Mathematical Society Lecture Note Series, pp. 153-171, 2005, doi:10.1017/ cbo9780511734885.008, papers from the 20th British Combinatorial Conference held at the University of Durham, Durham, July 10- 15, 2005. [3] L. Esperet and G. Mazzuoccolo, On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings, J. Graph Theory 77 (2014), 144-157, doi:10.1002/jgt.21778. [4] D. R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971), 168-194, doi:10.1007/bf01584085. [5] A. Hakobyan and V. Mkrtchyan, On Sylvester colorings of cubic graphs, Australas. J. Combin. 72 (2018), 472-491, https://ajc.maths.uq.edu.au/pdf/72/ajc_v72_p4 72. pdf. [6] I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981), 718-720, doi: 10.1137/0210055. [7] X. Hou, H.-J. Lai and C.-Q. Zhang, On perfect matching coverings and even subgraph coverings, J. Graph Theory 81 (2016), 83-91, doi:10.1002/jgt.21863. [8] F. Jaeger, On five-edge-colorings of cubic graphs and nowhere-zero flow problems, Ars Combin. 20 (1985), 229-244. [9] F. Jaeger, Nowhere-zero flow problems, in: L. W. Beineke and R. J. Wilson (eds.), Selected Topics in Graph Theory 3, Academic Press, San Diego, California, pp. 71-95, 1988. [10] G. Mazzuoccolo and V. Mkrtchyan, Normal edge-colorings of cubic graphs, submitted, arXiv:1804.09449 [cs.DM]. [11] V. V. Mkrtchyan, A remark on the Petersen coloring conjecture of Jaeger, Australas. J. Combin. 56 (2013), 145-151, https://ajc.maths.uq.edu.au/pdf/5 6/ajc_v56_p145. pdf. [12] S. Oum, Perfect matchings in claw-free cubic graphs, Electron. J. Combin. 18 (2011), #P62 (6 pages), https://www.combinatorics.org/ojs/index.php/eljc/article/ view/v18i1p62. [13] M. Preissmann, Sur les colorations des aretes des graphes cubiques, Ph.D. thesis, Universite Joseph Fourier, Grenoble, France, 1981, https://tel.archives-ouvertes.fr/ tel-00294175. [14] R. Samal, Cycle-continuous mappings—order structure, J. Graph Theory 85 (2017), 56-73, doi:10.1002/jgt.22047. [15] P. D. Seymour, On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. London Math. Soc. 38 (1979), 423-460, doi:10.1112/plms/s3-38.3.423. [16] E. Steffen, personal communication, 2011. [17] D. B. West, Introduction to Graph Theory, Prentice-Hall, Upper Saddle River, New Jersey, 1996. [18] C.-Q. Zhang, Integer Flows and Cycle Covers of Graphs, volume 205 of Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, New York, 1997.