Generalized Petersen graphs are $(1,3)$ -choosable

Yunfang Tang Department of Mathematics, China Jiliang University, Hangzhou 310018, P.R. China. Grant number: NSF11701543. Email: [email protected]. Yuting Yao
Department of Mathematics, China Jiliang University, Hangzhou 310018, P.R. China. Email: [email protected].

Abstract

A total weighting of a graph $G$ is a mapping $\phi$ that assigns a weight to each vertex and each edge of $G$ . The vertex-sum of $v\in V(G)$ with respect to $\phi$ is $S_{\phi}(v)=\sum_{e\in E(v)}\phi(e)+\phi(v)$ . A total weighting is proper if adjacent vertices have distinct vertex-sums. A graph $G=(V,E)$ is called $(k,k^{\prime})$ -choosable if the following is true: If each vertex $x$ is assigned a set $L(x)$ of $k$ real numbers, and each edge $e$ is assigned a set $L(e)$ of $k^{\prime}$ real numbers, then there is a proper total weighting $\phi$ with $\phi(y)\in L(y)$ for any $y\in V\cup E$ . In this paper, we prove that the generalized Petersen graphs are $(1,3)$ -choosable.

Keywords: Total weight choosability, generalized Petersen graph, $1$ - $2$ - $3$ Conjecture, Combinatorial Nullstellensatz

1 Introduction

A total weighting of a graph $G$ is a mapping $\phi:V(G)\cup E(G)\rightarrow\mathbb{R}$ . The vertex-sum of $v$ with respect to $\phi$ is $S_{\phi}(v)=\sum_{e\in E(v)}\phi(e)+\phi(v)$ , where $E(v)$ is the set of edges incident to $v$ . A total weighting $\phi$ with $\phi(v)=0$ for all vertices $v$ is also called an edge weighting. A total weighting $\phi$ is proper if for any edge $uv$ of $G$ , $S_{\phi}(u)\neq S_{\phi}(v)$ .

Proper edge weighting of graphs was first studied by Karoński, Łuczak and Thomason [4]. They conjectured that every graph with no isolated edge has a proper edge-weighting using weights 1,2, and 3. This conjecture is called the 1-2-3 Conjecture, and attracted considerable attention, and it finally proved by Ralph Keusch in [5].

The list version of edge weighting of graphs was introduced by Bartnicki, Grytczuk and Niwczyk in [2]. The list version of total weighting of graphs was introduced independently by Przybyło and Woźniak [8] and by Wong and Zhu in [9]. Suppose $\psi:V(G)\cup E(G)\longrightarrow\{1,2,\ldots\}$ is a mapping which assigns to each vertex and each edge of $G$ a positive integer. A $\psi$ -list assignment of $G$ is a mapping $L$ which assigns to $z\in V(G)\cup E(G)$ a set $L(z)$ of $\psi(z)$ real numbers. Given a total list assignment $L$ , a proper $L$ -total weighting is a proper total weighting $\phi$ with $\phi(z)\in L(z)$ for all $z\in V(G)\cup E(G)$ . We say $G$ is total weight $\psi$ -choosable if for any $\psi$ -list assignment $L$ , there is a proper $L$ -total weighting of $G$ . We say $G$ is $(k,k^{\prime})$ -choosable if $G$ is $\psi$ -total weight choosable, where $\psi(v)=k$ for $v\in V(G)$ and $\psi(e)=k^{\prime}$ for $e\in E(G)$ .

It was conjectured in [9] that every graph with no isolated edges is $(1,3)$ -choosable and every graph is $(2,2)$ -choosable, which are the list version of 1-2-3 Conjecture and list version of 1-2 Conjecture, respectively. Wong and Zhu [11] proved that every graph is $(2,3)$ -choosable. Cao [3] proved that every graph with no isolated edges is $(1,17)$ -choosable, and Zhu [12] proved that every graph with no isolated edges is $(1,5)$ -choosable. But the $(1,3)$ -choosable Conjecture and the $(2,2)$ -choosable Conjecture remain open. Indeed, it is unknown whether there is a constant $k$ such that every graph is $(k,2)$ -choosable.

Some special graphs are shown to be $(1,3)$ -choosable, such as complete graphs, complete bipartite graphs, trees (these graphs are shown in [2]), connected $2$ -degenerate non-bipartite graphs other than $K_{2}$ [10], graphs with maximum average degree less than $\frac{11}{4}$ [6], and Halin graphs [7].

The generalized Petersen graph $P(n,t)$ is the graph with vertex set $V(G)=\{u_{i},v_{i}:1\leq i\leq n\}$ and edge set $E(G)=\{u_{i}u_{i+1},u_{i}v_{i},v_{i}v_{i+t}\}$ , where the indices are modulo $n$ .

This paper proves that every generalized Petersen graph is $(1,3)$ -choosable.

2 Preliminaries

Assume $G$ is a simple graph, where $V(G)=\{v_{1},v_{2},\ldots,v_{n}\}$ and $E(G)=\{e_{1},e_{2},\ldots,e_{m}\}$ . Let $T(G)=V(G)\cup E(G)$ . We assign a variable $x_{v}$ to each vertex, and $x_{e}$ to each edge. For each vertex $v$ of $G$ , let $S_{u}=\sum_{e\in E(u)}x_{e}+x_{u}$ . Fix an arbitrary orientation $D$ of $G$ . Let

\displaystyle P(G)=P(x_{v_{1}},x_{v_{2}},\ldots,x_{v_{n}},x_{e_{1}},x_{e_{2}},\ldots,x_{e_{m}})=\prod_{u\in V(G)}P(G,u),

