Monotone Chromatic Number of Graphs

Abstract

For a graph G = (V, E), a vertex coloring (or, simply, a coloring) of G is a function C: V (G) → {1, 2, ..., k} (using the non-negative integers {1, 2, ..., k} as colors). In this research work, we introduce a new type of graph coloring called monotone coloring, along with this new coloring, we define the monotone chromatic number of a graph and establish some related new graphs. Basic properties and exact values of the monotone chromatic number of some graph families, like standard graphs, Kragujevac trees and firefly graph are obtained. Also, we get a characterization for bipartite graphs by defining the monotone bipartite graph. Exact values of the monotone chromatic number for some special case of Cartesian product of graphs are found. Finally, upper and lower bounds for monotone chromatic number of the Cartesian product for non trivial connected graphs are presented.