Rainbow neighbourhood number of graphs





Colour cluster, Colour classes, Rainbow neighbourhood, Expanded line graph, v-clique


In this paper, we introduce the notion of the rainbow neighbourhood and a related graph parameter namely the rainbow neighbourhood number and report on preliminary results thereof. The closed neighbourhood N [v] of a vertex v ∈ V (G) which contains at least one coloured vertex of each colour in the chromatic colouring of a graph is called a rainbow neighbourhood. The number of rainbow neighbourhoods in a graph G is called the rainbow neighbourhood number of G, denoted by rχ(G). We also introduce the concepts of an expanded line graph of a graph G and a v-clique of v ∈ V (G). With the help of these new concepts, we also establish a necessary and sufficient condition for the existence of a rainbow neighbourhood in the line graph of a graph G.

Author Biographies

Johan Kok, CHRIST (Deemed to be University).

Department of Mathematics.

Sudev Naduvath, CHRIST (Deemed to be University).

Department of Mathematics.

Muhammad Kamran Jamil, Riphah International University.

Department of Mathematics, Riphah Institute of Computing and Applied Sciences.


B. Andrásfai, P. Erdös, and V. Sós, “On the connection between chromatic number, maximal clique and minimal degree of a graph”, Discrete Mathematics, vol. 8, no. 3, pp. 205–218, May 1974, doi: 10.1016/0012-365X(74)90133-2.

J. Bondy and U. Murty, Graph theory, Elsevier Science: New York, 1976.

R. Brooks, “On colouring the nodes of a network”, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 37, no. 2, pp. 194–197, Apr. 1941, doi: 10.1017/S030500410002168X.

G. Chartrand and L. Lesniak, Graphs & digraphs. Boca Raton, FL: Chapman & Hall/CRC, 2000.

G. Chartrand and P. Zhang, Chromatic graph theory. (Discrete Mathematics and Its Applications) Boca Raton, FL: CRC Press, 2009.

R. Green, “Vizing’s theorem and edge-chromatic graph theory”, 2015. [On line]. Available: http://bit.ly/2LZMCwg

F. Harary, Graph theory, 5th ed. New Delhi: Narosa Publishing House, 2001.

T. Jensen and B. Toft, Graph coloring problems. New York, NY: John Wiley & Sons, Inc., 1995, doi: 10.1002/9781118032497.

S. Kalayathankal and C. Susanth, “The sum and product of chromatic numbers of graphs and their line graphs”, Journal Of Informatics And Mathematical Sciences, vol. 6, no. 2, pp. 77-85, 2014. [On line]. Available: http://bit.ly/2YF8tLr

A. King, B. Reed, and A. Vetta, “An upper bound for the chromatic number of line graphs”, European Journal of Combinatorics, vol. 28, no. 8, pp. 2182–2187, Nov. 2007, doi: 10.1016/j.ejc.2007.04.014.

J. Kok, N. Sudev, and K. Chithra, “Generalised colouring sums of graphs”, Cogent Mathematics, vol. 3, no. 1, Feb. 2016, doi: 10.1080/23311835.2016.1140002.

J. Kok and N. Sudev, “Theb-chromatic number of certain graphs and digraphs”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 19, no. 2, pp. 435–445, Jun. 2016, doi: 10.1080/09720529.2016.1160512.

M. Kubale, Ed., Graph colorings (Contemporary Mathematics, vol. 352). Providence, RI: American Mathematical Society, Jun. 2004, doi: 10.1090/conm/352.

D. West, Introduction to graph theory, 2nd ed. Dehli: Pearson Education Inc., 2001.



How to Cite

J. Kok, S. Naduvath, and M. K. Jamil, “Rainbow neighbourhood number of graphs”, Proyecciones (Antofagasta, On line), vol. 38, no. 3, pp. 469-484, Aug. 2019.