Berge–Fulkerson Coloring for Infinite Families of Snarks

Abstract

It is conjectured by Berge and Fulkerson that every bridgeless cubic graph has six perfect matchings such that each edge is contained in exactly two of them. Hägglund constructed Blowup$(K_4, C)$ and Blowup(Prism, $C_4)$. Based on these two graphs, Chen constructed infinite families of bridgeless cubic graphs $M_{0,1,2, \ldots ,k-2, k-1}$ which are obtained from cyclically 4-edge-connected and admitting Fulkerson-cover cubic graphs $G_0,G_1,\ldots , G_{k-1}$ by recursive process. He obtained that every graph in $M_{0,1,2,3}$ has a Fulkerson-cover and gave the open problem that whether every graph in $M_{0,1,2, \ldots ,k-2, k-1}$ has a Fulkerson-cover. In this paper, we solve this problem and prove that every graph in $M_{0,1,2, \ldots ,k-2, k-1}$ has a Fulkerson-cover.

1 Introduction

Let G be a simple graph with vertex set V(G) and edge set E(G). A circuit of G is a 2-regular connected subgraph. An even graph is a graph with even degree at every vertex. A perfect matching of G is a 1-regular spanning subgraph of G. The excessive index of G, denoted by $\chi _e'(G)$, is the least integer k, such that G can be covered by k perfect matchings. A cubic graph is a snark if it is bridgeless and not 3-edge-colorable.

The following is a famous open problem called Berge–Fulkerson conjecture:

Conjecture 1.1

(Berge–Fulkerson Conjecture [6], or see [11]) Every bridgeless cubic graph has six perfect matchings such that each edge belongs to exactly two of them.

We call such six perfect matchings in the conjecture as the Fulkerson-cover. Let G be a cubic graph. The graph 2G is obtained from G by duplicating every edge to become a pair of parallel edges. A graph G is Berge–Fulkerson colorable if the graph 2G is 6-edge-colorable. It means that there exists a mapping from E(2G) to $\{1,2,\ldots , 6\}$ such that every vertex of 2G is incident with edges colored with all six colors. Clearly, the six perfect matchings in the conjecture correspond to the 6-edge-coloring of the graph 2G. Thus Berge–Fulkerson colorable is an equivalent description of the Fulkerson-cover.

Although there are some results related with this conjecture, as examples, see [3, 5, 7, 8, 10, 12], Berge–Fulkerson conjecture is still open for many bridgeless cubic graphs even for some simple snarks. Fan and Raspaud [5] in 1994 made a weaker conjecture that every bridgeless cubic graph contains three perfect matchings with empty intersection. There are some known partial results such as the verification [9] of Fan–Raspaud conjecture for oddness two graphs. However, this weaker conjecture remains also unsolved.

Hägglund [7] constructed Blowup$(K_4, C)$ and Blowup(Prism, $C_4)$. Based on Blowup$(K_4, C)$, Esperet et al. [4] constructed infinite families of cyclically 4-edge-connected snarks with excessive index at least five. Based on these two graphs, Chen [2] constructed infinite families of cyclically 4-edge-connected snarks $E_{0,1,2,\ldots ,(k-1)}$ obtained from cyclically 4-edge-connected snarks $G_0,G_1,\ldots , G_{k-1}$, in which $E_{0,1,2}$ is Esperet et al.’s construction. If only assume that each graph in $\{G_0,G_1,\ldots , G_{k-1}\}$ has a Fulkerson-cover, then these infinite families of bridgeless cubic graphs are denoted by $M_{0,1,2, \ldots ,k-2, k-1}$. Chen [2] obtained that every graph in $M_{0,1}$ or in $M_{0,1,2,3}$ has a Fulkerson-cover and gave the following problem:

Problem 1.2

[2] If $H=\{G; G_0, G_1, \ldots ,G_{k-2}, G_{k-1}\} \in M_{0,1,2, \ldots ,k-2, k-1}$, does H have a Fulkerson-cover?

In this paper, we solve Problem 1.2. The main result is Theorem 1.3.

Theorem 1.3

Each graph in $M_{0, 1, 2, \ldots , k-2, k-1}$ for $k>2$ has a Fulkerson-cover.

2 Preliminaries

In this section, some necessary definitions, constructions and the lemma are given.

Let $X\subseteq V(G)$ and $Y\subseteq E(G)$. We use $G{\setminus } X$ to denote the subgraph of G obtained from G by deleting all the vertices of X and all the edges incident with X. While $G{\setminus } Y$ to denote the subgraph of G obtained from G by deleting all the edges of Y. The edge-cut of G associated with X, denoted by $\partial _{G}(X)$, is the set of edges of G with exactly one end in X. The edge set $C=\partial _{G}(X)$ is called a k-edge-cut if $|\partial _{G}(X)|=k$. A cycle of G is a subgraph of G with each vertex of even degree. A circuit of G is a minimal 2-regular cycle of G. A graph G is called cyclically k-edge-connected if at least k edges must be removed to disconnect it into two components, each of which contains a circuit.

