Chulalongkorn University Theses and Dissertations (Chula ETD)

Total colorings of glued graphs

Other Title (Parallel Title in Other Language of ETD)

การระบายสีแบบรวมของกราฟปะติด

Year (A.D.)

2007

Document Type

Thesis

First Advisor

Chariya Uiyyasathian

Second Advisor

Wanida Hemakul

Faculty/College

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

Degree Name

Master of Science

Degree Level

Master's Degree

Degree Discipline

Mathematics

DOI

10.58837/CHULA.THE.2007.1076

Abstract

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.

Other Abstract (Other language abstract of ETD)

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

Link to Full Text

Share

COinS