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

R. R. Kamalian

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 3 (2014), pp. 3-12

Résumé

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)$.