Eternal chromatic number (Q2878221)

A vertex \(k\)-coloring of a graph \(G = (V, E)\) is a function \(c : V \to I_k\) where \(I_k = \{1, 2, \ldots, k \}\). A \(k\)-coloring \(c\) is proper when for any edge \(xy \in E\), \(c(x) \neq c(y)\). The color classes of a \(k\)-coloring \(c\) are denoted by \(c_i\) where \(c_i\) is the set of all vertices which are assigned the color \(i\). Given a \(k\)-coloring \(c\) of a graph \(G\), a set \(A\) of vertices of \(G\) is called a transversal of \(c\) when for all \(i\), \(a \leq i \leq k\), \(A \cap c_i \neq \phi\). Given a \(k\)-coloring \(c\) of \(G\), let \(S_c = \{v \in V(G): N[v]\, \text{is a transversal of}\, c \}\). A \(k\)-coloring \(c\) is called a transversal coloring when \(S_c\) is a transversal of \(c\). Otherwise, \(c\) is a nontransversal coloring.NEWLINENEWLINENEWLINEThe following theorem is proved.NEWLINENEWLINELet \(c\) be a \(k\)-coloring of a graph \(G\). If \(S_c\) is not a transversal of \(c\), then there is a \((k - 1)\)-coloring of \(G\). However, the converse does not hold.NEWLINENEWLINENEWLINEGiven a \(k\)-coloring \(c\) of a graph \(G\), a defense to an attack on a vertex \(v\) is a \(k\)-coloring \(c^\prime\) such that \(c^{\prime}(v) \neq c(v)\) and for all \(w \notin N[v]\), \(c^{\prime} (w) = c(w)\). A vertex \(v\), with respect to a \(k\)-coloring \(c\), is said to be defendable, if there is a defense to an attack on \(v\). A \(k\)-coloring \(c\) is \textit{secure} when every vertex is defendable. Let \(\chi_{s}(G)\) be the smallest integer \(k\) for which there is a secure \(k\)-coloring of \(G\).NEWLINENEWLINENEWLINEThe following result is proved.NEWLINENEWLINENEWLINESuppose \(c\) is a nontransversal \(k\)-coloring of a graph \(G\) with \(c_j \cap S_c = \emptyset\), for some \(a \leq j \leq k\). For each vertex \(x \in c_j\), let \(i_x\) be a color with \(N[x] \cap c_{i_x} = \emptyset\). A defense to an attack on a vertex \(v\) of \(G\) is given by NEWLINE\[NEWLINE c^{\prime}(x)= \begin{cases} j, \quad & \text{if }x = v \text{ and } v \notin c_j\\ i_x, \quad & \text{if } x \in c_j \cap N[v]\\ c(x)\quad & \text{otherwise}. \end{cases}NEWLINE\]NEWLINE Let \(c\) be a \(k\)-coloring of a graph \(G\) and let \(v\) be a vertex in \(G\). We define, for each vertex \(w\) in \(G\), a subset of \(I_k = \{1, 2, \dots, k\}\) as follows. NEWLINE\[NEWLINE L_v(w) = \begin{cases} I_k - \{c(w)\} \quad & \text{if}\,\, w = v\\ I_k - \{c (u) : u \in N[w] - N[v] \}\quad & \text{if}\,\, w \in N(v)\\ \{c(w)\} \quad & \text{otherwise}. \end{cases}NEWLINE\]NEWLINENEWLINE The following characterizations are proved.NEWLINENEWLINESuppose \(c\) is a \(k\)-coloring of a graph \(G\). A vertex \(v\) is defendable if and only if there is a \(k\)-coloring \(c^{\prime}\) such that \(c^{\prime}(w) \in L_v(w)\) for every vertex \(w \in G\).NEWLINENEWLINEA proper \(k\)-coloring \(c\) of a graph \(G\) is secure if and only if for each \(v \in G\) there is a proper \(k\)-coloring \(c^{\prime}\) with \(c^{\prime}(w) \in L_v(w)\) for every vertex \(w \in G\).NEWLINENEWLINEIf \(G\) is a triangle free graph with \(n\) vertices there is an \(O(n^3)\) algorithm for determining whether or not an arbitrary \(k\)-coloring \(c\) is secure.NEWLINENEWLINEGiven a graph \(G\), a collection \(\mathcal{K}\) of \(k\)-colorings of \(G\) is said to be closed when, for every \(k\)-coloring \(c\) in \(\mathcal{K}\) and every vertex \(v\) in \(G\), there is a defense \(c^{\prime}\) in \(\mathcal{K}\) to an attack on \(v\).NEWLINENEWLINEA \(k\)-coloring \(c\) is an eternal \(k\)-coloring when \(c\) is an element of a closed set \(\mathcal{K}\) of \(k\)-colorings. A \(k\)-coloring that is not eternal is said to be a mortal \(k\)-coloring. \(\chi^{\infty} (G)\) is the smallest integer \(k\) for which there is an eternal \(k\)-coloring.NEWLINENEWLINENEWLINEFor any graph \(G\), every nontransversal \(k\)-coloring is eternal.NEWLINENEWLINENEWLINEFor any graph \(G\), \(\chi^{\infty} (G) = \chi(G)\) if and only if every \(\chi^{\infty} (G)\)-coloring is a transversal coloring.NEWLINENEWLINENEWLINEAn algorithm is given to produce an eternal \(k\)-coloring. It is also shown that eternal coloring problem is NP-hard.NEWLINENEWLINENEWLINEGiven a graph \(G\), \(M(G)\) is defined as the smallest integer such that for all \(k > M(G)\) every \(k\)-coloring is eternal.NEWLINENEWLINENEWLINEFor a graph \(G\) and a nonincreasing degree sequence labeling \(v_1, \dots, v_n\), let NEWLINE\[NEWLINEs(G) = \begin{cases} 1, &\text{if}\,\, \Delta(G) \leq 1; \\ \{i: \mathrm{deg}(v_{i -1})\leq i\, \text{ and }\mathrm{deg}(v_i)\geq i - 1 \} , &\text{if}\,\, \Delta(G) \geq 2. \end{cases} NEWLINE\]NEWLINE For any graph \(G\) with at least one edge, \(M(G) \leq s(G) \leq \Delta(G)\) and these bounds are tight.NEWLINENEWLINEThe following characterization is proved.NEWLINENEWLINEEvery \(k\)-coloring of a tree \(T\) is eternal if an only if every vertex in \(T\) has at most \(k - 2\) neighbours with degree \(k\) or more.