Volume 19, Issue 1 (4-2024)
IJMSI 2024, 19(1): 149-160 |
Back to browse issues page
Abstract:
A vertex coloring of a graph G is called acyclic if no two adjacent vertices have the same color and no cycle in G is bichromatic. The acyclic chromatic number a(G) of a graph G is the least number of colors in an acyclic coloring of G. In this paper, we obtain bound for the acyclic chromatic number of the strong product of a tree and a graph. An exact value for the acyclic chromatic number of the strong product of two trees is derived. Further observations are made on the upper bound for the strong product of three paths.
Type of Study: Research paper |
Subject:
General
References
1. M. O. Albertson, G. G. Chappell, H. A. Kierstead, A. Kundgen, R. Ramamurthi, Coloring with No 2-colored P4's, The electronic journal of combinatorics, 11(1), (2004), p. 26. [DOI:10.37236/1779]
2. P. S. Babu, Chithra A V, Acyclic Coloring of Some Operations on Certain Graphs, International Research Journal on Mathematical Sciences, (2012), 951-956.
3. O. V. Borodin, On Acyclic Colorings of Planar Graphs, Discrete Mathematics, 25(3), 1979, 211-236. [DOI:10.1016/0012-365X(79)90077-3]
4. D. Greenwell, L. Lovasz, Applications of Product Colouring, Acta Mathematica Hungarica, 25(3-4), (1974), 335-340.. [DOI:10.1007/BF01886093]
5. B. Grunbaum, Acyclic Colorings of Planar Graphs, Israel J. Math., 14, (1973), 390-412. [DOI:10.1007/BF02764716]
6. F. Harary, G. W. Wilcox, Boolean Operations on Graphs, Mathematica Scandinavica, (1967), 41-51. [DOI:10.7146/math.scand.a-10817]
7. R. E. Jamison, G. L. Matthews, J. Villalpando, Acyclic Colorings of Products of Trees, Information Processing Letters, 99(1), (2006), 7-12. [DOI:10.1016/j.ipl.2005.11.023]
8. S. Klavar, Coloring Graph Productsa Survey, Discrete Mathematics, 155(1-3), (1996), 135-145. [DOI:10.1016/0012-365X(94)00377-U]
9. A. V. Kostochka, Upper Bounds on the Chromatic Functions of Graphs, Ph.D. Thesis, Novosibirsk, Russia, 1978.
10. L. Lovasz, On the Shannon Capacity of a Graph, IEEE Transactions on Information theory, 25(1), (1979), 1-7. [DOI:10.1109/TIT.1979.1055985]
11. G. Sabidussi, Graph Multiplication, Math. Z., 72, (1962), 446-457. [DOI:10.1007/BF01162967]
12. C. Shannon, The Zero Error Capacity of a Noisy Channel, IRE Transactions on Information Theory, 2(3), (1956), 8-19. [DOI:10.1109/TIT.1956.1056798]
13. M. Tavakoli, F. Rahbarnia, A. R. Ashrafi, Note on Strong Product of Graphs, Kragujevac Journal of Mathematics, 37(1), (2013), 187-193.
14. J. Zerovnik, Chromatic Numbers of the Strong Product of Odd Cycles, Mathematica Slovaca, 56(4), (2006), 379-385.
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |