% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P14}{19(3)}{2012}
\usepackage{pstricks}
% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Polyhedral embeddings of snarks\\ with arbitrary  nonorientable genera}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Wenzhong Liu\thanks{The first author is the corresponding author,
supported by ``The Fundamental Research Funds for the Central Universities", No. NS2012143}\\
\small Department of Mathematics\\[-0.8ex]
\small Nanjing University of Aeronautics and Astronautics\\[-0.8ex]
\small 210016 Nanjing, P.R. China\\
\small\tt wzhliu7502@nuaa.edu.cn\\
\and
Yichao Chen\thanks{The work of the second author was partially supported by NNSFC under Grant No. 10901048}\qquad   \\
\small College of Mathematics and Econometrics\\[-0.8ex]
\small Hunan University\\[-0.8ex]
\small 410082 Changsha, P. R. China\\
\small\tt ycchen@hnu.edu.cn}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Nov 26, 2011}{Jul 10, 2012}{Aug 9, 2012}\\
\small Mathematics Subject Classifications: 05C10, 05C15}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
  Mohar and Vodopivec [Combinatorics, Probability and Computing
(2006) 15, 877-893] proved that for every integer $k$ ($k \geq 1$ and $k\neq 2$), there exists a snark
which polyhedrally embeds in $\mathbb{N}_k$ and presented the problem: Is there a snark that has a polyhedral embedding in the
Klein bottle? In the paper, we give a positive solution of the problem and strengthen Mohar and Vodopivec's  result.
We prove that for every integer $k$ ($k\geq 2$), there exists an infinite family of snarks with nonorientable genus
$k$ which polyhedrally embed in $\mathbb{N}_k$.
Furthermore, for every integer $k$ ($k> 0$), there exists a snark with nonorientable genus $k$ which polyhedrally
embeds in $\mathbb{N}_k$.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} polyhedral embedding; snark; nonorientable surface; nonorientable genus; Euler genus
\end{abstract}

\section{Introduction}

During a conference in 1968, Gr\"unbaum \cite{GR} conjectured that each cubic graph
with a polyhedral embedding in an orientable surface is 3-edge-colourable. A positive solution of this conjecture
would generalize the dual form of the Four-Color-Theorem to every orientable surface. The conjecture holds for the sphere from the results of Tait \cite{TA}
and Apple and Haken \cite{AH}. In \cite{KO2}, Kochol
disproved the conjecture by showing that there exist infinitely many snarks with
polyhedral embeddings in $\mathbb{S}_k$ $(k\geq 5)$. The smallest of the counterexamples
found by Kochol is a snark of order 74.
With the aid of computer, Mohar and Vodopivec \cite{MV1} proved  that for every cubic graph with
fewer than 30 vertices, the conjecture holds true. Furthermore, they proved that for every integer $k$ ($k \geq 1$ and $k\neq 2$), there exists a snark
which polyhedrally embeds in $\mathbb{N}_k,$ and proposed the following problem:

\begin{problem}\label{mvproblem} \emph{(Problem 5.3 of \cite{MV1})
Is there a snark that has a polyhedral embedding in the
Klein bottle?}
\end{problem}


 In the paper, we give a positive solution of Problem \ref{mvproblem} and strengthen Mohar and Vodopivec's result. Actually, we prove
 that for every integer $k$ ($k\geq 2$), there exists an infinite family of snarks with nonorientable genus
$k$ which polyhedrally embed in $\mathbb{N}_k$.
Furthermore, for every integer $k$ ($k> 0$), there exists a snark with nonorientable genus $k$ which polyhedrally
embeds in $\mathbb{N}_k$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminary}

 All graphs considered in this paper are connected. For some terminologies without description here, we may refer the reader to \cite{RD05, GT87, MT}.

 A \textit{surface} is a compact closed 2-dimensional manifold without
boundary. In topology, surfaces are classified into the \textit{orientable surface} $\mathbb{S}_m$,
with $m
 $ handles $(m\geq 0)$ and the \textit{nonorientable surface} $\mathbb{N}_k$,
with $k $ crosscaps $(k> 0)$. A graph embedding into a surface means
a \textit{cellular embedding}, so that every face of the embedding
is an open topological disk. The\emph{ orientable genus $\gamma(G)$} of a graph $G$ is the
smallest integer $k$ such that $G$ cellularly embeds into $\mathbb{S}_k$. Similarly, the\emph{ nonorientable genus $\widetilde{\gamma}(G)$} of a graph $G$ is the smallest integer
 $k$ such that $G$ cellularly embeds into $\mathbb{N}_k$.  The \emph{Euler genus ${\overline\gamma}(G)$}
