List assignment problems

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.