where

\displaystyle P(G,u)=\prod_{v\in N^{+}_{D}(u)}(S_{u}-S_{v})

It follows from the definition that a mapping $\phi:T(G)\rightarrow\emph{R}$ is a proper total weighting of $G$ if and only if $P(\phi)\neq 0$ , where $P(\phi)$ is the evaluation of $P$ at $x_{z}=\phi(z)$ for $z\in T(G)$ .

Assume $X$ is a subset of $V(G)$ and $H=G[X]$ is the subgraph of $G$ induced by $X$ . Denote by $T(G)\setminus T(H)=\left(V(G)\setminus V(H)\right)\cup\left(E(G)\setminus E(H)\right)$ .

Definition 2.1.

An induced subgraph $H$ of $G$ is called a $(k,k^{\prime})$ -choosable induced subgraph in $G$ if for any $(k,k^{\prime})$ -total list assignment $L$ of $G$ and any $L$ -total weighting $\psi:T(G)\setminus T(H)\rightarrow\emph{R}$ , there is an $L$ -total weighting $\phi$ of $G$ such that

(i)

$\phi\mid_{T(G)\setminus T(H)}=\psi$ ;
(ii)

$\sum_{z\in E_{G}(u)\cup\{u\}}\phi(z)\neq\sum_{z\in E_{G}(v)\cup\{v\}}\phi(z)$ for every edge $uv\in E(G)$ with $u\in X$ .

Clearly, if $G$ has a $(k,k^{\prime})$ -choosable induced subgraph $H$ such that $T(G)\setminus T(H)$ has an $L$ -total weighting $\psi$ satisfying $\sum_{z\in E_{G}(u)\cup{\{u\}}}\psi(z)\neq\sum_{z\in E_{G}(v)\cup{\{v\}}}\psi(z)$ for any two adjacent vertices $u,v\in V(G)\setminus V(H)$ , then $G$ is $(k,k^{\prime})$ -choosable. Especially, we have straightforward result in the following:

Lemma 2.2.

Suppose that $G$ has a $(k,k^{\prime})$ -choosable induced subgraph $H$ . Let $G^{\prime}=G[E(G)\setminus E(H)]$ . If $G^{\prime}$ is $(k,k^{\prime})$ -choosable, then $G$ is $(k,k^{\prime})$ -choosable.

Proof. If $G^{\prime}$ is $(k,k^{\prime})$ -choosable, then $G^{\prime}$ has an $L$ -total weighting $\psi$ satisfying

\sum_{z\in E_{G^{\prime}}(u)\cup{\{u\}}}\psi(z)\neq\sum_{z\in E_{G^{\prime}}(v)\cup{\{v\}}}\psi(z)

for any two adjacent vertices $u,v\in V(G)\setminus V(H)\subseteq V(G^{\prime})$ . Note that $E_{G}(u)=E_{G^{\prime}}(u)$ for each vertex $u\in V(G)\setminus V(H)$ . Then $T(G)\setminus T(H)$ also has an $L$ -total weighting $\psi$ satisfying $\sum_{z\in E_{G}(u)\cup{\{u\}}}\psi(z)\neq\sum_{z\in E_{G}(v)\cup{\{v\}}}\psi(z)$ for any two adjacent vertices $u,v\in V(G)\setminus V(H)$ . Thus the result follows. $\square$

Let $L$ be a $(k,k^{\prime})$ -total list assignment of $G$ and $\psi$ be an $L$ -total weighting on $T(G)\setminus T(H)$ . Assign a variable $x_{z}$ to each vertex or edge $z\in T(G)$ satisfying $x_{z}=\psi(z)$ is a constant for $z\in T(G)\setminus T(H)$ . Fix an orientation $D$ on $E(G)$ such that every edge of $\cup_{u\in V(H)}E_{G}(u)\setminus E(H)$ is oriented away from $H$ . Then we define a polynomial $Q_{G}(H)$ by

\displaystyle Q_{G}(H)=Q(\{x_{z}:z\in T(H)\})=\prod_{u\in V(H)}Q_{G}(H,u)=\prod_{u\in V(H)}\prod_{v\in N_{D}^{+}(u)}\left(\sum_{z\in E_{G}(u)\cup\{u\}}x_{z}-\sum_{z\in E_{G}(v)\cup\{v\}}x_{z}\right)

Note that $H$ is a $(k,k^{\prime})$ -choosable induced subgraph in $G$ if and only if $L$ and $\psi$ are defined as above, there is an $\phi(z)\in L(z)$ for each $z\in T(H)$ such that $Q(\{\phi(z):z\in T(H)\})\neq 0$ .

We will apply the following Combinatorial Nullstellsatz to establish a sufficient condition for getting a $(k,k^{\prime})$ -choosable induced subgraph.

Lemma 2.3.

(Combinatorial Nullstellensatz [1]) Let $\mathbb{F}$ be an arbitrary field, and let $P=P(x_{1},x_{2},\ldots,x_{n})$ be a polynomial in $\mathbb{F}[x_{1},x_{2},\ldots,x_{n}]$ . Suppose the degree $deg(P)$ of $P$ equals $\sum_{i=1}^{n}k_{i}$ , where each $k_{i}$ is a non-negative integer, and suppose the coefficient of $x_{1}^{k_{1}}\cdots$ $x_{n}^{k_{n}}$ in $P$ is non-zero. Then if $S_{1},\ldots,S_{n}$ are subsets of $\mathbb{F}$ with $\mid S_{i}\mid>k_{i}$ , there are $s_{1}\in S_{1},\ldots,s_{n}\in S_{n}$ so that $P(s_{1},s_{2},\ldots,s_{n})\neq 0$ .