of a graph $G$ is defined as $\min \{ 2\gamma(G), {\widetilde{\gamma}}(G) \}$. Also note that
${\overline\gamma}(G)= \min \{2-\chi{(\mathbb{S})} \mid $ G cellularly embeds into a surface $\mathbb{S}\}$, where
$\chi{(\mathbb{S})}$ denotes the Euler characteristic of a surface $\mathbb{S}$.
By the well-known formula $\widetilde{\gamma}(G)\leq 2\gamma{(G)}+1$, either
$\widetilde{\gamma}(G)=\overline{\gamma}(G)$ or  $\widetilde{\gamma}(G)=\overline{\gamma}(G)+1$.

 A graph $G$ is called a \emph{k-amalgamation} of two graphs $G_{1}$ and $G_{2}$, denoted by $G=G_{1}\bigcup_{k} G_{2}$,
if $G=G_{1}\bigcup G_{2}$
and $G_{1}\bigcap G_{2}$ is a set of $k$ vertices.
In \cite{AR},
 Archdeacon proved the following theorem:

 \medskip
 \begin{lemma}{\label{amalgamation}} (\cite{AR}, Theorem 1.1)
$$2-2k\leq \overline{\gamma}(G_{1})+ \overline{\gamma}(G_{2})-\overline{\gamma}(G_{1}{\bigcup}_{k}G_{2})\leq k^{2}-4.
$$
\end{lemma}


  An embedding of a graph $G$ is called \textit{polyhedral} if all facial walks are cycles, and any two of them
are either disjoint, intersect in one vertex, or intersect in one edge. If $G$ is a cubic graph, then
any two facial walks are either disjoint or intersect in precisely one edge.

  A \textit{snark} is a cyclically 4-edge-connected cubic graph of girth at least 5 with no 3-edge-coloring.
A graph is called a 4-\textit{snark} if it dose not admit a nowhere-zero
$\mathbb{Z}_2 \times \mathbb{Z}_2$-flow. It is well known that a nowhere-zero
$\mathbb{Z}_2 \times \mathbb{Z}_2$-flow in a cubic graph $G$ corresponds to a 3-edge-coloring of
$G$. Thus snarks form a proper
subclass of 4-snarks. Kochol \cite{KO1} introduced a general method to construct a 4-snark. It is based on the
following two steps.

 Suppose $v$ is a vertex of a graph $G$ and a graph $G'$ is obtained from $G$
 by the following process. Replace $v$ by a graph $H_{v}$ so that each edge $e$ of $G$
having one end $v$ now has one end from $H_{v}$. If $e$ is a loop incident with $v$, then both
ends of $e$ will now be from $H_{v}$. We call $G'$ a \textit{vertex superposition} of $G$.

 Suppose $e$ is an edge of $G$ with ends $u$ and $v$ and a graph $G'$ is constructed from $G$ as follows:
replace $e$ by a graph $H_{e}$ having at least two vertices. In other words,
we delete $e$ from $G$, pick two distinct vertices $u'$, $v'$ of $H_{e}$, and identify $u'$ with $u$
and $v'$ with $v$. We call $G'$ an \textit{edge superposition} of $G$. If $H_{e}$ is a 4-snark,
then $G'$ is called a 4-\textit{strong edge superposition} of $G$.

 A graph $G'$ is called a (4-\textit{strong})\textit{superposition} of a graph $G$ if $G'$ is obtained from
$G$ by some vertex and (4-\textit{strong}) edge superpositions. Kochol \cite{KO1} proved the following lemma:

\medskip
\begin{lemma}\label{Koch} (\cite{KO1}, Lemma 4.4) Let $G$ be a 4-strong superposition of a 4-snark, then $G$ is a 4-snark. \\

\end{lemma}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Main theorem}

  The Petersen graph $P$ is the smallest snark and has a polyhedral embedding in the
 projective plane, indicated in part $(b)$ of Figure \ref{Fig:Pete}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]\center
\begin{pspicture}(-3,-2.6)(8,2.5)
\psset{xunit=20pt,yunit=20pt}
%\psline(0,2)(-1.168,1.176) \psline(0,2)(1.168,1.176) \psline(0,2)(1.168,1.176)
%\pspolygon[linewidth=1.5pt](-1.9,.618,)(0,2)(1.9,.618)(1.18,-1.618)(-1.18,-1.618)

\pspolygon[linewidth=1.5pt](-2.853,.927,)(0,3)(2.853,.927)(1.763,-2.427)(-1.763,-2.427)
\psline(-1.9,.618)(-2.853,.927) \psline(0,2)(0,3)  \psline(1.9,.618)(2.853,.927)  \psline(1.18,-1.618)(1.763,-2.427)  \psline(-1.18,-1.618)(-1.763,-2.427)