Let $G_i$ be a cyclically 4-edge-connected snark with excessive index at least 5, for $i=0,1$. Let $x_iy_i$ be an edge of $G_i$ and $x_i^0, x_i^1 (y_i^0, y_i^1)$ be the neighbors of $x_i$ ($y_i$). Let $H_i$ be the graph obtained from $G_i$ by deleting the vertices $x_i$ and $y_i$. Let $\{G; G_0, G_1\}$ be the graph obtained from the disjoint union of $H_0, H_1$ by adding six vertices $a_0, b_0, c_0, a_1, b_1, c_1$ and 13 edges $a_0y_0^0, a_0x_1^0, a_0c_0, c_0b_0, b_0y_0^1, b_0x_1^1, b_1x_0^1, b_1y_1^1, b_1c_1, c_1a_1, a_1x_0^0, a_1y_1^0, c_0c_1$. The graphs of this type are denoted as $E_{0,1}$ (see Fig. 1).

Fig. 1

$\{G;G_0, G_1\}$

The families of graphs $E_{0,1, \ldots ,(k-1)}$ ($k\ge 2$) and $M_{0,1, \ldots ,(k-1)}$ ($k\ge 2$) are constructed by Chen as follows:

• 1. $\{G; G_0, G_1\}\in E_{0,1}$ with $A_j=\{a_j, b_j, c_j\}$ for $j=0, 1$.

• 2. For $3\le i\le k, \{G; G_0, G_1, \ldots ,G_{i-1}\}$ is obtained from $\{G; G_0, G_1, \ldots , G_{i-2}\}\in E_{0,1, \ldots ,(i-2)}$ by adding $H_{i-1}$ and $A_{i-1}=\{a_{i-1}, b_{i-1}, c_{i-1}\}$ and by inserting a vertex $v_{i-3}$ into $e_0$, where $e_0$ is the edge incident with $c_0$ different from $a_0c_0$ and $b_0c_0$, such that the following conditions (i), (ii) and (iii) hold.

• (i) $G_{i-1}$ is a cyclically 4-edge-connected snark with excessive index at least 5 (note that $x_{i-1}y_{i-1}$ is an edge of $G_{i-1}$ and $x_{i-1}^0, x_{i-1}^1$ (resp. $y_{i-1}^0, y_{i-1}^1$) are the neighbors of $x_{i-1}$ (resp. $y_{i-1}$));

• (ii) $H_{i-1}=G_{i-1}\backslash \{x_{i-1}, y_{i-1}\}$;

• (iii) $a_{i-1}$ is adjacent to $x_0^0$ and $y_{i-1}^0, b_{i-1}$ is adjacent to $x_0^1$ and $y_{i-1}^1, a_{i-2}$ is adjacent to $x_{i-1}^0$ and $y_{i-2}^0$, $b_{i-2}$ is adjacent to $x_{i-1}^1$ and $y_{i-2}^1, c_{i-1}$ is adjacent to $a_{i-1}, b_{i-1}$ and $v_{i-3}$, and the other edges of $\{G; G_0, G_1, \ldots ,G_{i-2}\}$ remain the same:

• 3. $\{G; G_0, G_1, \ldots ,G_{i-1}\}\in E_{0,1, \ldots ,(i-1)}$.

For example, $\{G;G_0, G_1, G_2\}$ and $\{G;G_0, G_1, G_2, G_3\}$ are shown in Fig. 2.

Fig. 2

$\{G;G_0, G_1, G_2\}$ and $\{G;G_0, G_1, G_2, G_3\}$

The class of graphs constructed by Esperet et al. is a special case for $k=3$ of $E_{0,1, \ldots ,(k-1)}$. If the excessive index and non 3-edge-colorability of $G_i\ (i=0, 1, 2,\ldots , (k-1))$ are ignored and only assume that $G_i$ has a Fulkerson-cover, then we obtain infinite families of bridgeless cubic graphs. We denote graphs of this type as $M_{0,1,2, \ldots ,(k-1)}$ for $k\ge 2$.

The following Lemma is very import in our main proofs;

Lemma 2.1

(Hao et al. [8]) A bridgeless cubic graph G has a Fulkerson-cover if and only if there are two disjoint matchings $M_1$ and $M_2$, such that $M_1\cup M_2$ is a cycle and $\overline{G{\setminus } M_i}$ is 3-edge colorable, for each $i=1, 2$, where $\overline{G{\setminus } M_i}$ is the graph obtained from $G{\setminus } M_i$ by suppressing all degree-2-vertices.

3 Each Graph in $M_{0, 1, 2, \ldots , k-2, k-1}$ Has a Fulkerson Cover

We give the results according to the parity of k.

Theorem 3.1

Let k be an even integer and $k\ge 4$. If $\Gamma \in M_{0,1,2, \ldots ,k-2, k-1}$, then $\Gamma$ has a Fulkerson-cover.

Proof

Since $\Gamma \in M_{0,1,2, \ldots ,k-2, k-1}$, assume $\Gamma =\{G; G_0, G_1, \ldots ,G_{k-2}, G_{k-1}\}$.

Since $G_{i}$ has a Fulkerson-cover, for each $i=0,1,\ldots ,k-1$, suppose that $\{M_i^1, M_i^2, M_i^3$ $, M_i^4, M_i^5, M_i^6\}$ is the Fulkerson-cover of $G_{i}$. Let $B_i^{2}$ be the set of edges in $G_i$ covered twice by $\{M_i^1, M_i^2, M_i^3 \}$ and $B_i^{0}$ be the set of edges in $G_i$ which are not covered by $\{M_i^1, M_i^2, M_i^3 \}$. Note that $B_i^{2} \cup B_i^{0}$ is an even cycle, and $\overline{G_i{\setminus } B_i^{2}}$ and $\overline{G_i{\setminus } B_i^{0}}$ can be colored by three colors. Then $B_i^{2}$ and $B_i^{0}$ are the desired disjoint matchings of $G_i$ as in Lemma  2.1. By choosing three perfect matchings of $G_{i}$, for each $i=0, 1,\ldots , k-1$, we can obtain two desired disjoint matchings $B_i^{2}$ and $B_i^{0}$ such that $x_iy_i\in B_i^{2}\cup B_i^{0}$ or $x_{i}, y_i\not \in V(B_i^{2}\cup B_i^{0})$.

Fig. 3

$\{G; G_0, G_1, \ldots ,G_{k-1}\}$ for even k

Three perfect matchings $\{M_i^1, M_i^2, M_i^3 \}$ of $G_i$ are chosen such that $x_{i}, y_i\not \in V(B_i^{2} \cup B_i^{0})$ if i is even; And three perfect matchings $\{M_i^1, M_i^2, M_i^3 \}$ of $G_i$ are chosen such that $x_iy_i\in B_i^{2}\cup B_i^{0}$ if i is odd. Without loss of generality, assume that $x_iy_i\in B_i^{2}$ and $x_i^0x_i, y_i^0y_i\in B_i^{0}$ for odd i.

$$\begin{aligned} \mathrm {Let}\ B_0=&\left( B_0^2-x_0y_0\right) \cup \left( B_1^0-\left\{ x_1^0x_1, y_1^0y_1\right\} \right) \cup \bigcup \limits _{i=2}^{k-1}\left( B_i^2-{x_iy_i}\right) \cup \bigcup \limits _{i=2}^{k-1}a_ic_i \\&\cup \bigcup \limits _{j=1}^{\frac{k-4}{2}} v_{2j-1}v_{2j}\cup \left\{ c_0v_{k-3}, c_1v_0, y_1^0a_1, x_1^0a_0\right\} ,\ \mathrm {and}\\ B_2=&\left( B_0^0-\left\{ x_0x_0^0,y_0y_0^0\right\} \right) \cup \left( B_1^2-{x_1y_1}\right) \cup \bigcup \limits _{i=2}^{k-1}\left( B_i^0-\left\{ x_ix_i^0, y_iy_i^0\right\} \right) \\&\cup \bigcup \limits _{j=1}^{\frac{k-2}{2}}\left\{ y_{2j+1}^0a_{2j+1}, x_{2j+1}^0a_{2j}\right\} \cup \bigcup \limits _{i=2}^{k-1} v_{i-2}c_i\cup \{a_0c_0, a_1c_1\}. \end{aligned}$$

Clearly, $B_0\cup B_2$ is an even cycle C. See Fig. 3.

If i is odd, by $x_iy_i\in B_i^{2}$, there exists a maximal path containing only 2-degree vertices as inter vertices in the graph $G_i{\setminus } B_i^0$, say $u_i^0\cdots y_ix_i\cdots u_i^1$, which corresponds to an edge $u_i^0u_i^1$ in the graph $\overline{G_i{\setminus } B_i^0}$ (see Fig. 4). From $x_i^0x_i, y_i^0y_i\in B_i^{0}$, there exist two maximal paths containing only 2-degree vertices as inter vertices in the graph $G_i{\setminus } B_i^2$, say $u_i^2\cdots x_i^0x_ix_i^1\cdots u_i^3$ and $u_i^5\cdots y_i^0y_iy_i^1\cdots u_i^4$, which correspond to $u_i^2u_i^3$ and $u_i^4u_i^5$, respectively, in the graph $\overline{G_i{\setminus } B_i^2}$ (see Fig. 5).