The goal of this paper is to prove that $H$ is a $(1,3)$ -choosable induced subgraph of $G$ and moreover, $x_{z}=\psi(z)$ is a constant $z\in T(G)\setminus T(H)$ . Thus we restrict to monomials of the form $\prod_{e\in E(H)}x_{e}^{i_{e}}$ by omitting the variables $x_{v}$ for $v\in V(H)$ and vanish all monomials $\prod_{z\in T(H)}x_{z}^{i_{z}}$ with $\sum_{z\in T(H)}i_{z}<\deg(Q_{G}(H))$ . For this purpose, we will consider the following polynomial:

	$\displaystyle P_{G}(H)$	$\displaystyle=$	$\displaystyle P(\{x_{e}:e\in E(H)\})=\prod_{u\in V(H)}P_{G}(H,u)$
		$\displaystyle=$	$\displaystyle\prod_{u\in V(H)}\left(\left(\sum_{e\in E_{H}(u)}x_{e}\right)^{\|E_{G}(u)\setminus E_{H}(u)\|}\prod_{v\in N_{D_{H}}^{+}(u)}\left(\sum_{e\in E_{G}(u)}x_{e}-\sum_{e\in E_{G}(v)}x_{e}\right)\right),$

where $D_{H}$ is the restriction of $D$ on $E(H)$ .

By Lemma 2.3, the following result is straightforward observation.

Corollary 2.4.

Let $H$ be an induced subgraph of a graph $G$ . If $P_{G}(H)$ has a monomial $\prod_{e\in E(H)}x_{e}^{i_{e}}$ with non-zero coefficient, then $H$ is a $(1,3)$ -choosable induced subgraph in $G$ , where $|i_{e}|\leq 2$ for each edge $e\in E(H)$ .

Definition 2.5.

Let $X=\{x_{1},x_{2},\ldots,x_{n}\}$ and $Y=\{x_{i_{1}},\ldots,x_{i_{m}}\}\subseteq X$ . We can think of every polynomial in $\mathbb{F}[X]$ as a polynomial in $\mathbb{T}[Y]$ with $\mathbb{T}=\mathbb{F}[X\backslash Y]$ . For $J=x_{i_{1}}^{j^{1}}\cdots x_{i_{m}}^{j_{m}}$ , we define a mapping $\eta_{J}:\mathbb{F}[X]\rightarrow\mathbb{T}$ by $\eta_{J}[P]$ = the coefficient of J in P $\in\mathbb{T}[Y]$ , for any $P\in\mathbb{F}[X]$ .

Lemma 2.6.

Let $P(x_{1},x_{2},\ldots,x_{n})$ be a polynomial of degree $m$ with $n$ variables, where $m,n\geq 1$ . Let

P(x_{1},x_{2},\ldots,x_{n})=\prod_{k=1}^{s}P_{k},\qquad J=\prod_{k=1}^{s}J_{k},

where $s$ is a positive integer and $1\leq s\leq m$ . For $k\geq 2$ , If $P_{k}$ does not contain any variable in $J_{1},J_{2},\ldots,J_{k-1}$ , $deg(\prod_{k=1}^{t}J_{k})=deg(\prod_{k=1}^{t}P_{k})$ , and $deg(J_{i})=deg(P_{i})$ for $t+1\leq i\leq s$ , where $t$ is a positive integer and $1\leq t\leq s$ , then

\eta_{J}[P]=\eta_{\prod_{k=1}^{t}J_{k}}[\prod_{k=1}^{t}P_{k}]\cdot\prod_{k=t+1}^{s}\eta_{J_{k}}[P_{k}].

Proof.

$\displaystyle\eta_{J}[P]$	$\displaystyle=$	$\displaystyle\eta_{J_{t+1}\cdots J_{s}}[\eta_{\prod_{k=1}^{t}J_{k}}[\prod_{k=1}^{t}P_{k}]\cdot\prod_{k=t+1}^{s}P_{k}]$
	$\displaystyle=$	$\displaystyle\eta_{\prod_{k=1}^{t}J_{k}}[\prod_{k=1}^{t}P_{k}]\cdot\eta_{J_{t+1}\cdots J_{s}}[\prod_{k=t+1}^{n}P_{k}]$
	$\displaystyle=$	$\displaystyle\eta_{\prod_{k=1}^{t}J_{k}}[\prod_{k=1}^{t}P_{k}]\cdot\prod_{k=t+1}^{s}\eta_{J_{k}}[P_{k}].$

$\square$

With the help of MATHEMATICA, the following results we will use in Lemma 3.1 are directly obtained.

Observation 2.7.

For any positive integer $s$ and $t$ , and $s<t$ , denote by $J^{*}_{s,t}=\prod_{i=s}^{t}y_{i}^{2}$ , $F^{*}_{s,t}=\prod_{i=s}^{t}(y_{i}+y_{i+1})(y_{i}-y_{i+2})$ , then $\eta_{J^{*}_{s,t}}[F^{*}_{s,t}]=1$ .

Theorem 2.8.

[2] If $G$ is a forest without isolated edges, then $G$ is $(1,3)$ -choosable.

Theorem 2.9.

[6] Graphs with maximum average degree less than $\frac{11}{4}$ are $(1,3)$ -choosable.

Theorem 2.10.

