% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}

\begin{document}
\setcounter{page}{133}
\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{Interval total colorings of bipartite graphs}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author[a,b]{P.A. Petrosyan},
\ead{pet\_petros@ipia.sci.am}
\author[a]{A.S. Shashikyan}
\ead{anishashikyan@gmail.com}
\author[a]{A.Yu. Torosyan}
\ead{arman.yu.torosyan@gmail.com}

\address[a]{Department of Informatics and Applied Mathematics,YSU}
\address[b]{Institute for Informatics and Automation Problems of NAS of RA}

\begin{keyword}
total coloring, interval coloring, bipartite graph, tree, complete
bipartite graph
\end{keyword}

\end{frontmatter}

% main text
\section{Introduction}

A total coloring of a graph $G$ is a coloring of its vertices and
edges such that no adjacent vertices, edges, and no incident
vertices and edges obtain the same color. The concept of total
coloring was introduced by V. Vizing \cite{b15} and independently by
M. Behzad \cite{b3}. The total chromatic number $\chi^{\prime
\prime}\left( G\right)$ is the smallest number of colors needed for
total coloring of $G$. In 1965 V. Vizing and M. Behzad conjectured
that $\chi ^{\prime\prime}\left( G\right)\leq \Delta (G)+2$ for
every graph $G$ \cite{b3,b15}, where $\Delta (G)$ is the maximum
degree of a vertex in $G$. This conjecture became known as Total
Coloring Conjecture \cite{b5}. It is known that Total Coloring
Conjecture holds for cycles, for complete graphs, for bipartite
graphs, for complete multipartite graphs \cite{b17}, for graphs with
a small maximum degree \cite{b6,b11,b14}, for graphs with minimum
degree at least $\frac{3}{4}\vert V(G)\vert$ \cite{b5} and for
planar graphs $G$ with $\Delta(G)\neq 6$ \cite{b5,b7,b13,b16}. M.
Rosenfeld \cite{b11} and N. Vijayaditya \cite{b14} independently
proved that the total chromatic number of graphs $G$ with $\Delta
(G)=3$ is at most $5$. A. Kostochka in \cite{b6} proved that the
total chromatic number of graphs with $\Delta(G)\leq 5$ is at most
$7$. The general upper bound for the total chromatic number was
obtained by M. Molloy and B. Reed \cite{b8}, who proved that
$\chi^{\prime\prime}\left( G\right)\leq \Delta (G)+10^{26}$ for
every graph $G$. The exact value of the total chromatic number is
known only for paths, cycles, complete and complete bipartite
graphs, $n$-dimensional cubes, complete multipartite graphs of odd
order \cite{b5}, outerplanar graphs \cite{b18} and planar graphs $G$
with $\Delta (G)\geq 9$ \cite{b4,b5,b7,b16}.

The key concept discussed in this work is the following. Given a
graph $G$, we say that $G$ is interval total colorable if there is
$t\geq 1$ for which $G$ has a total coloring with colors $1,2,\ldots
,t$ such that at least one vertex or edge of $G$ is colored by $i,$
$i=1,2,\ldots ,t,$ and the edges incident with each vertex $v$
together with $v$ are colored by $d_{G}(v)+1$ consecutive colors,
where $d_{G}(v)$ is the degree of the vertex $v$ in $G$.

The concept of interval total coloring \cite{b9,b10} is a new one in
graph coloring, synthesizing interval colorings \cite{b1,b2} and
total colorings. The introduced concept is valuable as it connects
to the problems of constructing a timetable without a
\textquotedblleft gap\textquotedblright and it extends to total
colorings of graphs one of the most important notions of classical
mathematics - the one of continuity.

In this work interval total colorings of bipartite graphs are
investigated.

\section{Main results}