If i is even, by $x_{i}, y_i\not \in V(B_i^{2})$, there exist four maximal paths containing only 2-degree vertices as inter vertices in the graph $G_i{\setminus } B_i^2$, say $u_i^0\cdots x_i^1x_i$ (maybe $u_i^0=x_i^1$), $u_i^1\cdots x_i^0x_i$ (maybe $u_i^1=x_i^0$), $u_i^2\cdots y_i^1y_i$ (maybe $u_i^2=y_i^1$) and $u_i^3\cdots y_i^0y_i$, which correspond to four edges $u_i^0x_i$, $u_i^1x_i$, $u_i^2y_i$ and $u_i^3y_i$, respectively, in the graph $\overline{G_i{\setminus } B_i^2}$ (see Fig. 6).

Fig. 4

$\overline{G_i{\setminus } B_i^0}$ with $x_iy_i\in B_i^{2}$

Fig. 5

$\overline{G_i{\setminus } B_i^2}$ with $x_iy_i\in B_i^{2}$

Fig. 6

$\overline{G_i{\setminus } B_i^2}$ with $x_{i}, y_i\not \in V(B_i^{2})$

Fig. 7

$\overline{G_i{\setminus } B_i^0}$ with $x_{i}, y_i\not \in V(B_i^{2})$

Similarly, by $x_{i}, y_i\not \in V(B_i^{0})$, there exist four maximal paths containing only 2-degree vertices as inter vertices in the graph $G_i{\setminus } B_i^0$, say $u_i^4\cdots x_i^1x_i$ (maybe $u_i^4=x_i^1$), $u_i^5\cdots x_i^0x_i$ (maybe $u_i^5=x_i^0$), $u_i^6\cdots y_i^1y_i$ (maybe $u_i^6=y_i^1$) and $u_i^7\cdots y_i^0y_i$ (maybe $u_i^7=y_i^0$), which correspond to four edges $u_i^4x_i$, $u_i^5x_i$, $u_i^6y_i$ and $u_i^7y_i$, respectively, in $\overline{G_i{\setminus } B_i^0}$ (see Fig. 7).

From the construction of $\Gamma$, we know that $\overline{\Gamma {\setminus } B_0}$ (see Fig. 8) is

$$\begin{aligned}&\left( \overline{G_1{\setminus } B_1^0}-u_1^0u_1^1\right) \cup \bigcup \limits _{j=0}^{\frac{k-2}{2}}\left( \overline{G_{2j}{\setminus } B_{2j}^2}-\{x_{2j}, y_{2j}\}\right) \cup \bigcup \limits _{j=1}^{\frac{k-2}{2}}\left( \overline{G_{2j+1}{\setminus } B_{2j+1}^2}\right. \\&\quad -\left. \left\{ u_{2j+1}^2u_{2j+1}^3, u_{2j+1}^4u_{2j+1}^5\right\} \right) \cup \left\{ u_1^0b_1, u_1^1b_0, b_1u_2^0, b_1u_2^1, u_0^2b_0, u_0^3b_0\right\} \\&\quad \cup \bigcup \limits _{j=1}^{\frac{k-2}{2}} \left\{ u_{2j}^3u_{2j+1}^2, u_{2j}^2b_{2j}, u_{2j+1}^3b_{2j}, u_{2j+1}^5u_{2j+2}^1, u_{2j+1}^4b_{2j+1}, u_{2j+2}^0b_{2j+1}, b_{2j}b_{2j+1}\right\} . \end{aligned}$$

And $\overline{\Gamma {\setminus } B_2}$ (see Fig. 8) is

$$\begin{aligned}&\left( \overline{G_1{\setminus } B_1^2}-\left\{ u_1^2u_1^3, u_1^4u_1^5\right\} \right) \cup \bigcup \limits _{j=0}^{\frac{k-2}{2}}\left( \overline{G_{2j}{\setminus } B_{2j}^0}-\{x_{2j}, y_{2j}\}\right) \\&\quad \cup \bigcup \limits _{j=1}^{\frac{k-2}{2}} \left( \overline{G_{2j+1}{\setminus } B_{2j+1}^0}-u_{2j+1}^0u_{2j+1}^1\right) \cup \left\{ u_1^4b_1, u_1^5u_2^5, b_1u_2^4, u_1^3b_0, u_0^7u_1^2, u_0^6b_0, b_0b_1\right\} \\&\quad \cup \bigcup \limits _{j=1}^{\frac{k-2}{2}}\left\{ u_{2j}^6b_{2j}, u_{2j}^7b_{2j}, b_{2j}u_{2j+1}^1, u_{2j+1}^0b_{2j+1}, b_{2j+1}u_{2j+2}^4, b_{2j+1}u_{2j+2}^5\right\} . \end{aligned}$$