[10] Every connected $2$ -degenerate non-bipartite graph other than $K_{2}$ is $(1,3)$ -choosable.

3 Proof of Theorem

Lemma 3.1.

Let $G$ be a cubic graph, and $H$ be an induced subgraph of $G$ . If $H$ is one of the following configurations:

(i)

$H$ is a graph obtained by two adjacent cycles with a common edge, where one cycle is an $n$ -cycle $u_{1}u_{2}\cdots u_{n}u_{1}$ and the other one is a $4$ -cycle $u_{1}u_{2}v_{2}v_{1}u_{1}$ ;
(ii)

$H$ is a graph obtained by two adjacent $5$ -cycles with a common edge, which is also called diamond $D_{8}$ ;
(iii)

$H$ is a graph obtained by by two adjacent cycles with two common edges, where one cycle is an $n$ -cycle $u_{1}u_{2}\cdots u_{n}u_{1}$ and the other one is a $8$ -cycle $u_{1}u_{2}v_{2}v_{t+2}u_{t+2}u_{t+1}v_{t+1}v_{1}u_{1}$ .

then $H$ is a $(1,3)$ -choosable induced subgraph in $G$ .

Proof. In the proof of this Lemma, the coefficients of all the polynomials we use are obtained by MATHEMATICA.

(i) Assign variables $y_{i}$ to $u_{i}u_{i+1}$ for $i=1,2,\ldots,n$ ; $z_{i}$ to $u_{i}v_{i}$ for $i=1,2$ , and $w$ to $v_{1}v_{2}$ , respectively. Fix an orientation of $H$ such that every edge $u_{i}u_{i+1}$ is oriented toward $u_{i+1}$ for $i\in[1,n-1]$ , every edge $u_{i}v_{i}$ is oriented toward $v_{i}$ for $i\in\{1,2\}$ , edge $u_{1}u_{n}$ is oriented toward $u_{n}$ and edge $v_{1}v_{2}$ is oriented toward $v_{2}$ (see Figure $1(i)$ ). Let $V(H_{0})=\{u_{i},v_{j}:i,j\in\{1,2\}\}$ . Then

$\displaystyle P_{G}(H)$	$\displaystyle=$	$\displaystyle\prod_{v\in V(H_{0})}P_{G}(H,v)\cdot\prod_{i=3}^{i=n}P_{G}(H,u_{i})$
	$\displaystyle=$	$\displaystyle[(y_{n}+y_{1}-w)(y_{n}+z_{1}-y_{2}-z_{2})(y_{1}+y_{2}-w)(y_{1}+z_{2}-y_{3})$
		$\displaystyle(y_{1}+z_{1}-y_{n-1})(z_{1}+w)(z_{1}-z_{2})(z_{2}+w)]\cdot F^{*}_{2,n-2}\cdot(y_{n-1}+y_{n}).$

Choose

J=z_{1}^{2}z_{2}w^{2}\prod_{i=1}^{n-1}y_{i}^{2}=(z_{1}wy_{1})^{2}z_{2}\cdot J^{*}_{2,n-2}\cdot y_{n-1}^{2}.

Then by Lemma 2.6 and Observation 2.7, we obtain that

$\displaystyle\eta_{J}[P_{G}(H)]$	$\displaystyle=$	$\displaystyle\eta_{y_{n-1}^{2}}\{\eta_{(z_{1}wy_{1})^{2}z_{2}}[(y_{n}+y_{1}-w)(y_{n}+z_{1}-y_{2}-z_{2})(y_{1}+y_{2}-w)(y_{1}+z_{2}-y_{3})$
		$\displaystyle(y_{1}+z_{1}-y_{n-1})(z_{1}+w)(z_{1}-z_{2})(z_{2}+w)]\cdot\eta_{J^{}_{2,n-2}}[F^{}_{2,n-2}]\cdot(y_{n-1}+y_{n})\}$
	$\displaystyle=$	$\displaystyle\eta_{y_{n-1}^{2}}[-3y_{n-1}\cdot(y_{n-1}+y_{n})]$
	$\displaystyle=$	$\displaystyle-3\neq 0.$

Thus the result $(i)$ follows by Corollary 2.4.

(ii) We may assume that $H=C_{8}+u_{1}u_{5}$ , where $C_{8}=u_{1}u_{2}\cdots u_{8}u_{1}$ . For convenience, set $u_{9}=u_{0}$ . Assign variables $y_{i}$ to $u_{i}u_{i+1}$ for $i\in[1,8]$ , and $z_{1}$ to $u_{1}u_{5}$ . Fix an orientation of $H$ such that every edge $u_{i}u_{i+1}$ is oriented toward $u_{i+1}$ for $i\in[1,8]$ , and edge $u_{1}u_{5}$ is oriented toward $u_{5}$ (see Figure $1(ii)$ ). Then

	$\displaystyle P_{G}(H)$	$\displaystyle=$	$\displaystyle\prod_{v\in V(C_{8})}P_{G}(H,v)=(y_{8}+y_{1}-y_{4}-y_{5})(y_{8}+z_{1}-y_{2})(y_{3}-y_{5}-z_{1})(y_{4}+z_{1}-y_{6})$
			$\displaystyle(y_{7}-y_{1}-z_{1})\cdot\prod_{i=1,2,3,5,6,7}(y_{i}+y_{i+1})\cdot\prod_{i=1,2,5,6}(y_{i}-y_{i+2}).$

