RO  EN
IMI/Publicaţii/BASM/Ediţii/BASM n.3 (76), 2014/

Estimates for the number of vertices with an interval spectrum in proper edge colorings of some graphs

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

Adobe PDF document – 0.14 Mb