|
Algebra and Discrete Mathematics, 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.
Поступила в редакцию: 17.12.2012 Исправленный вариант: 10.02.2015
Образец цитирования:
Rafayel Ruben Kamalian, “On one-sided interval edge colorings of biregular bipartite graphs”, Algebra Discrete Math., 19:2 (2015), 193–199
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/adm516 https://www.mathnet.ru/rus/adm/v19/i2/p193
|
|