Chulalongkorn University Theses and Dissertations (Chula ETD)

List assignment problems

Other Title (Parallel Title in Other Language of ETD)

ปัญหาการกำหนดค่ารายการ

Year (A.D.)

2010

Document Type

Thesis

First Advisor

Chariya Uiyyasathian

Second Advisor

Narong Punnim

Faculty/College

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

Degree Name

Doctor of Philosophy

Degree Level

Doctoral Degree

Degree Discipline

Mathematics

DOI

10.58837/CHULA.THE.2010.1147

Abstract

A k-list assignment of a graph G is a function which assigns a set of size k to each vertex of G. Given a k-list assignment L of a graph G, L is called a (k, t)-list assignment when ∣∪υεV(G) L(υ) = t and G is L-colorable when G has a proper coloring f such that f(υ) ε L(υ) for all υ ε V(G). If a graph G is L-colorable for every (k, t)-list assignment L, then G is called (k, t)-choosable and if G is (k, t)-choosable for each positive integer t then G is called k-choosable. In this dissertation, we investigate a sufficient condition to be (k, t)-choosable of n-vertex graphs and n-vertex graphs not containing Kk+1 as a subgraph. Moreover, we establish new strategies to obtain the complete result of 3-choosability of complete bipartite graphs with at most 16 vertices, and study the (k, t)-choosability of the complete bipartite graph K(2Kk-1), (2Kk-1) for all positive integers t.

Other Abstract (Other language abstract of ETD)

การกำหนดค่ารายการแบบ-k ของกราฟ คือฟังก์ชันจากเซตของจุดยอดของกราฟ G ไปเซตของเซตขนาด k ให้ L เป็นการกำหนดค่ารายการแบบ-k ของกราฟ G เรียก L ว่าเป็นการกำหนดค่ารายการแบบ- (k, t) เมื่อ ∣∪υεV(G) L(υ) = t และ G เป็นกราฟระบายสีได้แบบ -L เมื่อ G มีฟังก์ชันการระบายสี f ที่ f(υ) ε L(υ) ทุก υ ε V(G) ถ้ากราฟ G เป็นกราฟระบายสีได้แบบ- L สำหรับทุก L ที่เป็นการกำหนดค่ารายการแบบ- (k, t) จะเรียก G ว่ากราฟเลือกได้แบบ- (k, t) และถ้า G เป็นกราฟเลือกได้แบบ- (k, t) สำหรับทุก t แล้วจะเรียก G ว่าเป็นกราฟเลือกได้แบบ- k ในวิทยานิพนธ์ฉบับนี้เราหาเงื่อนไขเพียงพอที่ทำให้กราฟที่มีจุดยอด n จุดเป็นกราฟเลือกได้แบบ- (k, t) และหาเงื่อนไขที่เพียงพอที่ทำให้กราฟที่มีจุดยอด n จุดซึ่งไม่มี Kk+1 เป็นกราฟย่อยเป็นกราฟเลือกได้แบบ- (k, t) นอกจากนั้นเราสร้างกลยุทธ์ใหม่เพื่อที่ได้ผลลัพธ์ทั้งหมดเกี่ยวกับสมบัติการเลือกได้แบบ-3 ของกราฟสองส่วนแบบบริบูรณ์ที่มีจุดยอดไม่เกิน 16 จุด และศึกษาสมบัติการเลือกได้แบบ- (k, t) ของกราฟสองส่วนแบบบริบูรณ์ K(2Kk-1), (2Kk-1)

Link to Full Text

Share

COinS