Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights \thanks{This work was supported in part by the National Natural Science Foundation of China No. 11101329.}
{School of Mathematics and Statistics}
Let $G$ be a graph and $\mathcal {S}$ be a subset of $Z$. A vertex-coloring $\mathcal {S}$-edge-weighting of $G$ is an assignment of weight $s$ by the elements of $\mathcal {S}$ to each edge of $G$ so that adjacent vertices have different sums of incident edges weights. It was proved that every 3-connected bipartite graph admits a vertex-coloring $\{1,2\}$-edge-weighting (Lu, Yu and Zhang, (2011) \cite{LYZ}). %Let $H$ be a 3-edge-connected bipartite graph with %minimum degree $\delta(H)$. In this paper, we show that the following result: if a 3-edge-connected bipartite graph $G$ with minimum degree $\delta$ contains a vertex $u\in V(G)$ such that $d_G(u)=\delta$ and $G-u$ is connected, then $G$ admits a vertex-coloring $\mathcal {S}$-edge-weighting for $\mathcal {S}\in \{\{0,1\},\{1,2\}\}$. In particular, we show that every 2-connected and 3-edge-connected bipartite graph admits a vertex-coloring $\mathcal {S}$-edge-weighting for $\mathcal {S}\in \{\{0,1\},\{1,2\}\}$. The bound is sharp, since there exists a family of infinite bipartite graphs which are 2-connected and do not admit vertex-coloring $\{1,2\}$-edge-weightings or vertex-coloring $\{0,1\}$-edge-weightings. %Furthermore, %we show that every 2-connected graph with $\delta(G)\geq 5$ admits a %vertex-coloring $\{0,1\}$-edge-weighting. %A graph $G = (V, E)$ is called vertex-coloring $k$-edge-weighting if %the following holds: there is a mapping $w:E\rightarrow %\{1,2,\ldots,k\}$ such that for any two adjacent vertices $u, v$, %$\sum_{x\in N_G(G)}w(xu)\neq \sum_{y\in N(v)}w(yv)$. % %It was proved that every 3-colorable graph admits a vertex-coloring %$3$-edge-weighting (Karo\'nski et al. (2004) \cite{KLT}). Lu, Yu and Zhang (2011, \cite{LYZ}) %proved that every 3-connected bipartite graphs admits % vertex-coloring 2-edge-weighting. The current paper proves that every 2-vertex-connected and 3-edge-connected %bipartite graph admits a vertex-coloring 2-edge-weighting, \\ [2mm] Keywords: edge-weighting; vertex-coloring; $2$-connected; bipartite graph.\\ [2mm] {AMS subject classification (2000)}: 05C15.
1307.1863.tex
%6/29/13

%%%revised 7/7/2013
\documentclass[11pt]{article}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\def\papername{applied graph}
\usepackage{amsfonts, amsmath, amssymb}
\usepackage{amssymb,amsfonts,amsmath,
latexsym, epsfig,cite, psfrag,eepic,colordvi}
\usepackage{amscd,graphics}
\linespread{1.2}
\usepackage{lineno}
%\pagewiselinenumbers


\textwidth 18cm \textheight 22cm \topmargin 0 cm \hoffset -1.5 cm
\voffset 0cm

\setlength{\headsep}{30pt}%distance between yemei and text.

\setlength{\footskip}{.3in} \setlength{\textheight}{8.5in}
\setlength{\textwidth}{6in} \setlength{\parskip}{4pt}

\newcommand{\noi}{\noindent}
\newcommand{\de}{\backslash}
\newcommand{\buu}{\biggerundertilde}
\newcommand{\ti}{\widetilde}
\newcommand{\su}{\subseteq}
\newcommand{\s}{\preceq}
\newcommand{\qed}{\hfill $\Box $}
\newcommand{\pf}{\noindent {\bf Proof.} }

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{coro}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{problem}{Problem}



\begin{document}

\title{Vertex-Coloring Edge-Weighting of Bipartite Graphs  with Two
Edge Weights
\thanks{This work was supported in part by  the National Natural
Science Foundation of China No. 11101329.}}
\author{Hongliang Lu\footnote{E-mail address:
luhongliang215@sina.com}
\\ {\small School of Mathematics and Statistics}
\\ {\small Xi'an Jiaotong University, Xi'an, 710049, PR China}
}

\date{}

\maketitle

\begin{abstract}
Let $G$ be a graph and  $\mathcal {S}$ be a subset of $Z$. A
vertex-coloring $\mathcal {S}$-edge-weighting of $G$ is an
assignment of weight $s$ by the elements of $\mathcal {S}$ to each
edge of $G$ so that adjacent vertices have different sums of
incident edges weights.

It was proved that every 3-connected bipartite graph admits a
vertex-coloring $\{1,2\}$-edge-weighting (Lu, Yu and Zhang, (2011)
\cite{LYZ}). %Let $H$ be a 3-edge-connected bipartite graph with
%minimum degree $\delta(H)$.
In this paper, we show that the following result: if a
3-edge-connected bipartite graph $G$ with minimum degree $\delta$
contains a vertex $u\in V(G)$ such that $d_G(u)=\delta$ and $G-u$ is
connected, then $G$ admits a vertex-coloring $\mathcal
{S}$-edge-weighting for $\mathcal {S}\in \{\{0,1\},\{1,2\}\}$. In
particular, we show that every 2-connected and 3-edge-connected
bipartite graph admits a vertex-coloring $\mathcal
{S}$-edge-weighting for $\mathcal {S}\in \{\{0,1\},\{1,2\}\}$. The
bound   is sharp, since there exists a family of infinite bipartite
graphs which are 2-connected and do not admit  vertex-coloring
$\{1,2\}$-edge-weightings or vertex-coloring
$\{0,1\}$-edge-weightings.
%Furthermore,
%we show that every 2-connected graph with $\delta(G)\geq 5$ admits a
%vertex-coloring $\{0,1\}$-edge-weighting.
%A graph $G = (V, E)$ is called vertex-coloring $k$-edge-weighting if
%the following holds:  there is a mapping $w:E\rightarrow
%\{1,2,\ldots,k\}$ such that   for any two adjacent vertices $u, v$,
%$\sum_{x\in N_G(G)}w(xu)\neq \sum_{y\in N(v)}w(yv)$.
%
%It was proved that every 3-colorable graph admits a vertex-coloring
%$3$-edge-weighting (Karo\'nski et al. (2004) \cite{KLT}). Lu, Yu and Zhang (2011, \cite{LYZ})
%proved that every 3-connected bipartite graphs   admits
% vertex-coloring 2-edge-weighting. The current paper proves that every 2-vertex-connected and 3-edge-connected
%bipartite graph   admits a vertex-coloring 2-edge-weighting,
\\
[2mm] \textbf{Keywords}: edge-weighting; vertex-coloring; $2$-connected; bipartite graph.\\
[2mm] {\bf AMS subject classification (2000)}: 05C15.
\end{abstract}



\section{Introduction}



In this paper, we consider only finite, undirected and simple
connected graphs. For a vertex $v$ of graph $G=(V,E)$, $N_G(v)$
denotes the set of vertices which are adjacent to $v$ and
$d_G(v)=|N_G(v)|$ is called the \emph{degree} of vertex $v$. Let
$\delta(G)$ and $\triangle(G)$ denote the minimum degree and maximum
degree of graph $G$, respectively.
 For $v\in V(G)$ and $r\in Z^+$, let
$N_G^{r}(v)=\{u\in N(v)\ |\ d_G(u)=r\}$.  If $v\in V(G)$ and $e\in
E(G)$, we use $v\sim e$ to denote that $v$ is an end-vertex of $e$.
For two disjoint subsets $S,T$ of $V(G)$, let $E_G(S,T)$ denote the
subset of edges of $E(G)$ with one end in $S$ and other end in $T$
and let $e_G(S,T)=|E_G(S,T)|$.



Let   $\mathcal {S}$ be a subset of $Z$. A \emph{$\mathcal
{S}$-edge-weighting} of graph $G$ is an assignment of weight $s$ by
the elements of $\mathcal {S}$ to each edge of $G$.  A $\mathcal
{S}$-edge-weighting $w$ of   a graph $G$ induces a coloring of the
vertices of $G$, where the color of vertex $v$, denoted by $c(v)$,
is $\sum_{e\sim v}w(e)$. A $\mathcal {S}$-edge-weighting of a graph
$G$ is a \emph{vertex-coloring}   if for every edge $e = uv$,
$c(u)\neq c(v)$ and  we say that $G$ admits a \emph{vertex-coloring
$\mathcal {S}$-edge-weighting}.
  If $\mathcal {S}=\{1,2,\ldots,k\}$, then a
vertex-coloring $\mathcal {S}$-edge-weighting of graph $G$ is
usually called a \emph{vertex-coloring $k$-edge-weighting}.


%An $k$-edge-weighting of $G$ is an assignment $w : E(G)\rightarrow
%\{1,2,\ldots,k\}$. Given an $k$-edge-weighting, the weighted degree
%of a vertex $v$, denoted $c(v)$, is the sum of weights of the edges
%incident with $v$. An $k$-edge-weighting gives a vertex coloring if
%the weighted degrees of adjacent vertices are different.

For vertex-coloring edge-weighting, Karo\'nski, Luczak and Thomason
\cite{KLT} posed the following conjecture:
\begin{conjecture}\label{conj1}
Every graph with no isolated edge admits a vertex-coloring
$3$-edge-weighting.
\end{conjecture}
This conjecture is still wide open. Karo\'nski et al. \cite{KLT}
showed that the Conjecture \ref{conj1} is true for 3-colorable
graphs. Recently, Kalkowski et al. \cite{KKF} showed that every
graph with no isolated edge admits a vertex-coloring
5-edge-weighting. This result is an improvement on the previous
bounds on $k$ established by Addario-Berry et al. \cite{ADMRT},
Addario-Berry et al. \cite{ADR}, and Wang et al. \cite{WY}, who
obtained the bounds $k = 30, k = 16$, and $k = 13$, respectively.

Many graphs actually admit a vertex-coloring 2-edge-weighting (in
fact, experiments suggest (see \cite{ADR}) that almost all graphs
admit  a vertex-coloring 2-edge-weighting), however it is not known
which ones are not.  Chang et al and Lu et al (\cite{CLWY,LYZ}) have
made some progress in determining which classes of graphs admit
vertex-coloring 2-edge-weighting, notably having shown that
3-connected bipartite graphs are one such class. Khatirineja et al.
\cite{KNN} explored the problem of classifying those graphs which
admit a vertex-coloring 2-edge-weighting. %Moreover, they classified
%the minimal graphs which did not admit  vertex-coloring
%$2$-edge-weighting with respect to subgraph containment and also
%demonstrate techniques for constructing graphs which are not a
%vertex-coloring 2-edge-weighting.
Chang et al. \cite{CLWY}  proved that there exists a family of
infinite bipartite graphs (e.g., the generalized $\theta$-graphs)
which are 2-connected and have a vertex-coloring $3$-edge-weighting
but not  vertex-coloring $2$-edge-weightings.
%As a matter of fact, these two problems are not the same, in the
%sense that the corresponding families of graphs 0-1WEIGHT and
%1-2WEIGHT are not equal.

We write  \begin{align*}
 &\mathscr{G}_{12}=\{G\ |\ \mbox{$G$ admits a vertex-coloring
$\{1,2\}$-edge-weighting}\};\\
 &\mathscr{G}_{01}=\{G\ |\ \mbox{$G$ admits a vertex-coloring
$\{0,1\}$-edge-weighting}\};\\
& \mathscr{G}_{12}^{*}=\{G\ |\ \mbox{$G$ is bipartite and admits a
vertex-coloring
 $\{1,2\}$-edge-weighting}\};\\
& \mathscr{G}_{01}^*=\{G\ |\ \mbox{$G$ is bipartite and admits a
vertex-coloring $\{0,1\}$-edge-weighting}\}.
\end{align*}
 Dudek and  Wajc \cite{DW} showed that determining whether a graph belongs to
$\mathscr{G}_{12}$ or $\mathscr{G}_{01}$ is NP-complete. Moreover,
they showed that $\mathscr{G}_{12}\neq \mathscr{G}_{01}$. However,
the counterexamples constructed are non-bipartite. Let $C_6$  be a
cycle of length six and $\Gamma$ be a graph obtained by connecting
an isolated vertex to one of the  vertices of $C_6$. Take two
disjoint copies of $\Gamma$. Connect two vertices of degree one of
two copies and this gives a connected bipartite graph $G$. It is
easy to prove that $G$ admits a vertex-coloring 2-edge-weighting but
not  vertex-coloring $\{0,1\}$-edge-weightings. Hence
$\mathscr{G}_{01}^{*}\neq \mathscr{G}_{12}^{*}$. Next we would like
to propose the following problem.
%\begin{problem}
%Does $\mathscr{G}_{12}^{*}= \mathscr{G}_{12}^{*}$?
%\end{problem}
\begin{problem}
Determining  whether a graph  $G\in \mathscr{G}_{12}^{*}$ or
$G\in\mathscr{G}_{01}^{*}$ is polynomial?
\end{problem}

In this paper,  we characterize bipartite graphs which admit a
vertex-coloring $\mathcal {S}$-edge-weighting  for $\mathcal {S}\in
\{\{0,1\},\{1,2\}\}$, and obtain the following result.
\begin{theorem}\label{02EW}
Let $G$ be a 3-edge-connected bipartite graph $G=(U,W,E)$ with
minimum degree $\delta(G)$. If $G$ contains a vertex $u$ of degree
$\delta(G)$ such that $G-u$ is connected, then  $G$ admits a
vertex-coloring $\mathcal {S}$-edge-weighting for $\mathcal {S}\in
\{\{0,1\},\{1,2\}\}$.
\end{theorem}
By Theorem \ref{02EW}, it is easy to obtain the following result.
\begin{theorem}\label{02EW-conn}
Every 2-connected and 3-edge-connected bipartite graph $G=(U,W,E)$
admits a vertex-coloring $\mathcal {S}$-edge-weighting  for
$\mathcal {S}\in \{\{0,1\},\{1,2\}\}$.
\end{theorem}

So far,  all known counterexamples of bipartite graphs, which do not
have  vertex-coloring $\{0,1\}$-edge-weightings or vertex-coloring
$\{1,2\}$-edge-weightings  are graphs with minimum degree $2$. So we
would like to propose the following problem.
\begin{problem}
Does every bipartite graph with $\delta(G)\geq 3$ admit  a
vertex-coloring $\mathcal {S}$-edge-weighting, where $\mathcal
{S}\in \{\{0,1\},\{1,2\}\}$.
\end{problem}


%For vertex-coloring $\{0,1\}$-edge-weighting, the following result
%is a slight improvement of Theorem \ref{02EW}.
%\begin{theorem}\label{01EW}
%Let $G$ be 3-edge-connected bipartite graph with  $\delta(G)\geq 5$.
%If there exists a   vertex $u$   such that $G-u$ is connected and
%$d_G(u)=\delta$, then $G$ admits a vertex-coloring
%$\{0,1\}$-edge-weighting.
%%\begin{itemize}
%%\item[$(i)$] $\delta(G)\geq 5$, there exists a vertex $u\in V(G)$ such
%%that $G-u$ is connected and $d_G(u)\delta(G)$;
%%
%%\item[$(ii)$] $\delta(G)=4$, there exists a vertex $u\in V(G)$ such
%%that $G-u$ is connected, $d_G(u)=4$ and $\sum_{x\in
%%N_G(u)}d_G(x)>4|N_G(u)|$;
%%\end{itemize}
%\end{theorem}
%By Theorem \ref{01EW}, we can obtain the following result.
%\begin{theorem}\label{01EW-conn}
%Every 2-connected and $3$-edge-connected  bipartite graph  admits a
%vertex-coloring $\{0,1\}$-edge-weighting.
%\end{theorem}

A \emph{factor} of graph $G$ is a spanning subgraph. For a graph
$G$, there is a close relationship between 2-edge-weighting and
graph factors. Namely, a 2-edge-weighting problem is equivalent to
finding a special factor of graphs (see \cite{ADMRT,ADR}). So to
find factors with pre-specified degree is an important part of
edge-weighting.

Let $g,f:V(G)\rightarrow Z$ be two integer-valued function such that
$g(v)\leq f(v)$ and $g(v)\equiv f(v)\pmod 2$ for all $v\in V(G)$.  A
factor $F$ of $G$ is called \emph{$(g,f)$-parity factor} if
$g(v)\leq d_F(v)\leq f(v)$ and $d_F(v)\equiv f(v)\pmod 2$ for all
$v\in V(G)$. For $X\subseteq V(G)$, we write $g(X)=\sum_{x\in
X}g(x)$ and $f(X)$ is defined similarly. For $(g,f)$-parity factors,
Lov\'asz obtained a sufficient and necessary condition.
\begin{theorem}[Lov\'asz, \cite{Lovasz}]\label{Lovasz}
A graph $G$ contains a $(g,f)$-parity factor if and only if there
exist two disjoint subsets $S$ and $T$ such that
\begin{align*}
\eta(S,T)=f(S)-g(T)+\sum_{x\in T}d_{G-S}(x)-\tau(S,T)<0,
\end{align*}
where $\tau(S,T)$ denotes the number of components $C$, called
$g$-odd components  of $G-S-T$ such that $g(V(C))+e_G(V(C),T)\equiv
1\pmod 2$.
\end{theorem}


In the proof of main theorems, we need the following three Theorems.
\begin{theorem}[Chang et al., \cite{CLWY}]\label{Yu1}
  Every non-trivial connected bipartite graph $G = (A,B, E)$
with $|A|$ even admits a vertex-coloring 2-edge-weighting $w$ such
that $c(u)$ is odd for $u\in A$ and $c(v)$ is even for $v \in B$.
\end{theorem}

\begin{theorem}[Chang et al., \cite{CLWY}]\label{Yu2}
  Let $r\geq 3$ be an integer.  Every $r$-regular bipartite graph
  $G$ admits a vertex-coloring 2-edge-weighting.
\end{theorem}


\begin{theorem}[Khatirinejad et al., \cite{KNN}]\label{KNN}
    Every $r$-regular   graph
  $G$ admits a vertex-coloring 2-edge-weighting
   if and only if it admits a vertex-coloring $\{0,1\}$-edge-weighting.
\end{theorem}

\section{Proof of Theorem \ref{02EW}}

%By Theorem \ref{Yu1}, we have the following result.
\begin{coro} \label{Yu3}
  Every non-trivial connected bipartite graph $G = (A,B, E)$
with $|A|$ even admits a vertex-coloring $\{0,1\}$-edge-weighting..
\end{coro}

\pf By Theorem \ref{Yu1}, $G$ admits a vertex-coloring
2-edge-weighting $w$ such that $c(u)$ is odd for $u\in A$ and $c(v)$
is even for $v \in B$. Let $w'(e)=0$ if $w(e)=2$ and $w'(e)=1$ if
$w(e)=1$. Then $w'$ is a vertex-coloring $\{0,1\}$-edge-weighting of
graph $G$. \qed




Next, we show that the following two lemmas.

\begin{lemma}\label{lem1}
Let $G$ be a   bipartite graph $G$ with bipartition $(U,W)$, where
$|U|\equiv |W|\equiv 1\pmod 2$. Let $\delta(G)=\delta$ and $u\in U$
such that $d_G(u)=\delta$. If one of two conditions holds, then $G$
contains a factor $F$ such that $d_F(u)=\delta$, $d_F(x)\equiv
\delta+1\pmod 2$ for all $x\in U-u$, $d_F(y)\equiv \delta\pmod 2$
for all $y\in W$ and $d_F(y)\leq \delta-  2$ for all $y\in
N^{\delta}_G(u)$.
\begin{itemize}
\item[$(i)$] $\delta(G)\geq 4$, $G$ is 3-edge-connected and $G-u$ is connected.

\item[$(ii)$] $\delta(G)=3$, $G$ is  3-edge-connected and $|N^{\delta}_G(u)|\leq 2$.

%\item[$(iii)$] $\delta(G)\geq 4$, $G$ is  2-edge-connected and $G-u$ is
%connected.% and there exists a vertex $v\in N_G(u)$ such that
%$d_G(v)>4$.
\end{itemize}

%\begin{lemma}\label{lem1}
%Let $G=(U,W,E)$ be a  3-edge-connected bipartite graph, where
%$|U|\equiv |W|\equiv 1\pmod 2$. Let $\delta(G)=\delta$ and $u\in U$
%such that $d_G(u)=\delta$ and $$. If either $\delta\geq 4$ or
%$\delta(G)=3$ and $$, the $G$ contains a factor $F$ such that
%
%
%$G-u$ is connected, then $G$ contains a factor $F$, which satisfies
%the following conditions.
%\begin{itemize}
%\item[$(i)$] $d_F(u)=\delta$;
%
%\item[$(ii)$] $d_F(x)\equiv \delta\pmod 2$ for all $x\in W$
% and $d_F(x)\leq \delta-2$ for  all $x\in N^{\delta}_G(u)$;
%
%\item[$(iii)$]  $d_F(y)\equiv \delta+1\pmod 2$ for  all $y\in U-u$.
%\end{itemize}

%Then the following results hold.
%\begin{itemize}
%\item[$(i)$] if $\delta$ is odd, then $G$ contains a factor $F$ such
%that $d_F(u)=\delta$, $d_F(x)\equiv 0\pmod 2$   for all $x\in U-u$,
%$d_F(y)\equiv 1\pmod 2$   for all $x\in W$ and $d_F(y)\leq \delta-2$
%for  all $y\in N^{\delta}(u)$.
%
%\item[$(ii)$] if $\delta$ is even, then $G$ contains a factor $F$ such
%that $d_F(u)=\delta$, $d_F(x)\equiv 1\pmod 2$   for all $x\in U-u$,
%$d_F(y)\equiv 0\pmod 2$   for all $x\in W$ and $d_F(y)\leq \delta-2$
%for  all $y\in N^{\delta}(u)$.
%\end{itemize}
\end{lemma}

\pf Let $M$ be an integer such that $M\geq \triangle(G)$ and
$M\equiv \delta\pmod 2$ and let $m\in \{0,-1\}$ such that $m\equiv
\delta\pmod 2$.   %If $\delta$ is odd, then l
Let $g, f:V(G)\rightarrow Z$ such that
\[g(x)=\left\{\begin{array}{ll} \delta &\text{if}\
x=u, \\[5pt]
m &\text{if}\ x\in W,  \\[5pt]
m-1 &\text{if} \ x\in U-u,
\end{array}\right.\]
and
\[f(x)=\left\{\begin{array}{ll} M+1 &\text{if}\ x\in U-u,
\\[5pt]
M &\text{if} \ x\in (W\cup \{u\})-N^{\delta}_G(u), \\[5pt]
\delta-2 &\text{if} \ x\in N^{\delta}_G(u).
\end{array}\right.\]
%Else if $\delta$ is even, then let  $g, f:V(G)\rightarrow Z$ such
%that
%\[g(x)=\left\{\begin{array}{ll} \delta &\text{if}\
%x=u, \\[5pt]
%-1 &\text{if}\ x\in U-u,  \\[5pt]
%0 &\text{if} \ x\in W,
%\end{array}\right.\]
%and
%\[f(x)=\left\{\begin{array}{ll} M+1&\text{if}\ x\in U-u\,
%\\[5pt]
%M &\text{if} \ x\in (W\cup \{u\})-N^{\delta}_G(u) \\[5pt]
%\delta-2 &\text{if} \ x\in N^{\delta}_G(u).
%\end{array}\right.\]




By definition, we have $g(v)\equiv f(v)\pmod 2$ for all $v\in V(G)$.
It is sufficient for us to show that $G$ contains a $(g,f)$-parity
factor. Conversely, suppose that $G$ contains no $(g,f)$-parity
factors. By Theorem \ref{Lovasz}, there exist two disjoint subsets
$S$ and $T$ such that
\begin{align*}
\eta(S,T)=f(S)-g(T)+\sum_{x\in T}d_{G-S}(x)-\tau(S,T)<0,
\end{align*}
where $\tau(S,T)$ denotes the number of   $g$-odd components  of
$G-S-T$. Since $f(V(G))$ is even, by parity, we have
\begin{align}\label{eq:1}
\eta(S,T)=f(S)-g(T)+\sum_{x\in T}d_{G-S}(x)-\tau(S,T)\leq -2.
\end{align}
We choose $S$ and $T$ such that $S\cup T$ is minimal. Let
$A=V(G)-S-T$.

\medskip
\textbf{ Claim 1.~} $S\subseteq N^{\delta}_G(u)$.
\medskip

Otherwise, suppose that $S- N^{\delta}_G(u)\neq \emptyset$ and let
$v\in S-N^{\delta}_G(u)$. Let $S'=S-v$. We have
\begin{align*}
\eta(S',T)&=f(S')-g(T)+\sum_{x\in T}d_{G-S'}(x)-\tau(S',T) \\
&=f(S)-f(v)-g(T)+\sum_{x\in T}d_{G-S}(x)+e_G(v,T)-\tau(S',T)\\
&\leq f(S)-g_1(T)+\sum_{x\in
T}d_{G-S}(x)+e_G(v,T)-(\tau(S,T)-e_G(v,A))-f(v)\\
&=f(S)-g(T)+\sum_{x\in
T}d_{G-S}(x)-\tau(S,T)+(e_G(v,T)+e_G(v,A)-f(v))\\
&\leq f(S)-g(T)+\sum_{x\in
T}d_{G-S}(x)-\tau(S,T)+(d_G(v)-f(v))\\
 &\leq f(S)-g(T)+\sum_{x\in T}d_{G-S}(x)-\tau(S,T)\leq -2,
\end{align*}
contradicting to choice of $S$ and $T$.


\medskip
\textbf{ Claim 2.~} $T\subseteq \{u\}$.
\medskip

Otherwise, let   $v\in T-u$ and $ T'=T-v$. We have
\begin{align*}
\eta(S,T')&=f(S)-g(T')+\sum_{x\in T'}d_{G-S}(x)-\tau(S,T') \\
&=f(S)-g(T)+g(v)+\sum_{x\in T}d_{G-S}(x)-d_{G-S}(v)-\tau(S',T)\\
&\leq f(S)-g(T)+\sum_{x\in
T}d_{G-S}(x)-d_{G-S}(v)-(\tau(S,T)-e_G(v,A))+g(v)\\
&\leq f(S)-g(T)+\sum_{x\in
T}d_{G-S}(x)-\tau(S,T)+(g(v)-d_{G-S}(v)+e_G(v,A))\\
&\leq f(S)-g(T)+\sum_{x\in T}d_{G-S}(x)-\tau(S,T)\leq -2,
\end{align*}
contradicting to choice of $S$ and $T$.

We write $\tau(S,T)=\tau$.  By Claims 1 and 2, (\ref{eq:1}) implies
\begin{align}
\eta(S,T)&=f(S)-g(T)+\sum_{x\in T}d_{G-S}(x)-\tau \\
&=(\delta-2)|S|-\delta |T|+|T|(\delta-|S|)-\tau\\
&=(\delta-2-|T|)|S|-\tau\leq -2\label{eq:2},
\end{align}
which implies $\tau\geq 2$.

 Since $G$ is  3-edge-connected and $G-u$ is connected, then
we have $S\neq \emptyset$ and
\begin{align}\label{eq:3}
3\tau\leq
(\delta-|T|)|S|+|T|(\delta-|S|)=(\delta-2|T|)|S|+|T|\delta.
\end{align}
If $\delta\geq 4$, by (\ref{eq:2}) and (\ref{eq:3}), then  we have
\begin{align}\label{eq:4}
\delta\geq \delta|T|&\geq (2\delta-|T|-6)|S|+6\geq 2\delta-1,
\end{align}
a contradiction if $\delta\geq 4$. So we can assume that $\delta=3$.
Note that  $|S|\leq |N_G^{\delta}(u)|\leq 2$. By (\ref{eq:2}) and
(\ref{eq:3}), we have
\begin{align}\label{eq:41}
3=\delta\geq \delta|T|&\geq -|T||S|+6\geq 4,
\end{align}
a contradiction again.

 This completes the proof. \qed

\begin{lemma}\label{lem2}
Let $G$ be a   bipartite graph $G$ with bipartition $(U,W)$, where
$|U|\equiv |W|\equiv 1\pmod 2$. Let $\delta(G)=\delta$ and $u\in U$
such that $d_G(u)=\delta$. If one of two conditions holds, then $G$
contains a factor $F$ such that $d_F(u)=0$, $d_F(x)\equiv 1\pmod 1$
for all $x\in U-u$, $d_F(y)\equiv 0\pmod 2$   for all $x\in W$ and
$d_F(y)\geq  2$ for all $y\in N_G(u)$.
\begin{itemize}
\item[$(i)$] $\delta(G)\geq 4$, $G$ is 3-edge-connected and $G-u$ is connected.

\item[$(ii)$] $\delta(G)=3$, $G$ is  3-edge-connected and there exists a vertex $v\in N_G(u)$
such that $d_G(v)>3$.

%\item[$(iii)$] $\delta(G)\geq 4$, $G$ is  2-edge-connected and $G-u$ is
%connected.% and there exists a vertex $v\in N_G(u)$ such that
%$d_G(v)>4$.
\end{itemize}



\end{lemma}

\pf Let $M$ be an even integer such that $M\geq \triangle(G)$. Let
$g, f:V(G)\rightarrow Z$ such that
\[g(x)=\left\{\begin{array}{ll} 0 &\text{if}\
x\in (\{u\}\cup W)-N_G(u), \\[5pt]
2 &\text{if}\ x\in N_G(u),  \\[5pt]
-1 &\text{if} \ x\in U-u,
\end{array}\right.\]
and
\[f(x)=\left\{\begin{array}{ll} M+1 &\text{if}\ x\in U-u\,
\\[5pt]
M &\text{if} \ x\in W,\\[5pt]
0 &\text{if} \ x=u.
\end{array}\right.\]
Clearly, $g(v)\equiv f(v)\pmod 2$ for all $v\in V(G)$ and $g(V(G))$
is even. It is also sufficient for us to show that $G$ contains a
$(g,f)$-parity factor. Conversely, suppose that $G$ contains no
$(g,f)$-parity factors.   By Theorem \ref{Lovasz}, there exist two
disjoint subsets $S$ and $T$ such that
 \begin{align}\label{eq:5}
\eta(S,T)=f(S)-g(T)+\sum_{x\in T}d_{G-S}(x)-\tau(S,T)\leq -2,
\end{align}
where $\tau(S,T)$ denotes the number of   $g$-odd components  of
$G-S-T$. With similar proof in Lemma \ref{lem1}, we can say
$S\subseteq \{u\}$ and $T\subseteq N_G(u)$. Hence $f(S)=0$ and
$g(T)=2|T|$.  For simplicity, we write $\tau(S,T)=\tau$. By
(\ref{eq:5}), we have
\begin{align}\label{eq:6}
\tau\geq \sum_{x\in T}(d_{G}(x)-|S|)-2|T|+2\geq 2.
\end{align}
Note that $G-u$ is connected, so  we have $|S|\leq 1\leq |T|$. Since
$G$ is 3-edge-connected, then we have
\begin{align}\label{eq:7}
3\tau\leq \sum_{x\in T}(d_{G}(x)-|S|)+(\delta-|T|)|S|.
\end{align}
(\ref{eq:6}) and (\ref{eq:7}) implies
\begin{align}\label{eq:8}
2\sum_{x\in T}d_G(x)+6\leq |S||T|+6|T|+\delta|S|\leq 7|T|+\delta.
\end{align}
If $\delta\geq 4$, then we have $7|T|\geq 6+\delta(2|T|-1)\geq
8|T|+2$, a contradiction. So we can assume that $\delta=3$.
% Since
%$7|T|\geq 6+\delta(2|T|-1)$, then $|T|\geq 3$.
%By Claim 2, $|T|\leq
%\delta$. Hence we obtain $|T|=3$.
By condition (ii),    $\sum_{x\in T}d_G(x)\geq 3|T|+1$ and $G-u$ is
connected. Combining (\ref{eq:8}),  we have $|T|\geq 5$, a
contradiction since $|T| \leq |N_G(u)|\leq 3$.

%Now we prove (iii). Since $G$ is 2-edge-connected, then
%\begin{align}\label{eq:9}
%2\tau\leq \sum_{x\in T}(d_{G}(x)-|S|)+(\delta-|T|)|S|.
%\end{align}
%Since $G-u$ is connected and $\tau\geq 2$, then $|T|\geq 1$. If
%$|S|=0$, by (\ref{eq:6}) and (\ref{eq:9}), we have
%\begin{align}\label{eq:10}
% \sum_{x\in T} d_{G}(x)+2\leq 2|T|,
%\end{align}
%a contradiction. So we can say $|S|=1$. Then (\ref{eq:6}) and
%(\ref{eq:9}) implies
%\begin{align}\label{eq:11}
%4|T|+\delta\geq \sum_{x\in T} d_{G}(x)+4\geq \delta|T|+4.
%\end{align}
%(\ref{eq:10}) holds only if $|T|=1$ and $d_{G}(x)=4$ for $x\in T$.
% Hence we have $\delta\leq 4$, a
%contradiction.

 This completes this proof. \qed



\noindent\textbf{Proof of Theorem \ref{02EW}.} By Theorem \ref{Yu1}
and Corollary \ref{Yu3}, we can assume that both $|A|$ and $|B|$ are
odd.


 Firstly, we consider
$\mathcal {S}=\{0,1\}$. If $G$ is 3-regular, by Theorem \ref{Yu2},
then  $G$ admits a vertex-coloring 2-edge-weighting. By Theorem
\ref{KNN}, $G$ also admits a vertex-coloring
$\{0,1\}$-edge-weighting.
%
%
%So $G$ contains a factor $H$ such that two adjacent vertices has
%different degree. We assign edge one for each edge of $E(H)$ and
%edge zero for each edge of $E(G)-E(H)$. Then we obtain a
%vertex-coloring $\{0,1\}$-edge-weighting of graph $G$.
So we can assume that $\delta(G)\geq 3$ and $G$ is not 3-regular. If
$\delta(G)=3$, since $G$ is 3-edge-connected, then $G-x$ is
connected for every vertex $x$ of $G$ with degree no more than four.
Hence   $G$ contains a vertex $v$ with degree three such that $G-v$
is connected and $\sum_{x\in N_G(v)}d_G(v)\geq 3|N_G(v)|+1$. Let
\[u^*=\left\{\begin{array}{ll} u &\text{if}\
\delta \geq 4, \\[5pt]
v &\text{if}\ \delta =3.
\end{array}\right.\]
Without loss generality, we can assume that $u^*\in U$ and so it  is
a vertex satisfying the conditions of Lemma \ref{lem2}. Hence by
Lemma \ref{lem2}, $G$ contains a factor $F$, which satisfies the
following three conditions.
\begin{itemize}
\item[$(i)$]
$d_F(u^*)=0$;

\item[$(ii)$] $d_F(x)\equiv 1\pmod 2$ for all $x\in U-u^*$;

\item[$(iii)$]
$d_F(y)\equiv 0\pmod 2$ for all $x\in W$ and $d_F(y)\geq 2$ for all
$y\in N_G(u^*)$.
\end{itemize}
Clearly, $d_F(x)\neq d_F(y)$ for all $xy \in E(G)$. We assign weight
one for each edge of $E(F)$ and weight zero for each edge of
$E(G)-E(F)$. Then we obtain a vertex-coloring
$\{0,1\}$-edge-weighting of graph $G$.

 Secondly, we show that $G$ admits a vertex-coloring
 2-edge-weighting. By above discussion, we can assume that $G$
 is not 3-regular. If $\delta=3$, since $G$ is 3-edge-connected,
 then $G$ contains a vertex $v'$
 such that  $d_G(v')=3$, $G-v'$ is connected and $|N_G^{\delta}(v')|\leq 2$.

Similarly, we can assume  that $u^*\in U$ is a vertex satisfying the
conditions of Lemma \ref{lem1}. Hence  by Lemma \ref{lem1}, $G$
contains a factor a factor
 $F$ such that
\begin{itemize}
\item[$(i)$] $d_F(u^*)=\delta$;

\item[$(ii)$] $d_F(x)\equiv \delta\pmod 2$ for all $x\in W$
 and $d_F(x)\leq \delta-2$ for  all $x\in N^{\delta}_G(u^*)$;

\item[$(ii)$]  $d_F(y)\equiv \delta+1\pmod 2$ for  all $y\in U-u^*$.
\end{itemize}
Let $w$ be a 2-edge-weighting such that $w(e)=1$ for each $e\in
E(F)$ and $w(e')=2$ for each $e'\in E(G)-E(F)$. Clearly,
$c(u^*)=\delta$. If $y\in N^{\delta}_G(u^*)$, since there exists an
edge $e\sim y$ such that $e\notin E(F)$, then $c(y)=\sum_{e\sim
y}w(e)>\delta$. If $y\in N_G(u^*)- N^{\delta}_G(u^*)$, then
$c(y)\geq d_G(y)>\delta$. Hence $c(y)\neq c(u^*)$ for all $y\in
N_G(u^*)$. For each $xy\in E(G)$, where $x\in U-u^*$ and $y\in W$,
by the choice of $F$, we have $c(x)\equiv \delta+1\pmod 2$ and
$c(y)\equiv \delta\pmod 2$. Hence $w$ is a vertex-coloring
$\{1,2\}$-edge-weighting of graph $G$.

%Now we consider $\delta=3$. If $G$ is 3-regular, by Theorem
%\ref{Yu2}, then $G$ admits a vertex-coloring 2-edge-weighting. So we
%can assume that $G$ is not 3-regular. By Lemma \ref{lem2}, $G$
%contains a factor $F$ such that
%\begin{itemize}
%\item[$(i)$]
%$d_F(u)=0$;
%
%\item[$(ii)$] $d_F(x)\equiv 1\pmod 2$ for all $x\in U-u$;
%
%\item[$(iii)$]
%$d_F(y)\equiv 0\pmod 2$ for all $x\in W$ and $d_F(y)\geq2$ for all
%$y\in N_G(u)$.
%\end{itemize}




  %%We discuss two
%%cases. Suppose that the bipartition is $(A,B)$. Let $u\in A$ and
%%$d_G(u)=\delta$.
%%
%%\medskip
%%\textbf{ Case 1.~} $\delta$ is odd.
%%\medskip
%%
%%By Lemma \ref{lem1} (i), $G$ contains a factor $F$ satisfies the
%%following conditions:
%%\begin{itemize}
%%\item[$(i)$]
%%$d_F(x)$ is even for all $x\in A-u$;
%%
%%\item[$(ii)$] $d_F(y)$ is odd for all $y\in
%%B\cup \{u\}$;
%%
%%\item[$(iii)$] $d_F(u)=\delta$ and $d_F(y)\leq \delta-2$.
%%\end{itemize}
%%Assigning  $w(e)=1$ for every $e\in E(F)$ and  $w(e)=2$ for all
%%$e\in E(G)-E(F)$. Now we show that the   edge-weighting is
%%vertex-coloring.  Clearly, $c(x)\geq d_G(x)\geq \delta+1$ for every
%%$x\in N_G(u)-N^{\delta}_G(u)$. For $y\in N^{\delta}(u)$, we have
%%$c(y)\geq d_F(y)+2(\delta-d_F(y))\geq \delta+2$. Since $c(x)$ is
%%even for all $x\in A-u$ and  $c(y)$ is odd for all $y\in B$, then we
%%have $c(x)\neq  c(y)$ for all $xy\in E(G)$. Hence $G$ admits a
%%vertex-coloring 2-edge-weighting.
%%
%%\medskip
%%\textbf{ Case 2.~} $\delta$ is even.
%%\medskip
%%
%%\begin{itemize}
%%\item[$(i)$]
%%$d_F(x)$ is odd for all $x\in A-u$;
%%
%%\item[$(ii)$] $d_F(y)$ is even for all $y\in
%%B\cup \{u\}$;
%%
%%\item[$(iii)$] $d_F(u)=\delta$ and $d_F(y)\leq \delta-2$.
%%\end{itemize}
%%Assigning  $w(e)=1$ for every $e\in E(F)$ and  $w(e)=2$ for all
%%$e\in E(G)-E(F)$. With similar proof of Case 1, the edge-weighting
%%is a vertex-coloring.

This completes the proof. \qed




%\begin{lemma}\label{lem3}
%Let $G$ be a  2-edge-connected bipartite graph $G$ with
%$\delta(G)\geq 5$ and bipartition $(U,W)$, where $|U|\equiv
%|W|\equiv 1\pmod 2$. Let $u\in U$ such that $d_G(u)=\delta(G)$ and
%$G-u$ is connected.  Then $G$ contains a factor $F$ such that
%$d_F(u)=0$, $d_F(x)\equiv 0\pmod 1$   for all $x\in U-u$,
%$d_F(y)\equiv 0\pmod 2$   for all $x\in W$ and $d_F(y)\geq  2$ for
%all $y\in N_G(u)$.
%\end{lemma}



\begin{coro}
Let $G$ be a 3-edge-connected bipartite graph. If
$3\leq\delta(G)\leq 5$, then $G$ admits a vertex-coloring $\mathcal
{S}$-edge-weighting for $\mathcal {S}\in \{\{0,1\},\{1,2\}\}$.
\end{coro}

\pf  Since $ 3\leq\delta \leq 5$ and $G$ is 3-edge-connected, then
for every vertex $v$ of degree $\delta$, $G-v$ is connected. By
Lemma \ref{lem1} and Theorem \ref{02EW}, with the same proof, $G$
admits a vertex-coloring $\mathcal {S}$-edge-weighting for $\mathcal
{S}\in \{\{0,1\},\{1,2\}\}$. \qed


%\noindent \textbf{The Proof of Theorem \ref{02EW}.} Similarly, we
%only consider that $|A|=|B|$ is odd. %By Theorem \ref{}, we can
%%assume that $G$ is not 4-regular.
%%Firstly, we consider $$
%Let $u$ and $v$ be two adjacent vertices such that $G-u$ is
%connected and $d_G(u)=\delta$.  By Lemma \ref{lem2} (iii), there
%exists a factor $F$ such that $d_F(u)=0$, $d_F(x)$  is odd for all
%$x\in A-u$, $d_F(y)$ is even for all $y\in B$ and $d_F(y)\geq 2$ for
%all $y\in N_G(u)$. So by Theorem \ref{}, $G$ admits a vertex-coloring
%$\{0,1\}$-edge-weighting.


%By Lemma \ref{lem2}, %with similar proof in Theorem \ref{02EW},
%we
%have the following result.
%\begin{theorem}
%Every 2-connected graph with $\delta(G)\geq 4$  admits a
%vertex-coloring $\{0,1\}$-edge-weighting.
%\end{theorem}

%\noindent \textbf{Proof of Theorem \ref{01EW-conn}.}


 %If
%$\delta(G)\geq 5$, since $G$ is 2-connected, the result is followed
%by Theorem \ref{02EW}. So we can assume $\delta(G)=4$. If $G$ is
%4-regular, by Theorems \ref{} and \ref{}, $G$ admits a
%vertex-coloring $\{0,1\}$-edge-weighting. Now we say $G$ is not
%$4$-regular. Then $G$ contains two adjacent vertices $u$ and $v$
%such that $d_G(u)=4$ and $d_G(v)>4$. Since $G$ is 2-connected, then
%$G-u$ is connected.  By Theorem \ref{02EW}, $G$ admits a
%vertex-coloring $\{0,1\}$-edge-weighting. This completes the proof.
%\qed





%\begin{conjecture}
%Every 2-connected bipartite graph with $\delta(G)\geq 3$ admits a
%vertex-coloring $\{0,1\}$-edge-weighting.
%
%\end{conjecture}

%\begin{theorem}
% Every nice bipartite graph with $\delta(G)\geq 6$ admits an adjacent vertex-distinguishing
%2-edge-weighting.
%\end{theorem}


%\begin{coro}
%Every 3-edge-connected nice bipartite graph admits an adjacent
%vertex-distinguishing 2-edge-weighting.
%\end{coro}


\begin{coro}
Let $G$ be a bipartite graph with minimum degree $\delta\geq 4$. If
$G$ is $(\lfloor \frac{\delta}{2}\rfloor+1)$-edge-connected, then
$G$ admits a vertex-coloring $\mathcal {S}$-edge-weighting for
$\mathcal {S}\in \{\{0,1\},\{1,2\}\}$.
\end{coro}


%Now suppose that $\delta=6$ and for every vertex $x\in V(G)$ with
%degree $\delta$,  $G-x$ is not connected. Let $d_G(v)=\delta$ and
%$v'\in N^{\delta}(v)$. Assume $G-v$ contains two components $G_1$
%and $G_2$ and $v'\in V(G_2)$. Since $G-v'$ is not connected, then
%$G_2-v'$ is also not connected. Suppose that $G_2-v'$   contains two
%components $G_{21}$ and $G_{22}$.



%Since neither $G-v$ and $G-v'$ is connected, then $G-v-v'$ contains
%at least three

%\begin{conjecture}
%Every 3-edge-connected nice bipartite graph admits an adjacent
%vertex-coloring 2-edge-weighting.
%\end{conjecture}



\section{Conclusions}

Let $\mathcal {S}\in \{\{0,1\},\{1,2\}\}$. In this paper, we prove
that every $2$-connected and $3$-edge-connected bipartite graph
admit a vertex-coloring $\mathcal {S}$-edge-weighting. The
generalized $\theta$-graphs  is 2-connected and has a
vertex-coloring $3$-edge-weighting but not a vertex-coloring
$\mathcal {S}$-edge-weightings. So it is an interesting problem to
classify all $2$-connected bipartite graphs admitting a
vertex-coloring $\mathcal {S}$-edge-weighting. Since parity-factor
problem is polynomial, then there exists a polynomial algorithm to
find a vertex-coloring $\mathcal {S}$-edge-weighting of bipartite
graphs satisfying the conditions of  Theorem \ref{02EW}.

%\section*{Acknowledgments}
%The authors would like to thank .

\begin{thebibliography}{99}

\bibitem{AADR} L. Addario-Berry, R. E. L. Aldred, K. Dalal and B. A.
Reed, Vertex coloring edge partitions, \textit{J. Combinatorial
Theory Ser. B}, \textbf{94} (2005), 237-244.

\bibitem{ADMRT} L. Addario-Berry, K. Dalal, C. McDiarmid, B. A.
Reed and A. Thomason, Vertex-coloring edge-weightings,
\textit{Combintorica,} {\bf 27} (2007), 1-12.

\bibitem{ADR} L. Addario-Berry, K. Dalal and B. A. Reed, Degree
constrained subgraphs, \textit{Discrete Applied Math.}, {\bf 156}
(2008), 1168-1174.
%
%\bibitem{ATT} M. Aigner, E. Triesch and Zs. Tuza, Irregular
%assignments and vertex-distinguishing edge-colorings of graphs,
%\textit{Combinatorics,} \textbf{90}, (A. Barlotti et al, editors),
%Elsevier Science Pub., New York (1992), 1-9.

%\bibitem{amahashi} A. Amahashi and M. Kano, On factors with
%given components, \textit{Discrete Math.,} \textbf{42} (1982), 1-6.


%\bibitem{BRS} P. N. Balister, O. M. Riordan and R. H. Schelp,
%Vertex-distinguishing edge colorings of graphs, \textit{J. Graph
%Theory}, \textbf{42} (2003), 95-109.

%\bibitem{BB} B. Bollob\'{a}s, {\it Modern Graph Theory}, 2nd Edition,
%Springer-Verlag New York, Inc. 1998.
%
%\bibitem{BS} A. C. Burris and R. H. Schelp, Vertex-distinguishing
%proper edge colorings, \textit{J.  Graph Theory,} \textbf{26}
%(1997), 73-82.

\bibitem{CLWY} G. Chang, C. Lu, J. Wu and
Q. Yu, Vertex coloring $2$-edge weighting of bipartite graphs,
\emph{Taiwanese J. Math.}, \textbf{15} (2011), 1807-1813.



\bibitem{DW}
A. Dudek and D. Wajc, On the complexity of vertex-coloring
edgeweightings, \emph{Discrete Math. Theor. Comput. Sci.},
\textbf{13} (2011), 45-50.

\bibitem{KKF}
M. Kalkowski, M. Karo\'nski  and F. Pfender, Vertex-coloring
edge-weightings: towards the 1-2-3-conjecture, \emph{J. Combin.
Theory Ser. B}, \textbf{100} (2010), 347-349.


%\bibitem{Edwards} K. Edwards, The harmonioous chromatic number of
%bounded degree graphs, \textit{J. London Math. Soc.}, \textbf{55}
%(1997), 435-447.

%\bibitem{H} K. Heinrich, P. Hell, D. G. Kirkpatrick and G. Z. Liu, A
%simple existence criterion for $(g<f)$-factors, \textit{Discrete
%Math.}, \textbf{85} (1990), 313-317.

\bibitem{KLT} M. Karo\'{n}ski, T. {\L}uczak and A. Thomason, Edge
weights and vertex colors, \textit{J. Combinatorial Theory Ser. B},
\textbf{91} (2004), 151-157.

\bibitem{KNN} M. Khatirinejad,  R. Naserasr, M. Newman,
B. Seamone and B. Stevens,  Vertex-colouring edge-weightings with
two edge weights, \emph{Discrete Mathematics and Theoretical
Computer Science},   \textbf{14} (2012), 1-20.

\bibitem{Lovasz} L. Lov\'asz, Subgraphs with prescribed valencies,
 \textit{J. Combin. Theory},
\textbf{8} (1972), 391-416.

\bibitem{LYZ} H. Lu, Q. Yu and C. Zhang,
Vertex-coloring 2-edge-weighting of graphs,
European J. Combin.,  \textbf{32} (2011), 22-27.


\bibitem{WY} T. Wang and Q.  Yu, A note on vertex-coloring
$13$-edge-weighting,  \textit{Frontier Math. in China}, \textbf{3}
(2008), 1-7.

\end{thebibliography}


\end{document}

1307.1863.extracted_bib
\begin{thebibliography}{99}

\bibitem{AADR} L. Addario-Berry, R. E. L. Aldred, K. Dalal and B. A.
Reed, Vertex coloring edge partitions, \textit{J. Combinatorial
Theory Ser. B}, \textbf{94} (2005), 237-244.

\bibitem{ADMRT} L. Addario-Berry, K. Dalal, C. McDiarmid, B. A.
Reed and A. Thomason, Vertex-coloring edge-weightings,
\textit{Combintorica,} {\bf 27} (2007), 1-12.

\bibitem{ADR} L. Addario-Berry, K. Dalal and B. A. Reed, Degree
constrained subgraphs, \textit{Discrete Applied Math.}, {\bf 156}
(2008), 1168-1174.
%
%\bibitem{ATT} M. Aigner, E. Triesch and Zs. Tuza, Irregular
%assignments and vertex-distinguishing edge-colorings of graphs,
%\textit{Combinatorics,} \textbf{90}, (A. Barlotti et al, editors),
%Elsevier Science Pub., New York (1992), 1-9.

%\bibitem{amahashi} A. Amahashi and M. Kano, On factors with
%given components, \textit{Discrete Math.,} \textbf{42} (1982), 1-6.


%\bibitem{BRS} P. N. Balister, O. M. Riordan and R. H. Schelp,
%Vertex-distinguishing edge colorings of graphs, \textit{J. Graph
%Theory}, \textbf{42} (2003), 95-109.

%\bibitem{BB} B. Bollob\'{a}s, {\it Modern Graph Theory}, 2nd Edition,
%Springer-Verlag New York, Inc. 1998.
%
%\bibitem{BS} A. C. Burris and R. H. Schelp, Vertex-distinguishing
%proper edge colorings, \textit{J.  Graph Theory,} \textbf{26}
%(1997), 73-82.

\bibitem{CLWY} G. Chang, C. Lu, J. Wu and
Q. Yu, Vertex coloring $2$-edge weighting of bipartite graphs,
\emph{Taiwanese J. Math.}, \textbf{15} (2011), 1807-1813.



\bibitem{DW}
A. Dudek and D. Wajc, On the complexity of vertex-coloring
edgeweightings, \emph{Discrete Math. Theor. Comput. Sci.},
\textbf{13} (2011), 45-50.

\bibitem{KKF}
M. Kalkowski, M. Karo\'nski  and F. Pfender, Vertex-coloring
edge-weightings: towards the 1-2-3-conjecture, \emph{J. Combin.
Theory Ser. B}, \textbf{100} (2010), 347-349.


%\bibitem{Edwards} K. Edwards, The harmonioous chromatic number of
%bounded degree graphs, \textit{J. London Math. Soc.}, \textbf{55}
%(1997), 435-447.

%\bibitem{H} K. Heinrich, P. Hell, D. G. Kirkpatrick and G. Z. Liu, A
%simple existence criterion for $(g<f)$-factors, \textit{Discrete
%Math.}, \textbf{85} (1990), 313-317.

\bibitem{KLT} M. Karo\'{n}ski, T. {\L}uczak and A. Thomason, Edge
weights and vertex colors, \textit{J. Combinatorial Theory Ser. B},
\textbf{91} (2004), 151-157.

\bibitem{KNN} M. Khatirinejad,  R. Naserasr, M. Newman,
B. Seamone and B. Stevens,  Vertex-colouring edge-weightings with
two edge weights, \emph{Discrete Mathematics and Theoretical
Computer Science},   \textbf{14} (2012), 1-20.

\bibitem{Lovasz} L. Lov\'asz, Subgraphs with prescribed valencies,
 \textit{J. Combin. Theory},
\textbf{8} (1972), 391-416.

\bibitem{LYZ} H. Lu, Q. Yu and C. Zhang,
Vertex-coloring 2-edge-weighting of graphs,
European J. Combin.,  \textbf{32} (2011), 22-27.


\bibitem{WY} T. Wang and Q.  Yu, A note on vertex-coloring
$13$-edge-weighting,  \textit{Frontier Math. in China}, \textbf{3}
(2008), 1-7.

\end{thebibliography}