Interval colorings of edges of a multigraph

A. S. Asratian; R. R. Kamalian

paper

Interval colorings of edges of a multigraph

arXiv:1401.8079

Abstract

Let $G = (V_{1} (G), V_{2} (G), E (G))$ be a bipartite multigraph, and $R \subseteq V_{1} (G) \cup V_{2} (G)$ . A proper coloring of edges of $G$ with the colors $1, \dots, t$ is called interval (respectively, continuous) on $R$ , if each color is used for at least one edge and the edges incident with each vertex $x \in R$ are colored by $d (x)$ consecutive colors (respectively, by the colors $1, \dots, d (x))$ , where $d (x)$ is a degree of the vertex $x$ . We denote by $w_{1} (G)$ and $W_{1} (G)$ , respectively, the least and the greatest values of $t$ , for which there exists an interval on $V_{1} (G)$ coloring of the multigraph $G$ with the colors $1, \dots, t$ . In the paper the following basic results are obtained. \textbf{Theorem 2.} For an arbitrary $k$ , $w_{1} (G) \leq k \leq W_{1} (G)$ , there is an interval on $V_{1} (G)$ coloring of the multigraph $G$ with the colors $1, \dots, k$ . \textbf{Theorem 3.} The problem of recognition of the existence of a continuous on $V_{1} (G)$ coloring of the multigraph $G$ is $N P$ -complete. \textbf{Theorem 4.} If for any edge $(x, y) \in E (G)$ , where $x \in V_{1} (G)$ , the inequality $d (x) \geq d (y)$ holds then there is a continuous on $V_{1} (G)$ coloring of the multigraph $G$ . \textbf{Theorem 1.} If $G$ has no multiple edges and triangles, and there is an interval on $V (G)$ coloring of the graph $G$ with the colors $1, \dots, k$ , then $k \leq ∣ V (G) ∣ - 1$ .

References in corpus (1)

Interval colorings of complete bipartite graphs and trees

Interval colorings of edges of a multigraph

Abstract

References in corpus (1)

Cited by in corpus (11)