On the Chromatic Number of Cycle Books Graph

Abstract

Graph coloring is a fundamental topic in graph theory, with various applications in scheduling, networking, and optimization problems. In this study, we investigate the chromatic number of the cycle books graph , a structured graph formed by attaching multiple cycles to a common path . We establish that the chromatic number of    depends on the parity of . Specifically, we prove that if  is even, the chromatic number is , while if  is odd, the chromatic number is . These results provide a deeper understanding of coloring properties in book-like graphs and contribute to the broader study of chromatic numbers in structured graph families. The findings may be extended to other variations of book graphs and related topologies in future research.

Keywords

Chromatic number, Cycle Books Graph, Graph Coloring, Cycle, Graphs

Full Text:

PDF Check Plagiarism

References

P. Franklin, “The Four Color Problem,” Am. J. Math., vol. 44, no. 3, p. 225, Jul. 1922, doi: 10.2307/2370527.

K. Appel and W. Haken, “Every planar map is four colorable. Part I: Discharging,” Illinois J. Math., vol. 21, no. 3, Sep. 1977, doi: 10.1215/ijm/1256049011.

G. Chartrand and P. Zhang, A First Course in Graph Theory. United States: DOVER PUBLICATIONS, INC., 2012. [Online]. Available: http://lib.ysu.am/disciplines_bk/86ed8ab971105564c1b66357510f992a.pdf

B. Montgomery, “Dynamic coloring of graphs,” West Virginia University Libraries, 2001. doi: 10.33915/etd.1397.

N. Y. Vlasova and D. V. Karpov, “Bounds on the Dynamic Chromatic Number of a Graph in Terms of its Chromatic Number,” J Math Sci, vol. 232, pp. 21–24, 2018, doi: https://doi.org/10.1007/s10958-018-3855-4.

A. V. Sheeba, “Degree distance and Gutman index of corona product of graphs,” Trans. Comb., vol. 4, no. 3, pp. 11–23, 2015, doi: 10.22108/toc.2015.6332.

S. Jahanbekam, J. Kim, S. O, and D. B. West, “On r-dynamic coloring of graphs,” Discret. Appl. Math., vol. 206, pp. 65–72, Jun. 2016, doi: 10.1016/j.dam.2016.01.016.

A. Taherkhani, “On r-dynamic chromatic number of graphs,” Discret. Appl. Math., vol. 201, pp. 222–227, Mar. 2016, doi: 10.1016/j.dam.2015.07.019.

N. Ainun, A. Rianalita, and R. Mahmuzah, “Model Pembelajaran Creative Problem Solving Berbasis Budaya Lokal Pada Materi Program Linear Siswa SMA Negeri 9 Banda Aceh,” J. Serambi, vol. 4, no. 1, pp. 47–57, 2020, [Online]. Available: http://ojs.serambimekkah.ac.id/serambi-edukasi/article/view/1872

Finata Rastic Andrari, M. Maimunah, and N. D. Qadarsih, “PENERAPAN PEWARNAAN GRAF PADA PENJADWALAN UJIAN TAHFIDZ MENGGUNAKAN ALGORITMA WELCH POWELL,” Transform. J. Pendidik. Mat. dan Mat., vol. 7, no. 1, pp. 81–92, Jun. 2023, doi: 10.36526/tr.v7i1.2833.

M. Abdy, R. Syam, and T. Tina, “Bilangan Kromatik Pewarnaan Titik pada Graf Dual dari Graf Roda,” J. Math. Comput. Stat., vol. 4, no. 2, p. 95, 2021, doi: 10.35580/jmathcos.v4i2.24443.

A. I. Kristiana, M. I. Utoyo, Dafik, I. H. Agustin, R. Alfarisi, and E. Waluyo, “Vertex coloring edge-weighting of coronation by path graphs,” J. Phys. Conf. Ser., vol. 1211, p. 012004, Apr. 2019, doi: 10.1088/1742-6596/1211/1/012004.

