Chulalongkorn University Theses and Dissertations (Chula ETD)

Colorability of glued graphs

Other Title (Parallel Title in Other Language of ETD)

การระบายสีกราฟปะติด

Year (A.D.)

2006

Document Type

Thesis

First Advisor

Chariya Uiyyasathian

Faculty/College

Faculty of Science (คณะวิทยาศาสตร์)

Degree Name

Master of Science

Degree Level

Master's Degree

Degree Discipline

Mathematics

DOI

10.58837/CHULA.THE.2006.1186

Abstract

Let G₁ and G₂ be any two graphs. Let H₁ and H₂ be non-trivial connected subgraphs of G₁ and G₂, respectively, such that H₁ ≅ H₂ with an isomorphism ƒ, then the glued graph of G₁ and G₂ at H₁ and H₂ with respect to ƒ, denoted by G₁<>G₂ / H₁ ≅ H₂ is the graph that results from combining G₁ with G₂ by identifying H₁ and H₂ with respect to the isomorphism ƒ between H₁ and H₂. We investigate the results of the graph obtaining by gluing graphs of the same type where the types we are interested in are forests, trees, bipartite graphs, k-partite graphs, chordal graphs and interval graphs. Furthermore, we study properties of glued graphs involving in their colorability and edge-colorability. We give bounds of the chromatic numbers and the edge-chromatic numbers of glued graphs and also provide graphs to guarantee that each bound is the best possible.

Other Abstract (Other language abstract of ETD)

กำหนด G₁ และ G₂ เป็นกราฟและให H₁ และ H₂ เป็นกราฟย่อยเชื่อมโยงที่มีเส้นเชื่อมอย่างน้อยหนึ่งเส้นของ G₁ และ G₂ ตามลำดับ โดยที่ H₁ ≅ H₂ ด้วยสมสัณฐาน ƒ กราฟปะติดของ G₁ และ G₂ ที่ H₁ และ H₂ เทียบกับ ƒ เขียนแทนด้วย G₁<>G₂ / H₁ ≅ H₂ คือกราฟที่ได้จากการรวมกราฟ G₁ และ G₂ โดยการปะติดจุดยอดและเส้นเชื่อมใน H₁ และ H₂ ให้ตรงกับสมสัณฐาน ƒ เราสนใจการปะติดกราฟระหว่างกราฟชนิดเดียวกัน โดยกราฟที่เราสนใจคือ กราฟป่า กราฟต้นไม้ กราฟสองส่วน กราฟ k ส่วน กราฟมีคอร์ด และกราฟช่วง นอกจากนั้นเราศึกษาสมบัติของกราฟปะติดในการระบายสีจุดยอดและการระบายสีเส้นเชื่อม เราหาขอบเขตของรงคเลขและรงคเลขของเส้นเชื่อมของกราฟปะติด พร้อมทั้งให้กราฟที่รับประกันว่าแต่ละขอบเขตดีที่สุด

Link to Full Text

Share

COinS