Let $J=z_{1}^{2}\prod_{i=1}^{7}y_{i}^{2}/y_{4}$ , we obtain that $\eta_{J}[P_{G}(H)]=-8\neq 0$ . Thus the result follows by Corollary 2.4.

(iii) Assign variables $y_{i}$ , $z_{j}$ and $w_{k}$ to $u_{i}u_{i+1}$ , $u_{j}v_{j}$ , and $v_{k}v_{k+t}$ , respectively, for $i=\{1,2,\ldots,n\};j=\{1,2,t+1,t+2\};k=\{1,2\}$ , where the subscripts of $u_{i}$ are taken modulo $n$ . Fix an orientation of $H$ such that every edge $u_{i}u_{i+1}$ is oriented toward $u_{i+1}$ for $i\in[1,t-1]\cup[t+1,n-1]$ , edge $u_{j}v_{j}$ is oriented toward $v_{j}$ for $j\in\{1,2,t+1,t+2\}$ , edge $u_{1}u_{n}$ is oriented toward $u_{n}$ , edge $u_{t+1}u_{t}$ is oriented toward $u_{t}$ , and edge $v_{k}v_{k+t}$ is oriented toward $v_{k+t}$ for $k\in\{1,2\}$ (see Figure $1(iii)$ ). Note that $V(C_{8})=\{u_{1},u_{2},v_{2},v_{t+2},u_{t+2},u_{t+1},v_{t+1},v_{1}\}$ . Then

\displaystyle P_{G}(H)=\prod_{i=1}^{t-1}\prod_{i=t+2}^{n-1}P_{i},

where

$\displaystyle P_{1}$	$\displaystyle=$	$\displaystyle\prod_{v\in V(C_{8})}P_{G}(H,v)=(y_{n}+z_{1}-y_{2}-z_{2})(y_{n}+y_{1}-w_{1})(y_{1}+z_{1}-y_{n-1})(y_{1}+z_{2}-y_{3})$
		$\displaystyle(y_{1}+y_{2}-w_{2})(y_{t}+y_{t+1}-w_{1})(y_{t}+z_{t+1}-y_{t+2}-z_{t+2})(y_{t+1}+y_{t+2}-w_{2})(y_{t+1}+z_{t+1}-y_{t-1})$
		$\displaystyle(y_{t+1}+z_{t+2}-y_{t+3})(z_{1}-z_{t+1})(z_{1}+w_{1})(z_{2}-z_{t+2})(z_{2}+w_{2})(z_{t+1}+w_{1})(z_{t+2}+w_{2}),$
$\displaystyle P_{i}$	$\displaystyle=$	$\displaystyle P_{G}(H,u_{i+1})=\begin{cases}(y_{i}+y_{i+1})(y_{i}-y_{i+2})~{}&\mbox{if $i\in[2,t-2]\bigcup[t+2,n-2]$},\\ (y_{i}+y_{i+1})~{}&\mbox{if $i\in\{t-1,n-1\}$}.\end{cases}$

Choose $J=\prod_{i=1}^{t-1}\prod_{i=t+2}^{n-1}J_{i}$ , where

\displaystyle J_{i}

\displaystyle=

\displaystyle\begin{cases}y_{1}^{2}z_{1}^{2}z_{2}^{2}z_{t+1}^{2}z_{t+2}^{2}w_{1}^{2}w_{2}^{2}~{}&\mbox{if $i=1$},\\ y_{i}^{2}~{}&\mbox{if $i\in[2,t-2]\bigcup[t+2,n-2]$},\\ y_{t-1}^{2}y_{t}~{}&\mbox{if $i=t-1$, and $t\neq 2~{}(mod~{}3)$},\\ y_{t-1}y^{2}_{t}~{}&\mbox{if $i=t-1$, and $t=2~{}(mod~{}6)$},\\ y_{i}y_{i+1}~{}&\mbox{if $i\in\{t-1,n-1\}$, and $t=5~{}(mod~{}6)$},\\ y_{n-1}~{}&\mbox{if $i=n-1$, and $t\neq 5~{}(mod~{}6)$}.\end{cases}

In the following, we will determine $\eta_{J}[P_{G}(H)]$ by some procedures. For convenience, denoted by

\displaystyle Q^{*}=-y_{n}^{2}-y_{n-1}y_{t-1}-y_{n}y_{t-1}-y_{n-1}y_{t}+y_{n}y_{t}-y_{t}^{2}-2y_{n}y_{t+2}+2y_{t}y_{t+2}-y_{t+2}^{2},

$P^{\prime}_{1}=P_{1}$ , and $P^{\prime}_{i}=\eta_{J_{i-1}}[P^{\prime}_{i-1}]\cdot P_{i}$ for $i\in[2,t-1]$ .

With the help of MATHEMATICA, we determine that $\eta_{J_{i}}[P^{\prime}_{i}]$ for $i\in[1,t-1]$ in the following. For $i=3k+1$ ,

			$\displaystyle\eta_{J_{1}}[P^{\prime}_{1}]=\eta_{J_{1}}[P_{1}]$
		$\displaystyle=$	$\displaystyle-y_{2}^{2}+y_{2}(2y_{n}-2y_{t}+y_{t+2}-y_{t+3})-y_{3}(y_{t+2}+y_{t+3})+Q^{*},$
			$\displaystyle\eta_{J_{3k+1}}[P^{\prime}_{3k+1}]=\eta_{J_{3k+1}}[\eta_{J_{3k}}[P^{\prime}_{3k}]\cdot P_{3k+1}]$
		$\displaystyle=$	$\displaystyle-y_{3k+2}^{2}+(-1)^{3k+1}[y_{3k+2}(-2y_{n}+2y_{t}-y_{t+2}+y_{t+3})+y_{3k+3}(y_{t+2}+y_{t+3})]+Q^{*};$

