EDGE COLORING CYCLE BOOKS GRAPH B_(C_n,m)

Yeni Rahma Oktaviani, Saman Abdurrahman

Abstract


This study investigates the edge coloring of the cycle book graphs, denoted as B_(C_n,m), which consist of m cycles C_n intersection at a shared P_2 path. The primary objective is to identify the chromatic index-the fewest colors needed to ensure no two adjacent edges share the same color. Utilizing a deductive approach, the researchers developed an edge coloring function based on cyclic patterns for both even and odd values of n. The findings establish that the chromatic index χ' (B_(C_n,m) )= m+1 for all n≥3 and m≥2. This result is validated by coloring construction that aligns with the lower bound established by Vizing’s Theorem

Keywords


Chromatic index, Cycle Books Graphs, Edge Graph Coloring

Full Text:

PDF

References


R. Cole and J. Hopcroft, “On Edge Coloring Bipartite Graphs*,” Soc. Ind. Appl. Math., vol. 11, no. 3, pp. 540–546, 1982.

G. Y. W. R. Kaawoan and I. K. Budayasa, “Pewarnaan Sisi Pada Graf Komplet yang Memuat Sikel C4 Terwarna Sejati,” J. Ilm. Mat., vol. 13, no. 2, pp. 90–98, 2025, [Online]. Available: https://ejournal.unesa.ac.id/index.php/mathunesa/article/view/64649

V. G. Vizing, “On an estimate of the chromatic class of a p-graph,” Discret Anal., vol. 3, pp. 25–30, 1964, Accessed: Apr. 20, 2026. [Online]. Available: https://cir.nii.ac.jp/crid/1571980075458819456.bib?lang=en

J. Santoso, “On the Chromatic Number of Cycle Books Graph,” Compiler, vol. 14, no. 1, p. 27, 2025, doi: 10.28989/compiler.v14i1.2930.

V. R. Noviyanti, Kusbudiono, I. H. Agustin, and Dafik, “Pewarnaan Sisi r-Dinamis pada Graf Khusus dan Graf Operasi Sakel,” CGANT J. Math. Appl., vol. 2, no. 1, pp. 1–14, 2021, doi: 10.25037/cgantjma.v2i1.47.

J. M. Aldous and R. J. Wilson, Graphs and applications: an introductory approach, 4th ed. 2004. doi: 10.5860/choice.38-2200.

J. Santoso, Darmaji, A. Muliyana, and A. Saragih, “The Matric Dimension of Cycle Book Graphs Bc(m,n) Formed By A Common Path P2,” Barekeng, vol. 20, no. 2, pp. 1155–1166, 2026, doi: 10.30598/barekengvol20iss2pp1155-1166.

D. B. West, “Introduction to Graph Theory (2nd Edition),” 2001, Pearson Education (Singapore), India.

R. Diestel, Graph Theory, 5th edition. Berlin: Springer, 2017.

F. Harary, Graph Theory. Philippines: Reading, MA:Addison-Wesley, 1969.




DOI: https://doi.org/10.15548/map.v8i1.13832

Refbacks

  • There are currently no refbacks.


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

 

Lisensi Creative Commonsis licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.