\pspolygon[linewidth=1.5pt](0,2)(-1.18,-1.618)(1.9,.618)(-1.9,.618,)(1.18,-1.618)

\pscircle[fillcolor=white,fillstyle=solid](-1.9,.618,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](1.9,.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](1.18,-1.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](0,2){0.1}
\pscircle[fillcolor=white,fillstyle=solid](-1.18,-1.618){0.1}

\pscircle[fillcolor=white,fillstyle=solid](-2.853,.927,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](0,3){0.1}
\pscircle[fillcolor=white,fillstyle=solid](2.853,.927){0.1}
\pscircle[fillcolor=white,fillstyle=solid](1.763,-2.427){0.1}
\pscircle[fillcolor=white,fillstyle=solid](-1.763,-2.427){0.1}


\pscircle[linestyle=dashed](8,0){1.1}

\pspolygon[linewidth=1.5pt](5.147,.927,)(8,3)(10.853,.927)(9.763,-2.427)(6.237,-2.427)
\psline(6.1,.618)(5.147,.927) \psline(8,2)(8,3)  \psline(9.9,.618)(10.853,.927)  \psline(9.18,-1.618)(9.763,-2.427)  \psline(6.82,-1.618)(6.237,-2.427)


\psline[linecolor=blue](8.3,1.485)(8,2) \psline[linecolor=blue](6.82,-1.618)(7.7,-1.47)
\psline[linecolor=red](7.7,1.485)(8,2) \psline[linecolor=red](9.18,-1.618)(8.3,-1.47)
\psline[linecolor=green](6.1,.618)(6.7,.8)\psline(6.1,.618)(6.5,-.20)
\psline[linecolor=green](9.18,-.9)(9.18,-1.618)
\psline(9.9,.618)(9.45,.1)
\psline[linecolor=orange](9.9,.618)(9.2,.91)
\psline[linecolor=orange](6.82,-1.618)(6.8,-1.)


\pscircle[fillcolor=white,fillstyle=solid](6.1,.618,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](9.9,.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](9.18,-1.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](8,2){0.1}
\pscircle[fillcolor=white,fillstyle=solid](6.82,-1.618){0.1}

\pscircle[fillcolor=white,fillstyle=solid](5.147,.927,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](8,3){0.1}
\pscircle[fillcolor=white,fillstyle=solid](10.853,.927){0.1}
\pscircle[fillcolor=white,fillstyle=solid](9.763,-2.427){0.1}
\pscircle[fillcolor=white,fillstyle=solid](6.237,-2.427){0.1}
\put(-.2,-2.5){{$(a)$}} \put(5.3,-2.5){{$(b)$}}
\put(1.8,-.8){{$e$}} \put(7.5,-.8){{$e$}}


\end{pspicture}
\caption{$(a)$ the Petersen graph $P$ and $(b)$ the Petersen graph $P$ polyhedrally embeds in the projective plane}\label{Fig:Pete}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{figure}[h]\center
\begin{pspicture}(-.3,-1.6)(10,2.5)
\psset{xunit=15pt,yunit=15pt}
%\psline(0,2)(-1.168,1.176) \psline(0,2)(1.168,1.176) \psline(0,2)(1.168,1.176)
%\pspolygon[linewidth=1.5pt](-1.9,.618,)(0,2)(1.9,.618)(1.18,-1.618)(-1.18,-1.618)


%第二个图
\pscircle[linestyle=dashed](8,0){.82}

\pspolygon[linewidth=1.5pt](5.147,.927,)(8,3)(10.853,.927)(10.853,-2.427)(5.147,-2.427)
\psline(6.1,.618)(5.147,.927) \psline(8,2)(8,3)  \psline(9.9,.618)(10.853,.927)  \psline(9.18,-1.618)(10.853,-2.427)  \psline(6.82,-1.618)(5.147,-2.427)


\psline[linecolor=blue](8.3,1.485)(8,2) \psline[linecolor=blue](6.82,-1.618)(7.7,-1.47)
\psline[linecolor=red](7.7,1.485)(8,2) \psline[linecolor=red](9.18,-1.618)(8.3,-1.47)
\psline[linecolor=green](6.1,.618)(6.7,.8)\psline(6.1,.618)(6.5,-.20)
\psline[linecolor=green](9.18,-.9)(9.18,-1.618)
\psline(9.9,.618)(9.45,.1)
\psline[linecolor=orange](9.9,.618)(9.2,.91)
\psline[linecolor=orange](6.82,-1.618)(6.8,-1.)