for $i=3k+2$ ,

			$\displaystyle\eta_{J_{2}}[P^{\prime}_{2}]=\eta_{J_{2}}[\eta_{J_{1}}[P^{\prime}_{1}]\cdot P_{2}]$
		$\displaystyle=$	$\displaystyle y_{3}y_{4}+2y_{3}(y_{n}-y_{t}-y_{t+3})+y_{4}[2(y_{t}-y_{n})-y_{t+2}+y_{t+3}]+Q^{*},$
			$\displaystyle\eta_{J_{3k+2}}[P^{\prime}_{3k+2}]=\eta_{J_{3k+2}}[\eta_{J_{3k+1}}[P^{\prime}_{3k+1}]\cdot P_{3k+2}]$
		$\displaystyle=$	$\displaystyle y_{3k+3}y_{3k+4}+(-1)^{3k+2}[2y_{3k+3}(y_{n}-y_{t}-y_{t+3})+y_{3k+4}(2y_{t}-2y_{n}-y_{t+2}+y_{t+3})]+Q^{*};$

and for $i=3k+3$ ,

			$\displaystyle\eta_{J_{3}}[P^{\prime}_{3}]=\eta_{J_{3}}[\eta_{J_{2}}[P^{\prime}_{2}]\cdot P_{3}]$
		$\displaystyle=$	$\displaystyle y_{4}^{2}-y_{4}(y_{t+2}+y_{t+3}+y_{5})-2y_{5}(y_{n}-y_{t}-y_{t+3})+Q^{*},$
			$\displaystyle\eta_{J_{3k+3}}[P^{\prime}_{3k+3}]=\eta_{J_{3k+3}}[\eta_{J_{3k+2}}[P^{\prime}_{3k+2}]\cdot P_{3k+3}]$
		$\displaystyle=$	$\displaystyle y_{3k+4}^{2}-y_{3k+4}y_{3k+5}+(-1)^{3k+3}[y_{3k+4}(y_{t+2}+y_{t+3})+2y_{3k+5}(y_{n}-y_{t}-y_{t+3})]+Q^{*}.$

Set $i=t-2$ . Then by the above computations,

			$\displaystyle\eta_{J_{t-2}}[P^{\prime}_{t-2}]$
		$\displaystyle=$	$\displaystyle\begin{cases}-y_{t-1}^{2}+(-1)^{t}[y_{t-1}(-2y_{n}+2y_{t}-y_{t+2}+y_{t+3})+y_{t}(y_{t+2}+y_{t+3})]+Q^{}&~{}\mbox{if $t=0~{}(mod~{}3)$},\\ y_{t-1}y_{t}+(-1)^{t}[2y_{t-1}(y_{n}-y_{t}-y_{t+3})+y_{t}(2y_{t}-2y_{n}-y_{t+2}+y_{t+3})]+Q^{}&~{}\mbox{if $t=1~{}(mod~{}3)$},\\ y_{t-1}^{2}-y_{t-1}y_{t}+(-1)^{t-2}[y_{t-1}(y_{t+2}+y_{t+3})+2y_{t}(y_{n}-y_{t}-y_{t+3})]+Q^{*}&~{}\mbox{if $t=2~{}(mod~{}3)$}.\end{cases}$

Recall that $P^{\prime}_{t-1}=\eta_{J_{t-2}}[P^{\prime}_{t-2}]\cdot(y_{t-1}+y_{t})$ . Then

\displaystyle\eta_{J_{t-1}}[P^{\prime}_{t-1}]=\begin{cases}-1+2(-1)^{t}&~{}\mbox{if $t=0~{}(mod~{}3)$},\\ 1-2(-1)^{t}&~{}\mbox{if $t=1~{}(mod~{}3)$},\\ -4&~{}\mbox{if $t=2~{}(mod~{}6)$},\\ -2y_{n-1}-2y_{n}+y_{t+2}+y_{t+3}&~{}\mbox{if $t=5~{}(mod~{}6)$}.\end{cases}

Suppose that $t\neq 5~{}(mod~{}6)$ . It’s easily seen that $\deg(\prod_{i=1}^{t-1}J_{i})=\deg(\prod_{i=1}^{t-1}P_{i})$ , $\deg(J_{i})=\deg(P_{i})$ and $P_{i}$ does not contain any variable in $J_{1},J_{2},\ldots,J_{i-1}$ for $i\in[t+2,n-1]$ . Then by Lemma 2.6 and Observation 2.7, we have

$\displaystyle\eta_{J}[P_{G}(H)]$	$\displaystyle=$	$\displaystyle\eta_{\prod_{k=1}^{t-1}\prod_{k=t+2}^{n-1}J_{k}}[\prod_{k=1}^{t-1}\prod_{k=t+2}^{n-1}P_{k}]$
	$\displaystyle=$	$\displaystyle\eta_{\prod_{k=1}^{t-1}J_{k}}[\prod_{k=1}^{t-1}P_{k}]\cdot\prod_{k=t+2}^{n-1}\eta_{J_{k}}[P_{k}]$
	$\displaystyle=$	$\displaystyle\eta_{J_{t-1}}[P^{\prime}_{t-1}]\cdot\eta_{J^{}_{t+2,n-2}}[F^{}_{t+2,n-2}]\cdot\eta_{J_{n-1}}[P_{n-1}]$
	$\displaystyle=$	$\displaystyle\begin{cases}-1+2(-1)^{t}&~{}\mbox{if $t=0~{}(mod~{}3)$},\\ 1-2(-1)^{t}&~{}\mbox{if $t=1~{}(mod~{}3)$},\\ -4&~{}\mbox{if $t=2~{}(mod~{}6)$}.\end{cases}$

