|
List assignment problems |
|---|---|
| รหัสดีโอไอ | |
| Title | List assignment problems |
| Creator | Wongsakorn Charoenpanitseri |
| Contributor | Chariya Uiyyasathian, Narong Punnim |
| Publisher | Chulalongkorn University |
| Publication Year | 2553 |
| Keyword | Graphic methods, Graph theory, กราฟ, ทฤษฎีกราฟ, ปริญญาดุษฎีบัณฑิต |
| 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. |
| URL Website | cuir.car.chula.ac.th |
