R.R. KamalianExamples of cyclically-interval non-colorable bipartite graphs
cyclically-interval edge coloring, bipartite graph 05C15 For an undirected,
simple, finite, connected graph $G$, we denote by $V(G)$ and $E(G)$ the sets
of its vertices and edges, respectively. A function
$\varphi:E(G)\rightarrow\\{1,2,\ldots,t\\}$ is called a proper edge
$t$-coloring of a graph $G$ if adjacent edges are colored differently and each
of $t$ colors is used. An arbitrary nonempty subset of consecutive integers is
called an interval. If $\varphi$ is a proper edge $t$-coloring of a graph $G$
and $x\in V(G)$, then $S_{G}(x,\varphi)$ denotes the set of colors of edges of
$G$ which are incident with $x$. A proper edge $t$-coloring $\varphi$ of a
graph $G$ is called a cyclically-interval $t$-coloring if for any $x\in V(G)$
at least one of the following two conditions holds: a) $S_{G}(x,\varphi)$ is
an interval, b) $\\{1,2,\ldots,t\\}\setminus S_{G}(x,\varphi)$ is an interval.
For any $t\in\mathbb{N}$, let $\mathfrak{M}_{t}$ be the set of graphs for
which there exists a cyclically-interval $t$-coloring, and let

$\mathfrak{M}\equiv\bigcup_{t\geq 1}\mathfrak{M}_{t}.$

Examples of bipartite graphs that do not belong to the class $\mathfrak{M}$
are constructed. R.R. Kamalian 2013 R.R. Kamalian
Institute for Informatics and Automation Problems National Academy of Sciences
of RA, 0014 Yerevan, Republic of Armenia
E-mail<EMAIL_ADDRESS>
# Examples of cyclically-interval non-colorable bipartite graphs

R.R. Kamalian

##  1 Introduction

We consider undirected, simple, finite, and connected graphs. For a graph $G$
we denote by $V(G)$ and $E(G)$ the sets of its vertices and edges,
respectively. For a graph $G$, we denote by $\Delta(G)$ and $\chi^{\prime}(G)$
the maximum degree of a vertex of $G$ and the chromatic index of $G$ [14],
respectively. The terms and concepts which are not defined can be found in
[17].

For an arbitrary finite set $A$, we denote by $|A|$ the number of elements of
$A$. The set of positive integers is denoted by $\mathbb{N}$. An arbitrary
nonempty subset of consecutive integers is called an interval. An interval
with the minimum element $p$ and the maximum element $q$ is denoted by
$[p,q]$.

For any $t\in\mathbb{N}$ and arbitrary integers $i_{1},i_{2}$ satisfying the
conditions $i_{1}\in[1,t]$, $i_{2}\in[1,t]$, we define [8, 9] the sets
$intcyc_{1}[(i_{1},i_{2}),t],$ $intcyc_{1}((i_{1},i_{2}),t),$
$intcyc_{2}((i_{1},i_{2}),t),$ $intcyc_{2}[(i_{1},i_{2}),t]$ as follows:

$intcyc_{1}[(i_{1},i_{2}),t]\equiv[\min\\{i_{1},i_{2}\\},\max\\{i_{1},i_{2}\\}],$
$intcyc_{1}((i_{1},i_{2}),t)\equiv
intcyc_{1}[(i_{1},i_{2}),t]\backslash(\\{i_{1}\\}\cup\\{i_{2}\\}),$
$intcyc_{2}((i_{1},i_{2}),t)\equiv[1,t]\backslash
intcyc_{1}[(i_{1},i_{2}),t],$
$intcyc_{2}[(i_{1},i_{2}),t]\equiv[1,t]\backslash
intcyc_{1}((i_{1},i_{2}),t).$

If $t\in\mathbb{N}$ and $Q$ is a non-empty subset of the set $\mathbb{N}$,
then $Q$ is called a $t$-cyclic interval if there exist integers
$i_{1},i_{2},j_{0}$ satisfying the conditions $i_{1}\in[1,t]$,
$i_{2}\in[1,t]$, $j_{0}\in\\{1,2\\}$, $Q=intcyc_{j_{0}}[(i_{1},i_{2}),t]$.

A function $\varphi:E(G)\rightarrow[1,t]$ is called a proper edge $t$-coloring
of a graph $G$ if adjacent edges are colored differently and each of $t$
colors is used.

For a graph $G$ and a positive integer $t$, where $\chi^{\prime}(G)\leq
t\leq|E(G)|$, we denote by $\alpha(G,t)$ the set of all proper edge
$t$-colorings of $G$. Let us set

