**Authors:** R. R. Kamalian

### Abstract

For an undirected, simple, finite, connected graph $G$, we
denote by $V(G)$ and $E(G)$ the sets of its vertices and edges,
respectively. A function $\varphi:E(G)\rightarrow\{1,2,\ldots,t\}$
is called a proper edge $t$-coloring of a graph $G$ if all colors
are used and no two adjacent edges receive the same color. An
arbitrary nonempty subset of consecutive integers is called an
interval. The set of all proper edge $t$-colorings of $G$ is denoted
by $\alpha(G,t).$ The minimum value of $t$ for which there exists a
proper edge $t$-coloring of a graph $G$ is denoted by $\chi'(G).$
Let
$$\alpha(G)\equiv \bigcup_{t=\chi'(G)}^{|E(G)|}\alpha(G,t).$$
If $G$ is a graph, $\varphi\in\alpha(G)$, $x\in V(G)$, then the set
of colors of edges of $G$ incident with $x$ is called a spectrum of
the vertex $x$ in the coloring $\varphi$ of the graph $G$ and is
denoted by $S_G(x,\varphi).$ If $\varphi\in\alpha(G)$ and $x\in
V(G)$, then we say that $\varphi$ is interval (persistent-interval)
for $x$ if $S_G(x,\varphi)$ is an interval (an interval with $1$ as
its minimum element). For an arbitrary graph $G$ and any
$\varphi\in\alpha(G)$, we denote by
$f_{G,i}(\varphi)(f_{G,pi}(\varphi))$ the number of vertices of the
graph $G$ for which $\varphi$ is interval (persistent-interval). For
any graph $G$, let us set
$$\eta_i(G)\equiv \max_{\varphi\in\alpha(G)}f_{G,i}(\varphi),\quad
\eta_{pi}(G)\equiv \max_{\varphi\in\alpha(G)}f_{G,pi}(\varphi).$$
For graphs $G$ from some classes of graphs, we obtain lower bounds
for the parameters $\eta_i(G)$ and $\eta_{pi}(G).$

Institute for Informatics and Automation Problems

National Academy of Sciences of RA

0014 Yerevan, Republic of Armenia

E-mail:

### Fulltext

–

0.14 Mb