Rainbow neighbourhood number of graphs
DOI:
https://doi.org/10.22199/issn.0717-6279-2019-03-0030Keywords:
Colour cluster, Colour classes, Rainbow neighbourhood, Expanded line graph, v-cliqueAbstract
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.References
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.
Published
How to Cite
Issue
Section
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