\pscircle[fillcolor=white,fillstyle=solid](6.1,.618,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](9.9,.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](9.18,-1.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](8,2){0.1}
\pscircle[fillcolor=white,fillstyle=solid](6.82,-1.618){0.1}

\pscircle[fillcolor=white,fillstyle=solid](5.147,.927,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](8,3){0.1}
\pscircle[fillcolor=white,fillstyle=solid](10.853,.927){0.1}
\pscircle[fillcolor=white,fillstyle=solid](10.853,-2.427){0.1}
\pscircle[fillcolor=white,fillstyle=solid](5.147,-2.427){0.1}
\put(6.1,-.1){{$\cdots$}}

%第一个图，平移5.706
\pscircle[linestyle=dashed](2.294,0){.82}

\pspolygon[linewidth=1.5pt](-.532,.927,)(2.294,3)(5.147,.927)(5.147,-2.427)(-.532,-2.427)
\psline(0.394,.618)(-.532,.927) \psline(2.294,2)(2.294,3)  \psline(4.194,.618)(5.147,.927)  \psline(3.474,-1.618)(5.147,-2.427)  \psline(1.114,-1.618)(-.532,-2.427)


\psline[linecolor=blue](2.594,1.485)(2.294,2) \psline[linecolor=blue](1.114,-1.618)(1.994,-1.47)
\psline[linecolor=red](1.994,1.485)(2.294,2) \psline[linecolor=red](3.474,-1.618)(2.594,-1.47)
\psline[linecolor=green](0.394,.618)(0.994,.8)\psline(0.394,.618)(0.794,-.20)
\psline[linecolor=green](3.474,-.9)(3.474,-1.618)
\psline(4.194,.618)(3.744,.1)
\psline[linecolor=orange](4.194,.618)(3.494,.91)
\psline[linecolor=orange](1.114,-1.618)(1.049,-1.)


\pscircle[fillcolor=white,fillstyle=solid](0.394,.618,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](4.194,.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](3.474,-1.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](2.294,2){0.1}
\pscircle[fillcolor=white,fillstyle=solid](1.114,-1.618){0.1}

\pscircle[fillcolor=white,fillstyle=solid](-.532,.927,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](2.294,3){0.1}
\pscircle[fillcolor=white,fillstyle=solid](5.147,.927){0.1}
\pscircle[fillcolor=white,fillstyle=solid](5.147,-2.427){0.1}
\pscircle[fillcolor=white,fillstyle=solid](-.532,-2.427){0.1}



%第三个图 由第二个图平移2
\pscircle[linestyle=dashed](16,0){.82}

\pspolygon[linewidth=1.5pt](13.147,.927,)(16,3)(18.853,.927)(18.853,-2.427)(13.147,-2.427)
\psline(14.1,.618)(13.147,.927) \psline(16,2)(16,3)  \psline(17.9,.618)(18.853,.927)  \psline(17.18,-1.618)(18.853,-2.427)  \psline(14.82,-1.618)(13.147,-2.427)


\psline[linecolor=blue](16.3,1.485)(16,2) \psline[linecolor=blue](14.82,-1.618)(15.7,-1.47)
\psline[linecolor=red](15.7,1.485)(16,2) \psline[linecolor=red](17.18,-1.618)(16.3,-1.47)
\psline[linecolor=green](14.1,.618)(14.7,.8)\psline(14.1,.618)(14.5,-.20)
\psline[linecolor=green](17.18,-.9)(17.18,-1.618)
\psline(17.9,.618)(17.45,.1)
\psline[linecolor=orange](17.9,.618)(17.2,.91)
\psline[linecolor=orange](14.82,-1.618)(14.8,-1.)


\pscircle[fillcolor=white,fillstyle=solid](14.1,.618,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](17.9,.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](17.18,-1.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](16,2){0.1}
\pscircle[fillcolor=white,fillstyle=solid](14.82,-1.618){0.1}

\pscircle[fillcolor=white,fillstyle=solid](13.147,.927,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](16,3){0.1}
\pscircle[fillcolor=white,fillstyle=solid](18.853,.927){0.1}
\pscircle[fillcolor=white,fillstyle=solid](18.853,-2.427){0.1}
\pscircle[fillcolor=white,fillstyle=solid](13.147,-2.427){0.1}