In the following, we will consider $t=5~{}(mod~{}6)$ . For convenience, let $Q_{0}^{*}=-2y_{n-1}-2y_{n}$ , $P^{\prime}_{t+1}=\eta_{J_{t-1}}[P^{\prime}_{t-1}]$ , and $P^{\prime}_{i}=\eta_{J_{i-1}}[P^{\prime}_{i-1}]\cdot P_{i}$ , where $i\in[t+2,n-1]$ . With the help of MATHEMATICA, for $s\in[2,n-t+2]$ ,

\displaystyle\eta_{J_{t+s}}[P^{\prime}_{t+s}]=\begin{cases}Q_{0}^{*}+(-1)^{s+1}(y_{t+s+1}+y_{t+s+2})~{}&\mbox{if $s=1~{}(mod~{}3)$},\\ Q_{0}^{*}+(-1)^{s}(2y_{t+s+1}-y_{t+s+2})~{}&\mbox{if $s=2~{}(mod~{}3)$},\\ Q_{0}^{*}+(-1)^{s+1}(y_{t+s+1}-2y_{t+s+2})~{}&\mbox{if $s=0~{}(mod~{}3)$}.\end{cases}

Let $s=n-t-2$ . Then $n-2=t+s=3k+2+s$ , we have

\displaystyle\eta_{J_{n-2}}[P^{\prime}_{n-2}]=\begin{cases}[(-1)^{n}-2](y_{n-1}+y_{n})~{}&\mbox{if $n=2~{}(mod~{}3)$},\\ [(-1)^{n-1}-1]2y_{n-1}-[2+(-1)^{n-1}]y_{n}~{}&\mbox{if $n=0~{}(mod~{}3)$},\\ [(-1)^{n}-2]y_{n-1}-[1+(-1)^{n}]2y_{n}~{}&\mbox{if $n=1~{}(mod~{}3)$}.\end{cases}

Note that $P^{\prime}_{n-1}=\eta_{J_{n-2}}[P^{\prime}_{n-2}]\cdot(y_{n-1}+y_{n})$ , and $J_{n-1}=y_{n-1}y_{n}$ , then

\displaystyle\eta_{J}[P_{G}(H)]=\eta_{J_{n-1}}[P^{\prime}_{n-1}]

\displaystyle=

\displaystyle\begin{cases}(-1)^{n-1}-4~{}&\mbox{if $n\neq 2~{}(mod~{}3)$}\\ 2(-1)^{n}-4~{}&\mbox{if $n=2~{}(mod~{}3)$}\\ \end{cases}

From the above, the result follows. $\square$

By the definition of the generalized Petersen graph $P(n,t)$ , where $n\geq 3$ and $1\leq t\leq\frac{n}{2}$ , the following result is a straightforward observation:

•

$P(n,t)\cong P(n,n-t)$ ;
•

$P(n,t)$ can be decomposed into three subgraphs with disjoint edges:

$\displaystyle P(n,t)=G[V_{1}]\bigcup G[M]\bigcup G[V_{2}],$

where $G[V_{1}]$ is an $n$ -cycle, $G[M]$ is the induced subgraph of a perfect matching $M$ in $P(n,t)$ , $G[V_{2}]$ is composed by $(n,t)$ disjoint $\frac{n}{(n,t)}$ -cycles, and $G[V_{1}]$ and $G[V_{2}]$ are edge-disjoint.

Theorem 3.2.

The generalized Petersen graph $G=P(n,t)$ is $(1,3)$ -choosable.

Proof. Let $G$ be a graph with vertex set

V(G)=\{u_{1},u_{2},\ldots,u_{n};v_{1},v_{2},\ldots,v_{n}\}

and edge set

E(G)=\{u_{i}u_{i+1},u_{i}v_{i},v_{i}v_{i+t}:i\in\{1,2,\ldots,n\}\},

where the subscripts are taken modulo $n$ . Denote $V_{1}=\{u_{1},u_{2},\ldots,u_{n}\}$ as outer vertices set and $V_{2}=\{v_{1},v_{2},\ldots,v_{n}\}$ as inner vertices set. The edges $u_{i}u_{i+1},v_{i}v_{i+t}$ , and $u_{i}v_{i}$ are denoted as outer edges, inner edges and leg edges, respectively, where $i\in\{1,2,\ldots,n\}$ .

We will consider a demonstration of $P(n,t)$ into several types of cases in the following. Note that $n\geq 2t$ . If $n=2t$ and $t\geq 2$ , then ${\rm mad}(G)\leq\frac{5}{2}<\frac{11}{4}$ . By Theorem 2.9, $P(2t,t)$ is $(1,3)$ -choosable.

We may assume $n\geq 2t+1$ . Let $G^{\prime}=G[E(G)\setminus E(H)]$ .

If $t=1$ , then choose $H=G[V(1)\bigcup\{v_{1},v_{2}\}]$ . By lemma 3.1 $(i)$ , $H$ is a $(1,3)$ -choosable induced subgraph in $P(n,1)$ . According to the structure of $P(n,1)$ , it is not difficult to find $G^{\prime}$ is a tree obtained by attaching an edge to each inner vertex of a path $P_{n-1}=v_{2}\cdots v_{n}v_{1}$ . Then $G^{\prime}$ is $(1,3)$ -choosable by Lemma 2.8. Thus by Lemma 2.2, $P(n,1)$ is $(1,3)$ -choosable. Take $P(5,1)$ as an example, see Figure $2$ .

