\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Carl Johan Casselgren }
%
%
\medskip
\noindent
%
%
{\bf A Note on Path Factors of $(3,4)$-Biregular Bipartite Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
A proper edge coloring of a graph $G$ with
colors $1,2,3,\dots$ is called an
interval coloring if the colors on the edges incident with any
vertex are consecutive.
A bipartite graph is $(3,4)$-biregular
if all vertices in one part have degree $3$ and
all vertices in the other part have degree $4$. Recently it was proved
[\emph{J. Graph Theory} 61 (2009), 88-97] that
if such a graph $G$ has a spanning subgraph whose components are
paths with endpoints at
3-valent vertices and lengths in $\{2, 4, 6, 8\}$,
then $G$ has an interval coloring. It was
also conjectured that every simple $(3,4)$-biregular
bipartite graph has such a subgraph.
We provide some evidence for this conjecture by proving that a simple
$(3,4)$-biregular bipartite graph has a spanning subgraph whose components
are nontrivial paths with endpoints at $3$-valent vertices and lengths not exceeding $22$.
\end{document}