\end{pspicture}
\caption{The graph $G_{8k+2}$ resulting from $k$ copies of the Petersen graph polyhedrally embeds in $\mathbb{N}_k$}\label{Fig:poly}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%图3
\begin{figure}[h]\center
\begin{pspicture}(-.3,-1.6)(10,2.5)
\psset{xunit=15pt,yunit=15pt}
%\psline(0,2)(-1.168,1.176) \psline(0,2)(1.168,1.176) \psline(0,2)(1.168,1.176)
%\pspolygon[linewidth=1.5pt](-1.9,.618,)(0,2)(1.9,.618)(1.18,-1.618)(-1.18,-1.618)


%第二个图
\pscircle[linestyle=dashed](8,0){.82}

\pspolygon[linewidth=1.5pt](5.147,3,)(8,3)(10.853,3)(10.853,-2.427)(5.147,-2.427)
\psline(6.1,.618)(5.147,1.9) \psline(8,2)(8,3)  \psline(9.9,.618)(10.853,.927)  \psline(9.18,-1.618)(10.853,-1.8)  \psline(6.82,-1.618)(5.147,-1.)


\psline[linecolor=blue](8.3,1.485)(8,2) \psline[linecolor=blue](6.82,-1.618)(7.7,-1.47)
\psline[linecolor=red](7.7,1.485)(8,2) \psline[linecolor=red](9.18,-1.618)(8.3,-1.47)
\psline[linecolor=green](6.1,.618)(6.7,.8)\psline(6.1,.618)(6.5,-.20)
\psline[linecolor=green](9.18,-.9)(9.18,-1.618)
\psline(9.9,.618)(9.45,.1)
\psline[linecolor=orange](9.9,.618)(9.2,.91)
\psline[linecolor=orange](6.82,-1.618)(6.8,-1.)
%new added
\psline[linestyle=dashed](10.853,3)(13.147,3)
\psline[linestyle=dashed](10.853,-2.427)(13.147,-2.427)


\pscircle[fillcolor=white,fillstyle=solid](6.1,.618,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](9.9,.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](9.18,-1.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](8,2){0.1}
\pscircle[fillcolor=white,fillstyle=solid](6.82,-1.618){0.1}

\pscircle[fillcolor=white,fillstyle=solid](5.147,1.9,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](8,3){0.1}
\pscircle[fillcolor=white,fillstyle=solid](10.853,.927){0.1}
\pscircle[fillcolor=white,fillstyle=solid](10.853,-2.427){0.1}
\pscircle[fillcolor=white,fillstyle=solid](10.853,-1.8){0.1}
\pscircle[fillcolor=white,fillstyle=solid](5.147,-1){0.1}
\put(6.1,-.1){{$\cdots$}}

%第一个图，平移5.706
\pscircle[linestyle=dashed](2.294,0){.82}

\pspolygon[linewidth=1.5pt](-.532,.927,)(2.294,3)(5.147,3)(5.147,-2.427)(-.532,-2.427)
\psline(0.394,.618)(-.532,.927) \psline(2.294,2)(2.294,3)  \psline(4.194,.618)(5.147,.927)  \psline(3.474,-1.618)(5.147,-1.8)  \psline(1.114,-1.618)(-.532,-2.427)
\pscircle[fillcolor=white,fillstyle=solid](5.14,.927,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](5.14,3,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](10.853,3,){0.1}
\psline[linecolor=blue](2.594,1.485)(2.294,2) \psline[linecolor=blue](1.114,-1.618)(1.994,-1.47)
\psline[linecolor=red](1.994,1.485)(2.294,2) \psline[linecolor=red](3.474,-1.618)(2.594,-1.47)
\psline[linecolor=green](0.394,.618)(0.994,.8)\psline(0.394,.618)(0.794,-.20)
\psline[linecolor=green](3.474,-.9)(3.474,-1.618)
\psline(4.194,.618)(3.744,.1)
\psline[linecolor=orange](4.194,.618)(3.494,.91)
\psline[linecolor=orange](1.114,-1.618)(1.049,-1.)


\pscircle[fillcolor=white,fillstyle=solid](0.394,.618,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](4.194,.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](3.474,-1.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](2.294,2){0.1}
\pscircle[fillcolor=white,fillstyle=solid](1.114,-1.618){0.1}

\pscircle[fillcolor=white,fillstyle=solid](-.532,.927,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](2.294,3){0.1}
\pscircle[fillcolor=white,fillstyle=solid](5.147,.927){0.1}
\pscircle[fillcolor=white,fillstyle=solid](5.147,-1.8){0.1}
\pscircle[fillcolor=white,fillstyle=solid](-.532,-2.427){0.1}



%第三个图 由第二个图平移2
\pscircle[linestyle=dashed](16,0){.82}

