International Journal of Mathematics Trends and Technology
Volume 37 | Number 1 | Year 2016 | Article Id. IJMTT-V37P509 | DOI : https://doi.org/10.14445/22315373/IJMTT-V37P509
Graph colouring is one of the most important area of research in graph theory. A distance-2 colouring of a graph G is a proper vertex colouring of G such that every two vertices at a distance-2 or less are assigned different colours. The least integer k for which there is a k-colouring satisfying this condition is the distance-2 chromatic number of G and is denoted by 2 ( ) G . In this paper, we present algorithms to determine the distance-2 chromatic number for the duplicate graph of the Mycielskian graph of paths, cycles and complete graphs.
[1] O.V. Borodin, A.O. Ivanova and N.T. Neustroeva, Distance-2 colouring of sparse plane graphs (in Russian), Siberian Electronic Mathematical Reports, 1 (2004), 76 90.
[2] G.J. Chang, L. Huang and X. Zhu, Circular chromatic numbers of Mycielski’s graphs, Discrete Mathematics, 205 (1999), 23 37.
[3] G. Fertin, E. Godard and A. Raspaud, Acyclic and Kdistance colouring of the grid, Inform. Process. Lett., 87 (2003), 51 58.
[4] G. Fertin, A. Raspaud and B. Reed, On star colouring of graphs, Lecture Notes in Computer Science, 2204 (2001), 140 153.
[5] J. Mycielski, Sur le colouriage des graphs, Colloq. Math., 3 (1955), 161 162.
[6] K. Thirusangu, P.P. Ulaganathan and B. Selvam, Cordial labeling in duplicate graphs, Int. J. Computer Math. Sci. Appl., 4(1-2) (2010), 179 186.
[7] P.P. Ulaganathan, K. Thirusangu and B. Selvam, Edge magic total labeling in extended duplicate graph of path, International Journal of Applied Engineering Research, 6(10) (2011), 1211.
K. Anitha, B.Selvam, K. Thirusangu, "Distance-2 Chromatic Number for the Duplicate Graph of the Mycielskian Graphs," International Journal of Mathematics Trends and Technology (IJMTT), vol. 37, no. 1, pp. 97-72, 2016. Crossref, https://doi.org/10.14445/22315373/IJMTT-V37P509
PDF 
Abstract 
Keywords 
References 
Citation