$\alpha(G)\equiv\bigcup_{t=\chi^{\prime}(G)}^{|E(G)|}\alpha(G,t).$

If $G$ is a graph, $\varphi\in\alpha(G)$, and $x\in V(G)$, then the set
$\\{\varphi(e)/e\in E(G),e\textrm{ is incident with }x\\}$ is denoted by
$S_{G}(x,\varphi)$.

A proper edge $t$-coloring $\varphi$ of a graph $G$ is called a cyclically-
interval $t$-coloring of $G$, if for any $x\in V(G)$ at least one of the
following two conditions holds: a) $S_{G}(x,\varphi)$ is an interval, b)
$[1,t]\setminus S_{G}(x,\varphi)$ is an interval.

For any $t\in\mathbb{N}$, we denote by $\mathfrak{M}_{t}$ the set of graphs
for which there exists a cyclically-interval $t$-coloring. Let

$\mathfrak{M}\equiv\bigcup_{t\geq 1}\mathfrak{M}_{t}.$

For an arbitrary tree $D$, it was shown in [8, 9] that $D\in\mathfrak{M}$,
and, moreover, all possible values of $t$ were found for which
$D\in\mathfrak{M}_{t}$. For an arbitrary simple cycle $C$, it was shown in [7,
10] that $C\in\mathfrak{M}$, and, moreover, all possible values of $t$ were
found for which $C\in\mathfrak{M}_{t}$. Some interesting results on this and
related topics were obtained in [1, 3, 4, 15, 16, 11, 12, 13, 2, 5, 6].

In this paper, the examples of bipartite graphs that do not belong to the
class $\mathfrak{M}$ are constructed.

For any integer $m\geq 2$, set:

$V_{0,m}\equiv\\{x_{0}\\},\qquad V_{1,m}\equiv\\{x_{i,j}/\;1\leq i<j\leq
m\\},$ $V_{2,m}\equiv\\{y_{p,q}/\;1\leq p\leq m,1\leq q\leq m\\},$
$E^{\prime}_{m}\equiv\\{(x_{0},y_{p,q})/\;1\leq p\leq m,1\leq q\leq m\\}.$

For any integers $i,j,m$ satisfying the inequalities $m\geq 2$, $1\leq i<j\leq
m$, set:

$E^{\prime\prime}_{i,j,m}\equiv\\{(x_{i,j},y_{i,q})/\;1\leq q\leq
m\\}\cup\\{(x_{i,j},y_{j,q})/\;1\leq q\leq m\\}.$

For any integer $m\geq 2$, let us define a graph $G(m)$ by the following way:

$G(m)\equiv\Bigg{(}\bigcup_{k=0}^{2}V_{k,m},E^{\prime}_{m}\cup\Bigg{(}\bigcup_{1\leq
i<j\leq m}E^{\prime\prime}_{i,j,m}\Bigg{)}\Bigg{)}.$

It is not difficult to see that for any integer $m\geq 2$, $G(m)$ is a
bipartite graph with $\Delta(G(m))=\chi^{\prime}(G(m))=m^{2}$,
$|V(G(m))|=\frac{3m^{2}-m}{2}+1$, $|E(G(m))|=m^{3}$.

######  Theorem 1.

For any integer $m\geq 8$, $G(m)\not\in\mathfrak{M}$.

######  Proof 1.1.

Assume the contrary. It means that there exist integers $m_{0},t_{0},k_{0}$,
satisfying the conditions $m_{0}\geq 8$, $m_{0}^{2}\leq t_{0}\leq m_{0}^{3}$,
$t_{0}=m_{0}^{2}+k_{0}$, $0\leq k_{0}\leq m_{0}^{3}-m_{0}^{2}$,
$G(m_{0})\in\mathfrak{M}_{t_{0}}$.

Let $\varphi_{0}$ be a cyclically-interval $t_{0}$-coloring of the graph
$G(m_{0})$. Without loss of generality, we can suppose that
$S_{G(m_{0})}(x_{0},\varphi_{0})=[1,m_{0}^{2}]$. Let us consider the edges
$e^{\prime}$ and $e^{\prime\prime}$ of the graph $G(m_{0})$, which are
incident with the vertex $x_{0}$ and satisfy the equalities
$\varphi_{0}(e^{\prime})=1$,
$\varphi_{0}(e^{\prime\prime})=\lfloor\frac{m_{0}^{2}}{2}\rfloor$.