All graphs considered in this work are finite, undirected, and have
no loops or multiple edges. Let $V(G)$ and $E(G)$ denote the sets of
vertices and edges of $G$, respectively. An $(a,b)$-biregular
bipartite graph $G$ is a bipartite graph $G$ with the vertices in
one part have degree $a$ and the vertices in the other part have
degree $b$. An interval total $t$-coloring of a graph $G$ is a total
coloring of $G$ with colors $1,2,\ldots ,t$ such that at least one
vertex or edge of $G$ is colored by $i$, $i=1,2,\ldots,t$, and the
edges incident to each vertex $v$ together with $v$ are colored by
$d_{G}(v)+1$ consecutive colors. The set of all interval total
colorable graphs is denoted by $\mathfrak{T}$. For a graph $G\in
\mathfrak{T}$, the least (the minimum span) and the greatest (the
maximum span) values of $t$ for which $G$ has an interval total
$t$-coloring is denoted by $w_{\tau }\left( G\right)$ and $W_{\tau
}\left( G\right)$, respectively. Clearly,

\begin{center}
$\chi^{\prime \prime}\left(G\right)\leq w_{\tau }\left( G\right)\leq
W_{\tau }\left(G\right)\leq \vert V(G)\vert + \vert E(G)\vert$ for
every graph $G\in \mathfrak{T}$.
\end{center}

First, we give a general upper bound for the maximum span in
interval total colorings of bipartite graphs.

\textbf{Theorem 1.} If $G$ is a connected bipartite graph and $G\in
\mathfrak{T}$, then
\begin{center}
$W_{\tau}(G)\leq 2\vert V(G)\vert -1$.
\end{center}

Note that the bound of Theorem 1 is sharp for the simple path
$P_{n}$, since $W_{\tau}(P_{n})=2n-1$ for any $n\in \mathbf{N}$.

Next, we show that many bipartite graphs such as subcubic bipartite
graphs, regular bipartite graphs, trees, complete bipartite graphs,
$n$-dimensional cubes, $\left(2,b\right)$-biregular bipartite
graphs, doubly convex bipartite graphs, grids and some classes of
bipartite graphs with maximum degree $4$ have interval total
colorings. Moreover, we also obtain some bounds for the minimum span
and the maximum span in interval total colorings of these graphs. In
particular, we prove the following theorems.

\textbf{Theorem 2.} If $G$ is a bipartite graph with $\Delta (G)\leq
3$, then $G\in \mathfrak{T}$ and $w_{\tau }\left(G\right)\leq 5$.

\textbf{Theorem 3.} If $G$ is an $r$-regular bipartite graph with
$r\geq 2$, then $G\in \mathfrak{T}$ and $r+1\leq w_{\tau
}\left(G\right)\leq r+2$.

Note that for any $r\geq 3$, there is an $r$-regular bipartite graph
such that $G\in \mathfrak{T}$ and $w_{\tau }\left(G\right)= r+2$. In
\cite{b12}, it was proved that the problem of determining whether
$\chi^{\prime \prime}\left(G\right)=4$ is $NP$-complete even for a
cubic bipartite graph $G$. Therefore we can conclude that
verification whether $w_{\tau }\left(G\right)= r+1$ for an
$r$-regular bipartite graph $G$ with $r\geq 3$ is also
$NP$-complete.

\textbf{Theorem 4.} If $T$ is a tree, then $T\in \mathfrak{T}$ and
$w_{\tau }\left(T\right)\leq \Delta(T)+2$.

\textbf{Theorem 5.} If $m+n+2-\gcd \left(m,n\right)\leq t\leq
m+n+1$, where $\gcd \left(m,n\right)$ is the greatest common divisor
of $m$ and $n$, then the complete bipartite graph $K_{m,n}$ has an
interval total $t$-coloring for any $m,n\in \mathbf{N}$.

