Total colorings of glued graphs

• Main Author: Wongsakorn Charoenpanitseri (Author)
• Other Authors: Chariya Uiyyasathian (Contributor), Wanida Hemakul (Contributor), Chulalongkorn University. Faculty of Science (Contributor)
• Format: Book
• Published: Chulalongkorn University, 2013-06-26T14:49:26Z.
• Subjects: Thesis
• Online Access: http://cuir.car.chula.ac.th/handle/123456789/32534
• Other title: การระบายสีแบบรวมของกราฟปะติด
• Notes: http://cuir.car.chula.ac.th/handle/123456789/32534
• Keywords: Graph coloring; Complete graphs; Graphic methods; Bipartite graphs; กราฟ

Thesis (M.Sc.)--Chulalongkorn University, 2007

The Total Coloring conjecture states that for every graph G, X"(G) ≤ ∆(G)+2 when X"(G) is the total chromatic number of G and ∆(G) is the maximum number of degree of vertices of G. We say that a graph G is of type 1 if X"(G) = ∆(G)+1 and type 2 if X"(G) = ∆(G)+2. In this thesis, upper bounds of the total chromatic number of glued graphs in terms of the total chromatic number of original graphs are presented. We investigate that total chromatic number of glued graphs of same class where the classes are cycles, trees, bipartite graphs and complete graphs and prove that these glued graphs satisfy the Total Coloring Conjecture and obtain necessary and sufficient conditions for these glued graphs except the glued graph of bipartite graphs to be either of type 1 or type 2. Furthermore, we study sufficient conditions for any graph to satisfy the Total Coloring Conjecture and be either type 1 graph or type 2 graph and use these conditions to obtain the result of glued graphs of any graph and any tree.

ข้อความคาดการณ์ของการระบายสีแบบรวมของกราฟ G กล่าวว่า X"(G)≤ ∆(G)+2 เมื่อ X"(G) แทนรงคเลขแบบรวมของกราฟ G และ ∆(G) แทนดีกรีสูงสุดในกราฟ G เรากล่าวว่ากราฟ G สอดคล้องสมบัติชนิดที่หนึ่ง ถ้า X"(G) = ∆(G)+1 และชนิดที่สอง ถ้า X"(G) = ∆(G)+2 ในวิทยานิพนธ์ฉบับนี้เราหาขอบเขตบนของรงคเลขแบบรวมของกราฟปะติดในเทอมของรงคเลขแบบรวมของกราฟเริ่มต้น เราสนใจรงคเลขแบบรวมของกราฟปะติดระหว่างกราฟกลุ่มเดียวกันซึ่งคือ กราฟวง กราฟต้นไม้ กราฟสองส่วน และกราฟบริบูรณ์ และพิสูจน์ว่ากราฟเหล่านี้สอดคล้องข้อความคาดการณ์ของการระบายสีแบบรวมและเสนอเงื่อนไขจำเป็นและเพียงพอสำหรับกราฟปะติดเหล่านี้ยกเว้นกราฟปะติดของกราฟสองส่วน สอดคล้องข้อความคาดการณ์ของการระบายสีแบบรวมและสมบัติชนิดที่หนึ่ง หรือชนิดที่สอง ยิ่งกว่านั้นเราสนใจเงื่อนไขเพียงพอสำหรับกราฟใดๆ ที่สอดคล้องข้อความคาดการณ์ของการระบายสีแบบรวมและสมบัติชนิดที่หนึ่ง หรือ ชนิดที่สองเพื่อใช้เงื่อนไขเหล่านี้กับผลลัพธ์ของกราฟปะติดของกราฟใดๆ และกราฟต้นไม้ใดๆ