Suppose that $e^{\prime}=(x_{0},y^{\prime})$,
$e^{\prime\prime}=(x_{0},y^{\prime\prime})$. Clearly, there exists a vertex
$\widetilde{x}\in V_{1,m_{0}}$ in the graph $G(m_{0})$ which is adjacent to
the vertices $y^{\prime}$ and $y^{\prime\prime}$. It is not difficult to see
that $S_{G(m_{0})}(y^{\prime},\varphi_{0})\cup
S_{G(m_{0})}(\widetilde{x},\varphi_{0})\cup
S_{G(m_{0})}(y^{\prime\prime},\varphi_{0})$ is a $t_{0}$-cyclic interval.

Clearly, the inequalities $m_{0}^{2}+k_{0}-4m_{0}+4>4m_{0}-2$ and
$4m_{0}-1\leq\lfloor\frac{m_{0}^{2}}{2}\rfloor\leq m_{0}^{2}+k_{0}-4m_{0}+3$
are true. Consequently, $\lfloor\frac{m_{0}^{2}}{2}\rfloor\in
intcyc_{1}((4m_{0}-2,m_{0}^{2}+k_{0}-4m_{0}+4),m_{0}^{2}+k_{0})$. But it is
incompatible with the evident relations $\lfloor\frac{m_{0}^{2}}{2}\rfloor\in
S_{G(m_{0})}(y^{\prime\prime},\varphi_{0})$ and
$S_{G(m_{0})}(y^{\prime},\varphi_{0})\cup
S_{G(m_{0})}(\widetilde{x},\varphi_{0})\cup
S_{G(m_{0})}(y^{\prime\prime},\varphi_{0})\subseteq
intcyc_{2}[(4m_{0}-2,m_{0}^{2}+k_{0}-4m_{0}+4),m_{0}^{2}+k_{0}]$.
Contradiction.

The author thanks P.A. Petrosyan for his attention to this work.

## References

  * [1] Altinakar S., Caporossi G., Hertz A. On compact $k$-edge-colorings: A polynomial time reduction from linear to cyclic. Discrete Optimization 8(2011), 502–512.
  * [2] Asratian A.S. Investigation of some mathematical model of scheduling theory. Doctoral Thesis, Moscow, 1980 (in Russian).
  * [3] Bartholdi J.J., Orlin J.B., Ratliff H.D. Cyclic scheduling via integer programs with circular ones. Operations Research 28, 1980, 1074–1085.
  * [4] Dauscha W., Modrow H.D., Neumann A. On cyclic sequence type for constructing cyclic schedules. Zeitschrift für Operations Research 29, 1985, 1–30.
  * [5] Jensen T.R., Toft B. Graph Coloring Problems. Wiley Interscience Series in Discrete Mathematics and Optimization, 1995.
  * [6] Kamalian R.R. Interval Edge Colorings of Graphs. Doctoral dissertation. The Institute of Mathematics of the Siberian Branch of the Academy of Sciences of USSR, Novosibirsk, 1990 (in Russian).
  * [7] Kamalian R.R. On cyclically continuous edge colorings of simple cycles. Proceedings of the CSIT Conference, Yerevan, 2007, 79–80 (in Russian).
  * [8] Kamalian R.R. On a number of colors in cyclically interval edge colorings of trees. Research report LiTH-MAT-R-2010/09-SE, Linköping University, 2010.
  * [9] Kamalian R.R. On cyclically-interval edge colorings of trees. Buletinul of Academy of Sciences of the Republic of Moldova, Matematica 1(68), 2012, 50–58.
  * [10] Kamalian R.R. On a number of colors in cyclically-interval edge-colorings of simple cycles. Open Journal of Discrete Mathematics, 3(2013), 43–48.
  * [11] Kubale M. Graph Colorings. American Mathematical Society, 2004.
  * [12] Kubale M., Nadolski A. Chromatic scheduling in a cyclic open shop. European Journal of Operational Research 164(2005), 585–591.
  * [13] Nadolski A. Compact cyclic edge-colorings of graphs. Discrete Mathematics 308(2008), 2407–2417.
  * [14] Vizing V.G. The chromatic index of a multigraph. Kibernetika 3 (1965), 29–39.
  * [15] de Werra D., Mahadev N.V.R., Solot Ph. Periodic compact scheduling. ORWP 89/18, Ecole Polytechnique Fédérale de Lausanne, 1989.
  * [16] de Werra D., Solot Ph. Compact cylindrical chromatic scheduling. ORWP 89/10, Ecole Polytechnique Fédérale de Lausanne, 1989.
  * [17] West D.B. Introduction to Graph Theory. Prentice-Hall, New Jersey, 1996.