\textbf{Theorem 6.} For any $m,n\in \mathbf{N}$
\begin{center}
$W_{\tau }\left(K_{m,n}\right)=\left\{
\begin{tabular}{ll}
$m+n+1$, & if $m=n=1$,\\
$m+n+2$, & otherwise.\\
\end{tabular}%
\right.$
\end{center}

\textbf{Theorem 7.} For the $n$-dimensional cube $Q_{n}$, we have
$Q_{n}\in \mathfrak{T}$ with
\begin{center}
$w_{\tau }\left(Q_{n}\right)=\chi^{\prime\prime}\left( Q_{n}\right)$
and $W_{\tau }\left(Q_{n}\right)\geq \frac{\left(n+1\right)
(n+2)}{2}$ for any $n\in\mathbf{N}$.\\
\end{center}

Moreover, for the $n$-dimensional cube $Q_{n}$, we show that if
$w_{\tau }\left(Q_{n}\right) \leq t\leq \frac{\left(
n+1\right)(n+2)}{2}$, then $Q_{n}$ admits an interval total
$t$-coloring.

\textbf{Theorem 8.} If $G$ is a $(2,b)$-biregular bipartite graph
with $b\geq 3$, then $G\in \mathfrak{T}$ and $b+1\leq w_{\tau
}\left(G\right)\leq b+2$.

Finally, we show that there are bipartite graphs which have no
interval total coloring. The smallest known bipartite graph with 26
vertices and maximum degree 18 that is not interval total colorable
was obtained by A. Shashikyan.


\begin{thebibliography}{00}

\bibitem{b1} A.S. Asratian, R.R. Kamalian, Interval colorings of edges of a
multigraph, Appl. Math. 5 (1987) 25-34 (in Russian).

\bibitem{b2} A.S. Asratian, R.R. Kamalian, Investigation on interval
edge-colorings of graphs, J. Combin. Theory Ser. B 62 (1994) 34-43.

\bibitem{b3} M. Behzad, Graphs and their chromatic numbers, Ph.D. thesis,
Michigan State University, 1965.

\bibitem{b4} O.V. Borodin, A.V. Kostochka, D.R. Woodall, Total colorings of
planar graphs with large maximum degree, J. Graph Theory 26 (1997)
53-59.

\bibitem{b5} T.R. Jensen, B. Toft, Graph coloring problems, Wiley
Interscience Series in Discrete Mathematics and Optimization, 1995.

\bibitem{b6} A.V. Kostochka, The total coloring of a multigraphs with
maximal degree 5 is at most seven, Discrete Mathematics 162 (1996)
199-214.

\bibitem{b7} L. Kowalik, J.-S. Sereni, R. Skrekovski,
Total-colouring of plane graphs with maximum degree nine, SIAM J.
Discrete Math. 22 (2008) 1462-1479.

\bibitem{b8} M. Molloy, B. Reed, A bound on the total chromatic
number, Combinatorica 18 (1998) 241-280.

\bibitem{b9} P.A. Petrosyan, Interval total colorings of complete bipartite
graphs, Proceedings of the CSIT Conference (2007) 84-85.

\bibitem{b10} P.A. Petrosyan, Interval total colorings of certain graphs,
Mathematical Problems of Computer Science 31 (2008) 122-129.

\bibitem{b11} M. Rosenfeld, On the total coloring of certain graphs, Israel
J. Math. 9 (1971) 396-402.

\bibitem{b12} A. Sanchez-Arroyo, Determining the total colouring number is $NP$-hard,
Discrete Mathematics 78 (1989) 315-319.

\bibitem{b13} D.P. Sanders, Y. Zhao, On total 9-coloring planar graphs of
maximum degree seven, J. Graph Theory 31 (1999) 67-73.

\bibitem{b14} N. Vijayaditya, On the total chromatic number of a graph, J.
London Math. Soc. (2) 3 (1971) 405-408.

\bibitem{b15} V.G. Vizing, Chromatic index of multigraphs,
Doctoral Thesis, Novosibirsk, 1965 (in Russian).

\bibitem{b16} W. Wang, Total chromatic number of planar graphs with maximum degree
ten, J. Graph Theory 54 (2006) 91-102.

\bibitem{b17} H.P. Yap, Total colorings of graphs, Lecture Notes in
Mathematics 1623, Springer-Verlag, Berlin, 1996.

\bibitem{b18} Z. Zhang, J. Zhand, J. Wang, The total chromatic numbers of
some graphs, Scientia Sinica A 31 (1988) 1434-1441.

\end{thebibliography}

\end{document}