Fig. 8

$\overline{\Gamma {\setminus } B_0}$ and $\overline{\Gamma {\setminus } B_2}$ for even k

If i is odd, because $B_i^{2}$ and $B_i^{0}$ are the desired disjoint matchings of $G_i$ as in Lemma  2.1, $\overline{G_i{\setminus } B_i^0}$ is 3-edge colorable. Thus there exists a 2-factor, say $C_i^0$, such that each component is an even circuit and $u_i^0u_i^1$ is not in the 2-factor $C_i^0$. Similarly, because $\overline{G_i{\setminus } B_i^2}$ is 3-edge colorable, there exists a 2-factor $C_i^2$ such that each component is an even circuit and $\{u_i^2u_i^3, u_i^4u_i^5\}$ is in the 2-factor $C_i^2$.

If i is even, because $\overline{G_i{\setminus } B_i^2}$ is 3-edge colorable, there exists a 2-factor $C_i^2$ such that each component is an even circuit and $u_i^0x_iu_i^1$ and $u_i^2y_iu_i^3$ are in the 2-factor $C_i^2$. Because $\overline{G_i{\setminus } B_i^0}$ is 3-edge colorable, there exists a 2-factor $C_i^0$ such that each component is an even circuit and $\{u_i^4x_iu_i^5, u_i^6y_iu_i^7\}$ is in the 2-factor $C_i^0$.

Then $\overline{\Gamma {\setminus } B_0}$ has a 2-factor:

$$\begin{aligned} C_1^0&\cup \bigcup \limits _{j=1}^{\frac{k-2}{2}}\left( C_{2j+1}^2-\left\{ u_{2j+1}^2u_{2j+1}^3, u_{2j+1}^4u_{2j+1}^5\right\} \right) \cup \bigcup \limits _{j=0}^{\frac{k-2}{2}}\left( C_{2j}^2-\{x_{2j}, y_{2j}\}\right) \\&\cup \bigcup \limits _{j=1}^{\frac{k-2}{2}}\left\{ b_{2j}u_{2j+1}^3, b_{2j}u_{2j}^2, u_{2j}^3u_{2j+1}^2, b_{2j+1}u_{2j+1}^4, b_{2j+1}u_{2j+2}^0, u_{2j+1}^5u_{2j+2}^1\right\} \\&\cup \left\{ b_0u_0^3, b_0u_0^2, b_1u_2^0, b_1u_2^1\right\} . \end{aligned}$$

And each component is an even circuit.

Similarly $\overline{\Gamma {\setminus } B_2}$ has a 2-factor:

$$\begin{aligned} \bigcup \limits _{j=1}^{\frac{k-2}{2}}C_{2j+1}^0&\cup \left( C_1^2-\left\{ u_1^2u_1^3, u_1^4u_1^5\right\} \right) \cup \bigcup \limits _{j=0}^{\frac{k-2}{2}}\left( C_{2j}^0-\{x_{2j}, y_{2j}\}\right) \\&\cup \left\{ b_0u_0^6, b_0u_1^3, u_0^7u_1^2, b_1u_1^4, u_1^5u_2^5, b_1u_2^4\right\} \\&\cup \bigcup \limits _{j=1}^{\frac{k-2}{2}}\left\{ u_{2j}^6b_{2j}, u_{2j}^7b_{2j}, u_{2j+2}^4b_{2j+1}, u_{2j+2}^5b_{2j+1}\right\} . \end{aligned}$$

And each component is an even circuit.

So $\overline{\Gamma {\setminus } B_0}$ and $\overline{\Gamma {\setminus } B_2}$ are 3-edge colorable. Therefore, $B_0$ and $B_2$ are the desired matchings in $\Gamma$ of Lemma 2.1. So $\Gamma =\{G; G_0, G_1, \ldots ,G_{k-2}, G_{k-1}\}$ has a Fulkerson-cover. $\square$

Theorem 3.2

Let k be an odd integer. If $H\in M_{0, 1, 2, \ldots , k-2, k-1}$, then H has a Fulkerson-cover.

Proof

