Examples of bipartite graphs which are not cyclically-interval colorable

R. R. Kamalian

European University, 10 Davit Anhaght str., 0037, Yerevan, Republic of Armenia

Аннотация: 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. 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.

Ключевые слова и фразы: cyclically-interval $t$-coloring, bipartite graph.

MSC: 05C15

Поступила в редакцию: 11.12.2017

Язык публикации: английский