On one-sided interval edge colorings of biregular bipartite graphs

Rafayel Ruben Kamalian

Algebra and discrete mathematics, Tome 19 (2015) no. 2, pp. 193-199

Résumé

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.

Détail

Keywords: proper edge coloring, interval edge coloring, interval spectrum, biregular bipartite graph.