List Coloring in Graphs: Constructions Based on a Refined Scale of Choosability

Abstract

A proper vertex coloring of a graph assigns colors to its vertices so that no two adjacent vertices receive the same color. List coloring is a variation of proper vertex coloring where each vertex is assigned a prescribed list of available colors. In 2020, Xuding Zhu introduced a generalization of list coloring called λ-choosability which makes use of integer partitions to categorize list assignments. λ-partitionability is another framework of list coloring that develops naturally out of λ-choosability. All λ-partitionable graphs are λ-choosable, but the converse is not true. In this dissertation, we characterize all complete k-partite graphs which are only λ-choosable when λ is an integer partition which contains only 1's. We show several constructions of graphs which are λ-choosable but not λ-partitionable. We finally show progress towards constructing a counterexample whose purpose is to highlight a key difference between λ-choosability and λ-partitionability.