|
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, 2014, Number 3, Pages 3–12
(Mi basm374)
|
|
|
|
Estimates for the number of vertices with an interval spectrum in proper edge colorings of some graphs
R. R. Kamalian Institute for Informatics and Automation Problems, National Academy of Sciences of RA, 0014 Yerevan, Republic of Armenia
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\colon E(G)\to\{1,2,\dots,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)$.
Keywords and phrases:
proper edge coloring, interval spectrum.
Received: 30.04.2013
Citation:
R. R. Kamalian, “Estimates for the number of vertices with an interval spectrum in proper edge colorings of some graphs”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2014, no. 3, 3–12
Linking options:
https://www.mathnet.ru/eng/basm374 https://www.mathnet.ru/eng/basm/y2014/i3/p3
|
|