|
|
Algebra and Discrete Mathematics, 2015, Volume 19, Issue 2, Pages 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
Abstract:
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.
Keywords:
proper edge coloring, interval edge coloring, interval spectrum, biregular bipartite graph.
Received: 17.12.2012 Revised: 10.02.2015
Citation:
Rafayel Ruben Kamalian, “On one-sided interval edge colorings of biregular bipartite graphs”, Algebra Discrete Math., 19:2 (2015), 193–199
Linking options:
https://www.mathnet.ru/eng/adm516 https://www.mathnet.ru/eng/adm/v19/i2/p193
|
|