\pspolygon[linewidth=1.5pt](13.147,3,)(16,3)(18.853,.927)(18.853,-2.427)(13.147,-2.427)
\psline(14.1,.618)(13.147,1.9) \psline(16,2)(16,3)  \psline(17.9,.618)(18.853,.927)  \psline(17.18,-1.618)(18.853,-2.427)  \psline(14.82,-1.618)(13.147,-1)


\psline[linecolor=blue](16.3,1.485)(16,2) \psline[linecolor=blue](14.82,-1.618)(15.7,-1.47)
\psline[linecolor=red](15.7,1.485)(16,2) \psline[linecolor=red](17.18,-1.618)(16.3,-1.47)
\psline[linecolor=green](14.1,.618)(14.7,.8)\psline(14.1,.618)(14.5,-.20)
\psline[linecolor=green](17.18,-.9)(17.18,-1.618)
\psline(17.9,.618)(17.45,.1)
\psline[linecolor=orange](17.9,.618)(17.2,.91)
\psline[linecolor=orange](14.82,-1.618)(14.8,-1.)


\pscircle[fillcolor=white,fillstyle=solid](14.1,.618,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](17.9,.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](17.18,-1.618){0.1}
\pscircle[fillcolor=white,fillstyle=solid](16,2){0.1}
\pscircle[fillcolor=white,fillstyle=solid](14.82,-1.618){0.1}

\pscircle[fillcolor=white,fillstyle=solid](13.147,1.9,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](16,3){0.1}
\pscircle[fillcolor=white,fillstyle=solid](18.853,.927){0.1}
\pscircle[fillcolor=white,fillstyle=solid](18.853,-2.427){0.1}
\pscircle[fillcolor=white,fillstyle=solid](13.147,-2.427){0.1}
\pscircle[fillcolor=white,fillstyle=solid](13.147,-1.8){0.1}
%新加
\psline[linestyle=dashed](13.147,.9)(12.3,.6)
\psline[linestyle=dashed](13.147,-1.9)(12.3,-1.9)
\psline[linestyle=dashed](10.853,-1)(11.7,-1.7)
\psline[linestyle=dashed](10.853,1.9)(11.7,1.3)

\pscircle[fillcolor=white,fillstyle=solid](5.147,-2.427){0.1}
\pscircle[fillcolor=white,fillstyle=solid](5.147,-1){0.1}
\pscircle[fillcolor=white,fillstyle=solid](5.147,1.9,){0.1}
\pscircle[fillcolor=white,fillstyle=solid](13.147,3){0.1}
\pscircle[fillcolor=white,fillstyle=solid](10.853,1.9){0.1}
\pscircle[fillcolor=white,fillstyle=solid](10.853,-1.){0.1}
\pscircle[fillcolor=white,fillstyle=solid](13.147,-1){0.1}
\pscircle[fillcolor=white,fillstyle=solid](13.147,.9){0.1}

\end{pspicture}
\caption{The  snark $S_{12k-2}$ polyhedrally embeds in $\mathbb{N}_k$}\label{Fig:Snar}
\end{figure}



\begin{figure}[h]\center
\begin{pspicture}(-1,-2)(7,2)
%\psset{xunit=22pt,yunit=22pt}
%%%第一个图
\pscircle(0,0){1}
\psline[linestyle=dashed](0,1)(0,1.6)
\psline[linestyle=dashed](.951,.309)(1.521,.4944)
\psline[linestyle=dashed](-.951,.309)(-1.521,.4944)
\psline[linestyle=dashed](.588,-.809)(.9392,-1.2944)
\psline[linestyle=dashed](-.588,-.809)(-.9392,-1.2944)
\pscircle[fillcolor=white,fillstyle=solid](.951,.309){.1}
\pscircle[fillcolor=white,fillstyle=solid](-.951,.309){.1}
\pscircle[fillcolor=white,fillstyle=solid](.588,-.809){.1}
\pscircle[fillcolor=white,fillstyle=solid](-.588,-.809){.1}
\pscircle[fillcolor=white,fillstyle=solid](0,1){.1}




%%%第二个图
\pscircle(5,0){1}\pscircle(5,0){.5}
\psline[linestyle=dashed](5,1)(5,1.6)
\psline[linestyle=dashed](5.951,.309)(6.521,.4944)
\psline[linestyle=dashed](4.049,.309)(3.479,.4944)
\psline[linestyle=dashed](5.588,-.809)(5.9392,-1.2944)
\psline[linestyle=dashed](4.412,-.809)(4.0608,-1.2944)
\pscircle[fillcolor=white,fillstyle=solid](5.951,.309){.1}
\pscircle[fillcolor=white,fillstyle=solid](4.049,.309){.1}
\pscircle[fillcolor=white,fillstyle=solid](5.588,-.809){.1}
\pscircle[fillcolor=white,fillstyle=solid](4.412,-.809){.1}
\pscircle[fillcolor=white,fillstyle=solid](5,1){.1}
%\psline(7,0)(6,2)\psline(8,0)(6,1)

