% 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}