Chulalongkorn University Theses and Dissertations (Chula ETD)
Isomorphism classes and vertex coloring for graphs C[subscript G](a,b)
Other Title (Parallel Title in Other Language of ETD)
ชั้นสมสัณฐานและการระบายสีจุดยอดสำหรับกราฟ C[subscript G](a,b)
Year (A.D.)
2012
Document Type
Thesis
First Advisor
Yotsanan Meemark
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Mathematics
DOI
10.58837/CHULA.THE.2012.969
Abstract
In this thesis, we use the properties of finite abelian group to derive isomorphism testing on the graph C[subscript G](a,b) defined above. We study classes of isomorphic graphs. This work generalizes Nicoloso and Pietropaoli’s paper, which obtain analogous results when is a cyclic group. In addition, we study the algorithms to give an explicit assignment of colors to the vertices of graph C[subscript G](a,b) such that adjacent vertices receive different colors and the number of colors is minimized.
Other Abstract (Other language abstract of ETD)
ในวิทยานิพนธ์ฉบับนี้ เราใช้สมบัติของกรุปจำกัดสลับที่ในการทดสอบการสมสัณฐานบนกราฟ C[subscript G](a,b) ที่ได้นิยามไว้ข้างต้น เราศึกษาชั้นสมสัณฐานของกราฟดังกล่าว ทำให้งานของเราเป็นกรณีทั่วไปของนิโคโลโซและไพโทรเปาลิ ซึ่งผลที่ได้คล้ายคลึงกัน เมื่อ เป็นกรุปวัฏจักร นอกจากนี้ เรายังศึกษาขั้นตอนวิธีและได้วิธีการระบายสีจุดยอดที่ชัดแจ้งสำหรับกราฟ C[subscript G](a,b) โดยที่จุดยอดประชิดกันใช้สีต่างกัน และมีจำนวนสีที่ใช้น้อยที่สุด
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Leela-apiradee, Worrawate, "Isomorphism classes and vertex coloring for graphs C[subscript G](a,b)" (2012). Chulalongkorn University Theses and Dissertations (Chula ETD). 62009.
https://digital.car.chula.ac.th/chulaetd/62009