Monotone Chromatic Number of Graphs

Main Article Content

Anwar Saleh, Najat Muthana, Wafa Al-Shammakh, Hanaa Alashwali


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.

Article Details


  1. D.M. Cardoso, J.O. Cerdeira, J.P. Cruz, C. Dominic, Injective Edge Chromatic Index of a Graph, ArXiv:1510.02626 [Math]. (2015).
  2. J.L. Fouquet , J.L. Jolivet, Strong edge-colorings of graphs and applications to multi k -gons, Ars Combin. 16A (1983), 141-150.
  3. F. Guthrie. Note on the colouring of maps. Proc. R. Soc. Edinburgh. 10 (1880), 727-728.
  4. I. Gutman, Kragujevac trees and their energy, Sci. Publ. State Univ. Novi Pazar Ser. A., Appl. Math. Inform. Mech. 6 (2) (2014), 71-79.
  5. G. Hahn, J. Kratochv ´il, J. ˘sir ´an˘ and D. Sotteau, On the injective chromatic number of graphs. Discrete Math. 256 (2002), 179-192.
  6. F. Harary, Graph theory, Addison-Wesley, Reading Mass. (1969).
  7. J.X. Li, J.M. Guo, W.C. Shiu, On the second largest Laplacian eigenvalues of graphs, Linear Algebra Appl. 438 (2013), 2438-2446.
  8. N. Zufferey, P. Amstutz, P. Giaccari, Graph colouring approaches for a satellite range scheduling problem, J. Schedul. 11 (4) (2008), 263-277.