Stability in respect of chromatic completion of graphs
Eunice Mphako-Banda, Johan Kok · Open Journal of Discrete Applied Mathematics · 2022
In an improper coloring, an edge \(uv\) for which, \(c(u)=c(v)\) is called a bad edge. The notion of the chromatic completion number of a graph \(G\) denoted by \(\zeta(G),\) is the maximum number of edges over all chromatic colorings that can be added to \(G\) without adding a bad edge. We introduce the stability of a graph in respect of chromatic completion. We prove that the set of chromatic completion edges denoted by \(E_\chi(G),\) which corresponds to \(\zeta(G)\) is unique if and only if \(G\) is stable in respect of chromatic completion. After that, chromatic completion and stability regarding Johan coloring are discussed. The difficulty of studying chromatic completion of graph operations is shown by presenting results for two elementary graph operations.