\psline(5,-1)(5,-.5)
\psline(5.476,-.155)(5.951,-.31)
\psline(4.524,-.155)(4.049,-.31)
\psline(4.4123,0.809)(4.7062,0.4045)
\psline(5.5877,0.809)(5.2938,0.4045)

\pscircle[fillcolor=white,fillstyle=solid](5.476,-.155){.1}
\pscircle[fillcolor=white,fillstyle=solid](5.951,-.31){.1}
\pscircle[fillcolor=white,fillstyle=solid](4.524,-.155){.1}
\pscircle[fillcolor=white,fillstyle=solid](4.049,-.31){.1}

\pscircle[fillcolor=white,fillstyle=solid](5.5877,0.809){.1}
\pscircle[fillcolor=white,fillstyle=solid](4.4123,0.809){.1}
\pscircle[fillcolor=white,fillstyle=solid](5.2938,0.4045){.1}
\pscircle[fillcolor=white,fillstyle=solid](4.7062,0.4045){.1}
\pscircle[fillcolor=white,fillstyle=solid](5,-1){.1}
\pscircle[fillcolor=white,fillstyle=solid](5,-.5){.1}

%标字母
\put(-.2,-1.9){$C_{1,5}$}\put(4.8,-1.9){{$C_{2,5}$}}
\end{pspicture}
\caption{The graph $C_{i,5}$ $(i=1,2)$}\label{Fig:twog}
\end{figure}

\begin{theorem} For every integer $k$ ($k\geq 2$), there exists an infinite family of  snarks with
nonorientable genus $k$ which polyhedrally embed in $\mathbb{N}_k$.
\end{theorem}

\begin{proof}

The proof comprises the following two parts:

$(a)$. For every integer $k$ ($k\geq 2$), we construct an infinite family of  snarks with polyhedral
embeddings in $\mathbb{N}_k$;

$(b)$. For every integer $k$ ($k\geq 2$), we prove that the  snarks which are constructed in part $(a)$ have nonorientable genus $k$.

  The Petersen graph $P$  has a polyhedral embedding in $\mathbb{N}_1$  as shown in part $(b)$ of Figure \ref{Fig:Pete}.  By applying 4-strong edge superposition $(k-1)$ times so that
the edge $e$ is recurrently replaced by the copy of $P$, we get the graph $G_{8k+2}$ of order $8k+2$, shown in Figure \ref{Fig:poly}.
 Replacing all vertices of degree 5 in $G_{8k+2}$ by the paths of order 3, we obtain the graph $S_{12k-2}$
 of order $12k-2$ (see Figure \ref{Fig:Snar}).
By Lemma \ref{Koch}, $S_{12k-2}$ is a 4-snark. Then $S_{12k-2}$ has no 3-edge-coloring.
Since $S_{12k-2}$ is a cubic graph, it has a 4-edge-coloring by Vizing theorem. Because the Petersen graph
is cyclically 4-edge-connected and has girth 5, $S_{12k-2}$ is cyclically
4-edge-connected and has girth 5. So $S_{12k-2}$ is a snark. It has a polyhedral embedding
in $\mathbb{N}_k$, indicated in Figure \ref{Fig:Snar}.


 In $G_{8k+2}$, replace all vertices of degree 5 by paths of order 3 or by graphs $C_{i,5}$ ($i\geq 1$),
drawn in Figure \ref{Fig:twog}. Dashed lines indicate the edges incident with a vertex of degree 5 in $G_{8k+2}$.
The resulting graphs are vertex superpositions of $G_{8k+2}$ and are snarks by Lemma \ref{Koch}. Thus we construct an
infinite family of snarks with polyhedral embeddings in $\mathbb{N}_k$.

  Now, we prove part $(b)$. Let $k=2$ in Lemma 2, we get
