2018/10/29 by Eunice Mphako-Banda, Mphako-Banda, Eunice, Johan Kok +1
Computer Science · #05C15 #05C38 #05C75 #05C85 #Advanced Graph Theory Research #FOS: Mathematics #General Mathematics (math.GM) #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1810.13328
openalex publication_date 2018/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In an improper colouring 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 ζ(G), is the maximum number of edges over all chromatic colourings that can be added to G without adding a bad edge. We introduce stability of a graph in respect of chromatic completion. We prove that the set of chromatic completion edges denoted by Eχ(G), which corresponds to ζ(G) is unique if and only if G is stable in respect of chromatic completion. Thereafter, chromatic completion and stability is discussed in respect of Johan colouring. The difficulty of studying chromatic completion with regards to graph operations is shown by presenting results for two elementary graph operations.