By $H\in M_{0, 1, 2, \ldots , k-2, k-1}$, assume $H=\{G; G_0, G_1, \ldots ,G_{k-2}, G_{k-1}\}$. Since $G_{i}$ has a Fulkerson-cover, for each $i=0,1,\ldots ,k-1$, suppose that $\{M_i^1, M_i^2, M_i^3, M_i^4, M_i^5, M_i^6\}$ is the Fulkerson-cover of $G_{i}$. Let $B_i^{2}$ be the set of edges covered twice by $\{M_i^1, M_i^2, M_i^3 \}$ and $B_i^{0}$ be the set of edges which are not covered by $\{M_i^1, M_i^2, M_i^3 \}$. Now $B_i^{2} \cup B_i^{0}$ is an even cycle, and $\overline{G_i{\setminus } B_i^{2}}$ and $\overline{G_i{\setminus } B_i^{0}}$ can be colored by three colors. Then $B_i^{2}$ and $B_i^{0}$ are the desired disjoint matchings of $G_i$ as in Lemma 2.1. By choosing three perfect matchings of $G_{i}$, for each $i=0,1,\ldots ,k-1$, we can obtain two desired disjoint matchings $B_i^{2}$ and $B_i^{0}$ such that $x_{i}y_i\in B_i^{2}\cup B_i^{0}$ or $x_{i}, y_i\not \in V(B_i^{2} \cup B_i^{0})$. If i is even and $i\ne 0$, three perfect matchings of $G_i$ are chosen such that $x_{i}, y_i\not \in V(B_i^{2} \cup B_i^{0})$. If i is odd or $i=0$, three perfect matchings of $G_i$ are chosen such that $x_{i}y_i\in B_i^{2}\cup B_i^{0}$. Without loss of generality, assume that $x_iy_i\in B_i^{2}$ and $x_i^0x_i, y_i^0y_i\in B_i^{0}$ if $i=0$ or i is odd.

Let

$$\begin{aligned} B_0&= \left( B_0^2-x_0y_0\right) \cup \left( B_1^0-\left\{ x_1^0x_1, y_1^0y_1\right\} \right) \cup \bigcup \limits _{i=2}^{k-1}\left( B_i^2-{x_iy_i}\right) \\&\cup \left\{ y_1^0a_1, x_1^0a_0, c_1v_0\right\} \cup \bigcup \limits _{i=2}^{k-1}a_ic_i\cup \bigcup \limits _{j=0}^{\frac{k-5}{2}}v_{2j+1}v_{2j+2}, \end{aligned}$$

Fig. 9

$\{G; G_0, G_1, \ldots ,G_{k-2}, G_{k-1}\}$ for odd k

If i is odd or $i=0$, by $x_iy_i\in B_i^{2}$, there exists a maximal path containing only 2-degree vertices as inter vertices in the graph $G_i\backslash B_i^0$, say $u_i^0\cdots y_ix_i\cdots u_i^1$, which corresponds to an edge $u_i^0u_i^1$ in the graph $\overline{G_i{\setminus } B_i^0}$ (see Fig. 4); by $x_i^0x_i, y_i^0y_i\in B_i^{0}$, there exist two distinct maximal path containing only 2-degree vertices as inter vertices in the graph $G_i{\setminus } B_i^2$, say $u_i^2\cdots x_i^0x_ix_i^1\cdots u_i^3$ and $u_i^5\cdots y_i^0y_iy_i^1\cdots u_i^4$ which correspond to edges $u_i^2u_i^3$ and $u_i^4u_i^5$, respectively, in the graph $\overline{G_i{\setminus } B_i^2}$ (see Fig. 5).

$$\begin{aligned} B_2&= \left( B_1^2-{x_1y_1}\right) \cup \bigcup \limits _{i=2}^{k-1} \left( B_i^0-\left\{ x_ix_i^0, y_iy_i^0\right\} \right) \cup \left( B_0^0-\left\{ x_0x_0^0, y_0y_0^0\right\} \right) \\&\cup \{a_1c_1\}\cup \bigcup \limits _{i=1}^{\frac{k-1}{2}}\left\{ a_{2i}x_{2i+1}^0, a_{2i+1}y_{2i+1}^0\right\} \cup \bigcup \limits _{i=2}^{k-1}\{ v_{i-2}c_i\}. \end{aligned}$$

See Fig. 9. Clearly, $B_0\cup B_2$ is an even cycle C.