$$\overline{\gamma}(G_{1}{\bigcup}_{2}G_{2})\geq \overline{\gamma}({G_{1}})+ \overline{\gamma}({G_{2}}).
\ \ \ \ \ \ (1)$$
Since the Petersen graph $P$ has orientable genus
1 and nonorientable genus 1, $\overline{\gamma}(P)=1$ from the Euler genus definition. Recurrently computing $\overline{\gamma}(G_{8i+2})$ from $i=2$ to
 $i=k$ (see Figure \ref{Fig:poly}), we can deduce $\overline{\gamma}(G_{8k+2})\geq k$ according to the inequality (1). For every graph $G$,
  $\widetilde{\gamma}(G)=\overline{\gamma}(G)$ or  $\widetilde{\gamma}(G)=\overline{\gamma}(G)+1$. Thus we get
 $\widetilde{\gamma}(G_{8k+2})\geq k$. Since $G_{8k+2}$ has an embedding in $\mathbb{N}_k$ (see Figure \ref{Fig:poly}), $\widetilde{\gamma}(G_{8k+2})=k$ is deduced.


 When replacing all vertices of degree 5 in $G_{8k+2}$ by paths of order 3 or by graphs $C_{i,5}$ ($i\geq 1$),
  the resulting graphs
 are snarks according to the previous argument. It is clear that the obtained
  snarks have nonorientable genus $k$ because $\widetilde{\gamma}(G_{8k+2})=k$ and paths of order 3 or graphs $C_{i,5}$ ($i\geq 1$) are all planar graphs.

\end{proof}


\begin{corollary} For every integer $k$ ($k >0$), there exists a snark with
nonorientable genus $k$ which polyhedrally embeds in $\mathbb{N}_k$.
\end{corollary}

\begin{proof}
This is directly deduced from Theorem 4 and the fact that the Petersen graph has a polyhedral embedding in the projective plane.
\end{proof}




%===========================================================================


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
 The authors are grateful to the referees for their useful suggestions. Thanks are given to
   Professor Tommy Jensen for his patience and detail comments on a former version of the paper.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}
\bibitem{AH}
K. Appel and W. Haken, Every planar map is four colorable, {\sl Contemp. Math.} {\bf98}
Amer. Math. Soc., Providence RI, 1989.

\bibitem{AR}
D. Archdeacon, The nonorientable genus is additive, {\sl J. Graph Theory} {\bf10} (3) (1986) 363--383.


\bibitem{BK07}
S. Belcastro and J. Kaminski, Families of dot-product snarks on orientable surfaces of
low genus, {\sl Graphs Combin.} {\bf23} (2007) 229--240.



\bibitem{RD05}
R. Diestel, {\sl Graph Theory}, 3rd edn, Springer, Berlin, 2005.

\bibitem{GR}
B. Gr\"unbaum, Conjecture 6, In Recent Progress in Combinatorics
(W. T. Tutte, ed.), Academic Press, New York, 1969, p. 343.



\bibitem{GT87} J. L. Gross and T. W. Tucker, {\sl Topological Graph Theory}, Dover, 2001 (original
edn. Wiley, 1987).

\bibitem{IS75}
R. Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait
colorable, {\sl Amer. Math. Monthly} {\bf82} (1975) 221--239.

\bibitem{KO1}
M. Kochol, Superposition and constructions of graphs without nowhere-zero k-flows,
{\sl Eur. J. Combin.} {\bf23} (2002) 281--306.

\bibitem{KO2}
M. Kochol, Polyhedral embeddings of snarks in orientable surfaces, {\sl Proc.
Amer. Math. Soc.} {\bf137} (5) (2009) 1613--1619.

\bibitem{LLY}
W. Z.  Liu, Y. P. Liu and Y. Xu, A census of boundary cubic rooted planar maps, {\sl Discrete Appl. Math.}
{\bf155} (2007) 1678-1688.

\bibitem{LL}
W. Z. Liu and Y. P. Liu, The number of rooted essential maps on surfaces, {\sl Acta Math. Sin.}
 {\bf 8}(24)(2008) 1303-1312.


\bibitem{MI}
G. Miller, An additivity theorem for the genus of a graph,  {\sl J. Combin. Theory Ser.} B {\bf43} (1) (1987) 25--47.


\bibitem{MT}
B. Mohar and C. Thomassen, {\sl Graphs on Surfaces}, Johns Hopkins University Press, Baltimore,
London, 2001.

\bibitem{MV1}
B. Mohar and A. Vodopivec, On polyhedral embeddings of cubic graphs, {\sl Combin. Probab. Comput.} {\bf 15}
(2006) 877--893.

\bibitem{MV2}
B. Mohar and A. Vodopivec, The genus of Petersen powers, {\sl J. Graph Theory} {\bf67} (2011) 1--8.

\bibitem{TA}
P. G. Tait, Remarks on the colouring of maps, {\sl Proc. Soc. Edinburgh} {\bf10} (1880) 729.

\bibitem{TW85}
F. C. Tinsley and J. J. Watkins, {\sl A study of snark embeddings, Graphs and Applications}
(Boulder, CO, 1982), Wiley-Interscience Publication, New York, 1985, 317-332.

\end{thebibliography}



\end{document}
