RO  EN
IMI/Publicaţii/BASM/Ediţii/BASM n.1(89), 2019/

Examples of bipartite graphs which are not cyclically-interval colorable

Authors: R.R. Kamalian

Abstract

A proper edge $t$-coloring of an undirected, simple, finite, connected graph $G$ is a coloring of its edges with colors $1,2,...,t$ such that all colors are used, and no two adjacent edges receive the same color. A cyclically-interval $t$-coloring of a graph $G$ is a proper edge $t$-coloring of $G$ such that for each its vertex $x$ at least one of the following two conditions holds: a) the set of colors used on edges incident to $x$ is an interval of integers, b) the set of colors not used on edges incident to $x$ is an interval of integers. %A cyclically-interval $t$-coloring of a graph $G$ is a proper edge $t$-coloring of $G$ such that for each its vertex %$x$ at least one of the following two statements is true: a) the set of colors used on edges incident to $x$ forms %an interval of integers, b) the set of colors not used on edges incident to $x$ forms an interval of integers. For any positive integer $t$, let $\mathfrak{M}_t$ be the set of graphs for which there exists a cyclically-interval $t$-coloring. Examples of bipartite graphs that do not belong to the class $\bigcup\limits_{t\geq 1}\mathfrak{M}_t$ are constructed.

European University
10 Davit Anhaght str., 0037, Yerevan
Republic of Armenia
E-mail:



Fulltext

Adobe PDF document – 0.09 Mb