Some New Graph Coloring Problems

Graph coloring involves assignment of colors, labels, or weights to the elements of a given graph. A color class of the graph includes a set of its vertices having the same color. A rainbow neighbourhood in the graph includes the closed neighbourhood of a vertex which consists of at least a vertex from every color class. This chapter discusses some new types of graph coloring based on the rainbow neighbourhoods in the graph concerned and related results. It also discusses some new graph coloring protocols, which have many practical applications, especially in connectivity and optimisation problems. Graph coloring can be considered as an assignment of colors to the elements of graphs under consideration. The chapter reviews a wheel graph, double wheel graph, helm graph, closed helm, flower graph and a web graph. It illustrates rainbow neighbourhood number of some graph transformations and graph products along with the paucity number of graphs.