Fig. 2. $G=P(5,1)$

Fig. 3. $G=P(8,2)$

Fig. 4. $G=P(7,3)$

Fig. 5. $G=P(10,4)$

If $t=2$ , then choose $H=G[X]$ , where $X=\{u_{i},v_{i}:i=1,2,3,4\}$ and the edge set $E[X]$ . Expanding the plane of the structure $H$ , it is not difficult to see that $H$ is a graph obtained by two adjacent $5$ -cycles with a common edge $u_{2}u_{3}$ , by Lemma 3.1 $(ii)$ , $H$ is a $(1,3)$ -choosable induced subgraph in $G$ . According to the structure of $P(n,2)$ , we claim that $G^{\prime}$ is $(1,3)$ -choosable. When $5=2t+1\leq n\leq 6$ , $G^{\prime}$ is a tree. When $n\geq 7$ , $G^{\prime}$ contains an odd $5$ -cycle $u_{5}u_{6}u_{7}v_{7}v_{5}u_{5}$ , which is a non-bipartite $2$ -degenerate graph. Thus by Theorems 2.8 and 2.10, the claim is proved. By Lemma 2.2, $G=P(n,2)$ is $(1,3)$ -choosable. Take $P(8,2)$ as an example, see Figure $3$ .

Suppose that $t\geq 3$ .

If $n=2t+1$ , then choose $H=G[X]$ , where $X=\{u_{i},v_{i}:i=1,2,t+1,t+2\}$ . Expanding the plane of the structure $H$ , it is not difficult to see that $H$ is a graph obtained by two adjacent $5$ -cycles with a common edge $v_{1}v_{t+2}$ . By Lemma 3.1 $(ii)$ , $H$ is a $(1,3)$ -choosable induced subgraph in $G$ . Note that $G^{\prime}$ is a non-bipartite $2$ -degenerate graph, since it contains an odd $5$ -cycle $\{v_{3},v_{t+3},u_{t+3},u_{t+4},v_{t+4}v_{3}\}$ . Then by Theorem 2.10, $G^{\prime}$ is $(1,3)$ -choosable. Therefore by Lemma 2.2, $G=P(2t+1,t)$ is $(1,3)$ -choosable. Take $P(7,3)$ as an example, see Figure $4$ .

If $n\geq 2t+2$ , then choose $H=G[X]$ , where $X=V_{1}\bigcup\{v_{i}:i=1,2,t+1,t+2\}$ . Expanding the plane of the structure $H$ , it is not difficult to see that it is isomorphic to the graph as in Lemma 3.1 $(iii)$ . Thus $H$ is a $(1,3)$ -choosable induced subgraph in $G$ . Note that $G[V_{2}]$ is a graph composed by $(n,t)$ disjoint $\frac{n}{(n,t)}$ -cycles $C(1),\cdots,C((n,t))$ . Denote by $C^{*}(i)$ be a unicyclic graph obtained by attaching one edge to each vertex of $\frac{n}{(n,t)}$ -cycle $C(i)$ . Then $G\setminus G[V_{1}]$ is a graph composed by $(n,t)$ disjoint $\frac{n}{(n,t)}$ -cycles $C^{*}(1),\cdots,C^{*}((n,t))$ , in which each $C^{*}(i)$ contains $v_{i}$ and $v_{i+t}$ for $i\in\{1,\dots,(n,t)\}$ . According to the structure of

G^{\prime}=(G[M]-\{u_{i}v_{i}:i\in\{1,2,t+1,t+2\}\})\bigcup(G[V_{2}]-\{v_{1}v_{t+1},v_{2}v_{t+2}\}),

we have three cases to discuss. When $(n,t)=1$ , $G^{\prime}$ is a forest obtained from $C^{*}(1)$ by deleting two edges $v_{1}v_{t+1}$ and $v_{2}v_{t+2}$ in the $n$ -cycle and four leg edges $\{u_{i}v_{i}:i\in\{1,2,t+1,t+2\}\}$ in $M$ . When $(n,t)=2$ , $G^{\prime}$ is a forest obtained from two disjoint unicyclic graphs $C^{*}(i)$ ( $i=1,2$ ) by deleting one $v_{i}v_{t+i}$ in the $\frac{n}{2}$ -cycle and two leg edges $\{u_{i}v_{i}:i\in\{i,t+i\}\}$ in $M$ , respectively. Otherwise, $G^{\prime}=F_{0}\cup G_{0}$ , where $F_{0}$ is a forest consisting of two disjoint unicyclic graphs $C^{*}(i)$ ( $i=1,2$ ) by deleting one edge $v_{i}v_{t+i}$ in the $\frac{n}{(n,t)}$ -cycle and two leg edges $\{u_{i}v_{i}:i\in\{i,t+i\}\}$ in $M$ , respectively, and $G_{0}$ is a graph obtained from $(n,t)-2$ disjoint unicyclic graphs $C^{*}(3),\cdots,C^{*}((n,t))$ . Note that ${\rm mad}(G^{\prime})\leq 2$ . Then $G^{\prime}$ is $(1,3)$ -choosable by Theorem 2.9. Thus by Lemma 2.2, the result follows. Take $P(10,4)$ as an example, see Figure $5$ .