Colorability of glued graphs
Thesis (M.Sc.)--Chulalongkorn University, 2006
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Theses and Dissertations |
| Language: | English |
| Published: |
Chulalongkorn University
2011
|
| Subjects: | |
| Online Access: | http://cuir.car.chula.ac.th/handle/123456789/15010 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Chulalongkorn University |
| Language: | English |
| id |
th-cuir.15010 |
|---|---|
| record_format |
dspace |
| spelling |
th-cuir.150102011-03-31T08:09:57Z Colorability of glued graphs การระบายสีกราฟปะติด Chanon Promsakon Chariya Uiyyasathian Chulalongkorn University. Faculty of Science Adhesive joints Graph coloring Graph theory Thesis (M.Sc.)--Chulalongkorn University, 2006 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. กำหนด G₁ และ G₂ เป็นกราฟและให H₁ และ H₂ เป็นกราฟย่อยเชื่อมโยงที่มีเส้นเชื่อมอย่างน้อยหนึ่งเส้นของ G₁ และ G₂ ตามลำดับ โดยที่ H₁ ≅ H₂ ด้วยสมสัณฐาน ƒ กราฟปะติดของ G₁ และ G₂ ที่ H₁ และ H₂ เทียบกับ ƒ เขียนแทนด้วย G₁<>G₂ / H₁ ≅ H₂ คือกราฟที่ได้จากการรวมกราฟ G₁ และ G₂ โดยการปะติดจุดยอดและเส้นเชื่อมใน H₁ และ H₂ ให้ตรงกับสมสัณฐาน ƒ เราสนใจการปะติดกราฟระหว่างกราฟชนิดเดียวกัน โดยกราฟที่เราสนใจคือ กราฟป่า กราฟต้นไม้ กราฟสองส่วน กราฟ k ส่วน กราฟมีคอร์ด และกราฟช่วง นอกจากนั้นเราศึกษาสมบัติของกราฟปะติดในการระบายสีจุดยอดและการระบายสีเส้นเชื่อม เราหาขอบเขตของรงคเลขและรงคเลขของเส้นเชื่อมของกราฟปะติด พร้อมทั้งให้กราฟที่รับประกันว่าแต่ละขอบเขตดีที่สุด 2011-03-31T08:09:56Z 2011-03-31T08:09:56Z 2006 Thesis 9741426267 http://cuir.car.chula.ac.th/handle/123456789/15010 en Chulalongkorn University 947996 bytes application/pdf application/pdf Chulalongkorn University |
| institution |
Chulalongkorn University |
| building |
Chulalongkorn University Library |
| country |
Thailand |
| collection |
Chulalongkorn University Intellectual Repository |
| language |
English |
| topic |
Adhesive joints Graph coloring Graph theory |
| spellingShingle |
Adhesive joints Graph coloring Graph theory Chanon Promsakon Colorability of glued graphs |
| description |
Thesis (M.Sc.)--Chulalongkorn University, 2006 |
| author2 |
Chariya Uiyyasathian |
| author_facet |
Chariya Uiyyasathian Chanon Promsakon |
| format |
Theses and Dissertations |
| author |
Chanon Promsakon |
| author_sort |
Chanon Promsakon |
| title |
Colorability of glued graphs |
| title_short |
Colorability of glued graphs |
| title_full |
Colorability of glued graphs |
| title_fullStr |
Colorability of glued graphs |
| title_full_unstemmed |
Colorability of glued graphs |
| title_sort |
colorability of glued graphs |
| publisher |
Chulalongkorn University |
| publishDate |
2011 |
| url |
http://cuir.car.chula.ac.th/handle/123456789/15010 |
| _version_ |
1681414125535625216 |