If i is even and $i\ne 0$, since $x_{i}, y_i\not \in V(B_i^{2})$, there exist four maximal paths containing only 2-degree vertices as inter vertices in the graph $G_i{\setminus } B_i^2$, say $u_i^0\cdots x_i^1x_i$ (maybe $u_i^0=x_i^1$), $u_i^1\cdots x_i^0x_i$ (maybe $u_i^1=x_i^0$), $u_i^2\cdots y_i^1y_i$ (maybe $u_i^2=y_i^1$) and $u_i^3\cdots y_i^0y_i$ (maybe $u_i^3=y_i^0$), which correspond to edges $u_i^0x_i$, $u_i^1x_i$, $u_i^2y_i$ and $u_i^3y_i$, respectively, in the graph $\overline{G_i{\setminus } B_i^2}$ (See Fig. 6). Similarly, by $x_{i}, y_i\not \in V(B_i^{0})$, there exist four maximal paths containing only 2-degree vertices as inter vertices in the graph $G_i{\setminus } B_i^0$, say $u_i^4\cdots x_i^1x_i$ (maybe $u_i^4=x_i^1$), $u_i^5\cdots x_i^0x_i$ (maybe $u_i^5=x_i^0$), $u_i^6\cdots y_i^1y_i$ (maybe $u_i^6=y_i^1$) and $u_i^7\cdots y_i^0y_i$ which correspond to edges $u_i^4x_i$, $u_i^5x_i$, $u_i^6y_i$ and $u_i^7y_i$,respectively, in the graph $\overline{G_i{\setminus } B_i^0}$ (see Fig. 7).

If $k=1$, then $H=G_0$ which has a Fulkerson-cover.

If $k\ge 2$, we will prove $\overline{H{\setminus } B_0}$ and $\overline{H{\setminus } B_2}$ are 3-edge colorable in the following.

From the construction of H, one has that $\overline{H{\setminus } B_0}$ (see Fig. 10) is

$$\begin{aligned}&\left( \overline{G_0{\setminus } B_0^2}-\left\{ u_0^2u_0^3, u_0^4u_0^5\right\} \right) \cup \left( \overline{G_1{\setminus } B_1^0}-u_1^0u_1^1\right) \\&\quad \cup \bigcup \limits _{j=1}^{\frac{k-1}{2}}\left\{ u_{2j}^2b_{2j}, u_{2j+1}^3b_{2j}, u_{2j+1}^2u_{2j}^3\right\} \\&\quad \cup \bigcup \limits _{j=1}^{\frac{k-3}{2}}\left\{ u_{2j+1}^4b_{2j+1}, u_{2j+1}^5u_{2j+2}^1, u_{2j+2}^0b_{2j+1}, b_{2j}b_{2j+1}\right\} \\&\quad \cup \left\{ u_0^5c_0, u_0^4b_0, b_0c_0, b_{k-1}c_0, u_1^1b_0, u_1^0b_1, u_2^0b_1, u_2^1b_1\right\} \cup Q_0\cup Q_1, \end{aligned}$$

where $Q_1=\bigcup \nolimits _{j=1}^{\frac{k-3}{2}}(\overline{G_{2j+1}{\setminus } B_{2j+1}^2}-\{u_{2j+1}^2u_{2j+1}^3, u_{2j+1}^4u_{2j+1}^5\})$ and $Q_0=\bigcup \nolimits _{j=1}^{\frac{k-1}{2}}(\overline{G_{2j}{\setminus } B_{2j}^2}-\{x_{2j}, y_{2j}\}).$ And $\overline{H{\setminus } B_2}$ (see Fig. 10) is

$$\begin{aligned}&\left( \overline{G_1{\setminus } B_1^2}-\left\{ u_1^2u_1^3, u_1^4u_1^5\right\} \right) \cup \left( \overline{G_0{\setminus } B_0^0}-u_0^0u_0^1\right) \\&\quad \cup \left\{ u_1^5u_2^5, u_1^4b_1, u_2^4b_1, u_1^2c_0, u_1^3b_0,b_0c_0, u_0^0b_0, c_0b_1\right\} \\&\quad \cup \bigcup \limits _{j=1}^{\frac{k-1}{2}}\left( (\overline{G_{2j}{\setminus } B_{2j}^0}-\{x_{2j}, y_{2j}\})\right. \\&\quad \left. \cup \left\{ u_{2j}^6b_{2j}, u_{2j+1}^1b_{2j}, u_{2j}^7b_{2j}\right\} \right) \\&\quad \cup \bigcup \limits _{j=1}^{\frac{k-3}{2}}\left( \left( \overline{G_{2j+1}{\setminus } B_{2j+1}^0}-\left\{ u_{2j+1}^0u_{2j+1}^1\right\} \right) \right. \\&\quad \left. \cup \left\{ u_{2j+1}^0b_{2j+1}, u_{2j+2}^4b_{2j+1}, u_{2j+2}^5b_{2j+1}\right\} \right) . \end{aligned}$$

If i is odd or $i=0$, because $\overline{G_i{\setminus } B_i^0}$ is 3-edge colorable, there exists a 2-factor $C_i^0$ such that each component is an even circuit and $u_i^0u_i^1$ is not in the 2-factor $C_i^0$. Because $\overline{G_i{\setminus } B_i^2}$ is 3-edge colorable, there exists a 2-factor $C_i^2$ such each component is an even circuit and $u_i^2u_i^3, u_i^4u_i^5$ are in the 2-factor $C_i^2$.