Y. Xu, “The Chromatic Number of (P5, HVN)-free Graphs,” Acta Math. Appl. Sin. English Ser., vol. 40, no. 4, pp. 1098–1110, Oct. 2024, doi: 10.1007/s10255-024-1029-3.

D. Wu, B. Xu, and Y. Xu, “The chromatic number of heptagraphs,” J. Graph Theory, vol. 106, no. 3, pp. 711–736, Jul. 2024, doi: 10.1002/jgt.23094.

A. Lahiri, S. Nandi, S. Taruni, and S. Sen, “On Chromatic Number of (n, m)-graphs,” 2021, pp. 745–751. doi: 10.1007/978-3-030-83823-2_119.

T. Karthick and S. Mishra, “On the Chromatic Number of (P6,Diamond)-Free Graphs,” Graphs Comb., vol. 34, no. 4, pp. 677–692, Jul. 2018, doi: 10.1007/s00373-018-1905-9.

M. Ridwan, H. Assiyatun, and E. T. Baskoro, “The dominating partition dimension and locating-chromatic number of graphs,” Electron. J. Graph Theory Appl., vol. 11, no. 2, p. 455, Oct. 2023, doi: 10.5614/ejgta.2023.11.2.10.

N. Cordero-Michel, H. Galeana-Sánchez, and I. A. Goldfeder, “Cycles and new bounds for the chromatic number,” Discrete Math., vol. 346, no. 3, p. 113255, Mar. 2023, doi: 10.1016/j.disc.2022.113255.

A. Gyárfás, “Graphs with k odd cycle lengths,” Discrete Math., vol. 103, no. 1, pp. 41–48, May 1992, doi: 10.1016/0012-365X(92)90037-G.

P. Mihók and I. Schiermeyer, “Cycle lengths and chromatic number of graphs,” Discrete Math., vol. 286, no. 1–2, pp. 147–149, Sep. 2004, doi: 10.1016/j.disc.2003.11.055.

J. Santoso and Darmaji, “The partition dimension of cycle books graph,” J. Phys. Conf. Ser., vol. 974, p. 012070, Mar. 2018, doi: 10.1088/1742-6596/974/1/012070.

J. Santoso, “Dimensi Metrik Dan Dimensi Partisi Graf Cycle Books,” Sepuluh Nopember Institut of Technology, 2018. [Online]. Available: https://repository.its.ac.id/59061/1/06111650010004-Master_Thesis.pdf

J. Santoso and D. Darmaji, “THE PARTITION DIMENSION OF CYCLE BOOKS GRAPH B_(m,n) WITH A COMMON PATH P_2,” BAREKENG J. Ilmu Mat. dan Terap., vol. 19, no. 2, pp. 791–804, Apr. 2025, doi: 10.30598/barekengvol19iss2pp791-804.

N. Inayah, W. Aribowo, and M. M. Windra Yahya, “The Locating Chromatic Number of Book Graph,” J. Math., vol. 2021, pp. 3–5, 2021, doi: 10.1155/2021/3716361.

N. Hartsfield and G. Ringel, Pearls in Graph Theory. San Diego: Academic Press, 1994.

H. J. Karloff, “An NC algorithm for Brooks’ Theorem,” Theor. Comput. Sci., vol. 68, no. 1, pp. 89–103, Oct. 1989, doi: 10.1016/0304-3975(89)90121-7.

N. Robertson, D. P. Sanders, P. Seymour, and R. Thomas, “Reducibility in the Four-Color Theorem,” pp. 1–8, 2014, doi: 16. https://doi.org/10.48550/arXiv.1401.6481.

http://dx.doi.org/10.28989/compiler.v14i1.2930

Article Metrics

Abstract view: 222 times
Download     : 312   times Download     : 7   times

This work is licensed under a Creative Commons Attribution 4.0 International License.

Refbacks

• There are currently no refbacks.