Equitable coloring on subdivision vertex join of cycle C_m with path P_n

K. Praveena, M. Venkatachalam and A. Rohini
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 25, 2019, Number 2, Pages 190–198
DOI: 10.7546/nntdm.2019.25.2.190-198
Full paper (PDF, 155 Kb)

Details

Authors and affiliations

K. Praveena
Department of Computer Science,
Dr. G. R. Damodaran College of Science (Autonomous)
Coimbatore – 641 014, Tamil Nadu, India

M. Venkatachalam
PG and Research Department of Mathematics,
Kongunadu Arts and Science College (Autonomous)
Coimbatore – 641 029, Tamil Nadu, India

A. Rohini
PG and Research Department of Mathematics,
Kongunadu Arts and Science College (Autonomous)
Coimbatore – 641 029, Tamil Nadu, India

Abstract

Graph coloring is one of the research areas that shaped the graph theory as we know it today. An equitable coloring of a graph G is a proper coloring of the vertices of G such that color classes differ in size by at most one. The subdivision graph S(G) of a graph G is the graph obtained by inserting a new vertex into every edge of G. Let G₁ and G₂ be two graphs with vertex sets V(G₁) and V(G₂), respectively. The subdivision-vertex join of two vertex disjoint graphs G₁ and G₂ is the graph obtained from S(G₁) and G₂ by joining each vertex of V(G₁) with every vertex of V(G₂). In this paper, we find the equitable chromatic number of subdivision vertex join of cycle graph with path graph.

Keywords

• Equitable coloring
• Subdivision graph
• Subdivision vertex join

2010 Mathematics Subject Classification

• 05C15

References

1. Bu, C. & Zhou, J. (2014). Resistance distance in subdivision-vertex join and subdivision-edge join of graphs, Linear Algebra and its Applications, 458, 454–462.
2. Indulal, G. (2012). Spectrum of two new joins of graphs and infinite families of integral graphs, Kragujevac Journal of Mathematics, 36, 133–139.
3. Kaliraj, K., J, Vivik, V., & Vernold Vivin, J. (2012). Equitable coloring on Corona graph of Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, 81, 191–197.
4. Liu, X. G. & Lu, P. L. (2013). Spectra of Subdivision-Vertex and Subdivision-Edge neighbourhood coronae, Linear Algebra and its Applications, 438 (8), 3547–3559.
5. Liu, X. G. & Zhang, Z. (2019). Spectra of subdivision-vertex join and subdivision-edge join of two graphs, Bulletin of the Malaysian Mathematical Sciences Society, 42 (1), 15–31.
6. Meyer, W. (1973). Equitable coloring, Amer. Math. Monthly, 80, 920–922.
7. Varghese, R. P. & Reji Kumar, K. (2016). Spectra of a new Join of Two Graphs, Advances in Theoretical and Applied Mathematics, 11 (4), 459–470.
8. Zhong-Fu, Z., Mu-chun, L. & Bin, Y. (2008). On the Vertex Distinguishing Equitable Edge-coloring of Graphs, ARS Combinatoria, 86, 193–200