RUS  ENG
Полная версия
ЖУРНАЛЫ // Algebra and Discrete Mathematics // Архив

Algebra Discrete Math., 2015, том 19, выпуск 2, страницы 193–199 (Mi adm516)

RESEARCH ARTICLE

On one-sided interval edge colorings of biregular bipartite graphs

Rafayel Ruben Kamalian

Institute for Informatics and Automation Problems of National Academy of Science of the Republic of Armenia

Аннотация: A proper edge $t$-coloring of a graph $G$ is a coloring of edges of $G$ with colors $1,2,\ldots,t$ such that all colors are used, and no two adjacent edges receive the same color. The set of colors of edges incident with a vertex $x$ is called a spectrum of $x$. Any nonempty subset of consecutive integers is called an interval. A proper edge $t$-coloring of a graph $G$ is interval in the vertex $x$ if the spectrum of $x$ is an interval. A proper edge $t$-coloring $\varphi$ of a graph $G$ is interval on a subset $R_0$ of vertices of $G$, if for any $x\in R_0$, $\varphi$ is interval in $x$. A subset $R$ of vertices of $G$ has an $i$-property if there is a proper edge $t$-coloring of $G$ which is interval on $R$. If $G$ is a graph, and a subset $R$ of its vertices has an $i$-property, then the minimum value of $t$ for which there is a proper edge $t$-coloring of $G$ interval on $R$ is denoted by $w_R(G)$. We estimate the value of this parameter for biregular bipartite graphs in the case when $R$ is one of the sides of a bipartition of the graph.

Ключевые слова: proper edge coloring, interval edge coloring, interval spectrum, biregular bipartite graph.

MSC: 05C15, 05C50, 05C85

Поступила в редакцию: 17.12.2012
Исправленный вариант: 10.02.2015

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



Реферативные базы данных:


© МИАН, 2024