Fig. 10

$\overline{H{\setminus } B_0}$ and $\overline{H{\setminus } B_2}$ with odd k

If i is even and $i\ne 0$, because $\overline{G_i{\setminus } B_i^2}$ is 3-edge colorable, there exists a 2-factor $C_i^2$ such each component is an even circuit and two paths with length two $u_i^0x_iu_i^1$ and $u_i^2y_iu_i^3$ are in the 2-factor $C_i^2$. Similarly, because $\overline{G_i{\setminus } B_i^0}$ is 3-edge colorable, there exists a 2-factor $C_i^0$ such each component is an even circuit and $u_i^4x_iu_i^5, u_i^6y_iu_i^7$ are in the 2-factor $C_i^0$.

Then $\overline{H{\setminus } B_0}$ (see Fig. 10) has a 2-factor:

$$\begin{aligned}&\left( C_0^2-\left\{ u_0^4u_0^5, u_0^2u_0^3\right\} \right) \cup C_1^0\cup \bigcup \limits _{j=1}^{\frac{k-3}{2}}\left( C_{2j+1}^2-\left\{ u_{2j+1}^2u_{2j+1}^3, u_{2j+1}^4u_{2j+1}^5\right\} \right) \\&\quad \cup \bigcup \limits _{j=1}^{\frac{k-1}{2}}\left( C_{2j}^2-\{x_{2j}, y_{2j}\}\right) \cup \bigcup \limits _{j=1}^{\frac{k-1}{2}}\left\{ b_{2j}u_{2j+1}^3, b_{2j}u_{2j}^2, u_{2j}^3u_{2j+1}^2\right\} \\&\quad \cup \bigcup \limits _{j=1}^{\frac{k-3}{2}}\left\{ b_{2j+1}u_{2j+1}^4,b_{2j+1}u_{2j+2}^0, u_{2j+1}^5u_{2j+2}^1\right\} \cup \left\{ b_0u_0^4, b_1u_2^0, b_1u_2^1, b_0c_0, u_0^5c_0\right\} . \end{aligned}$$

and each component is an even circuit. $\overline{H{\setminus } B_2}$ has a 2-factor:

$$\begin{aligned}&C_0^0\cup \left( C_1^2-\left\{ u_1^2u_1^3, u_1^4u_1^5\right\} \right) \cup \bigcup \limits _{j=1}^{\frac{k-1}{2}}\left( (C_{2j}^0-\{x_{2j}, y_{2j}\})\cup \left\{ u_{2j}^6b_{2j}, u_{2j}^7b_{2j}\right\} \right) \\&\quad \cup \bigcup \limits _{j=1}^{\frac{k-3}{2}}C_{2j+1}^0\cup \bigcup \limits _{j=1}^{\frac{k-3}{2}}\left\{ u_{2j+2}^4b_{2j+1}, u_{2j+2}^5b_{2j+1}\right\} \\&\quad \cup \left\{ c_0u_1^2, b_0c_0, b_0u_1^3, u_1^5u_2^5, u_1^4b_1, u_2^4b_1\right\} \end{aligned}$$

And each component is an even circuit.

So $\overline{H{\setminus } B_0}$ and $\overline{H{\setminus } B_2}$ are 3-edge colorable. Therefore, $B_0$ and $B_2$ are the desired matchings of Lemma 2.1 and $H=\{G; G_0, G_1,$ $\ldots ,G_{k-2},$ $G_{k-1}\}$ has a Fulkerson-cover. $\square$

From Theorems 3.1 and 3.2, we get the Theorem 1.3 that every graph in $M_{0,1,2,\ldots ,(k-1)}$ has a Fulkerson-cover.

4 Remark on Treelike Snarks

The families of graphs $E_{0,1, \ldots ,(k-1)}$ and $M_{0,1, \ldots ,(k-1)}$ for $k\ge 2$, which are constructed by Chen [2], are set of graphs having all vertices not in $H_0, H_1, \ldots , H_{k-1}$ and not in ${a_i, b_i, c_i}$ on a path. Abreu et al. [1] proposed Treelike snarks which generalize this idea by considering an arbitrary tree instead of a path, but the graphs $H_i$ are all copies of the Petersen graph minus an edge. They proved that all such Treelike snarks have excessive index at least five.

In this paper, we prove that every graph in $M_{0,1,2, \ldots ,k-2, k-1}$ has a Fulkerson-cover. Since the Petersen graph has a Fulkerson cover, as a directive corollary of this result, each graph in the subclass of treelike snarks obtained by considering a path instead of an arbitrary tree has a Fulkerson cover. So we give a conjecture as follows:

Conjecture 4.1

(Conjecture) Every Treelike snarks proposed in [1] has a Fulkerson cover.