On dynamic coloring of certain cycle-related graphs
Tóm tắt
Coloring the vertices of a particular graph has often been motivated by its utility to various applied fields and its mathematical interest. A dynamic coloring of a graph G is a proper coloring of the vertex set V(G) such that for each vertex of degree at least 2, its neighbors receive at least two distinct colors. A dynamic k-coloring of a graph is a dynamic coloring with k colors. A dynamic k-coloring is also called a conditional (k, 2)-coloring. The smallest integer k such that G has a dynamic k-coloring is called the dynamic chromatic number $$\chi _d(G)$$ of G. In this paper, we investigate the dynamic chromatic number for the line graph of sunlet graph and middle graph, total graph and central graph of sunlet graphs, paths and cycles. Also, we find the dynamic chromatic number for Mycielskian of paths and cycles and the join graph of paths and cycles.
Tài liệu tham khảo
Ahadi, A.; Akbari, S.; Dehghan, A.; Ghanbari, M.: On the difference between chromatic number and dynamic chromatic number of graphs. Discret. Math. 312, 2579–2583 (2012)
Akbari, S.; Ghanbari, M.; Jahanbakam, S.: On the dynamic chromatic number of graphs. Combinatorics and Graphs. In: Contemporary Mathematics-American Mathematical Society, vol. 531, pp. 11–18 (2010)
Akbari, S.; Ghanbari, M.; Jahanbekam, S.: On the list dynamic coloring of graphs. Discret. Appl. Math. 157, 3005–3007 (2009)
Alishahi, M.: Dynamic chromatic number of regular graphs. Discret. Appl. Math. 160, 2098–2103 (2012)
Bowler, N.; Erde, J.; Lehner, F.; Merker, M.; Pitz, M.; Stavropoulos, K.: A counterexample to Montgomery’s conjecture on dynamic colourings of regular graphs. Discret. Appl. Math. 229, 151–153 (2017)
Dehghan, A.; Ahadi, A.: Upper bounds for the \(2\)-hued chromatic number of graphs in terms of the independence number. Discret. Appl. Math. 160(15), 2142–2146 (2012)
Harary, F.: Graph Theory. Narosa Publishing home, New Delhi (1969)
Kim, S.J.; Lee, S.J.; Park, W.J.: Dynamic coloring and list dynamic coloring of planar graphs. Discret. Appl. Math. 161, 2207–2212 (2013)
Lai, H.J.; Montgomery, B.; Poon, H.: Upper bounds of dynamic chromatic number. Ars Combinatoria 68, 193–201 (2003)
Li, X.; Zhou, W.: The \(2\)nd-order conditional \(3\)-coloring of claw-free graphs. Theor. Comput. Sci. 396, 151–157 (2008)
Li, X.; Yao, X.; Zhou, W.; Broersma, H.: Complexity of conditional colorability of graphs. Appl. Math. Lett. 22, 320–324 (2009)
Mohanapriya, N.; Vernold Vivin, J.; Venkatachalam, M.: \(\delta \)-Dynamic chromatic number of Helm graph families. Cogent Math. 3(1), 1178411, 1–4 (2016)
Mohanapriya, N.; Vernold Vivin, J.; Venkatachalam, M.: On dynamic coloring of fan graphs. Int. J. Pure Appl. Math. 106, 169–174 (2016)
Montgomery, B.: Dynamic coloring of graphs, ProQuest LLC, Ann Arbor, MI, Ph.D Thesis, West Virginia University (2001)
Mycielski, J.: Surle coloriage des graphes. Colloquium Mathematicum 3, 161–162 (1955)
Taherkhani, A.: On \(r\)-dynamic chromatic number of graphs. Discret. Appl. Math. 201, 222–227 (2016)
Vernold Vivin, J.: Harmonious coloring of total graphs, \(n\)-leaf, central graphs and circumdetic graphs, Bharathiar University, (2007), Ph.D Thesis, Coimbatore, India