RUS  ENG
Полная версия
ЖУРНАЛЫ // Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica // Архив

Bul. Acad. Ştiinţe Repub. Mold. Mat., 2014, номер 3, страницы 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

Аннотация: 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)$.

Ключевые слова и фразы: proper edge coloring, interval spectrum.

MSC: 05C15

Поступила в редакцию: 30.04.2013

Язык публикации: английский



© МИАН, 2024