DMS Combinatorics Seminar

Speaker: Evan Leonard

Title: Refined Choosability and Tightly Colorable Graphs

Abstract: Two similar yet distinct problems in graph theory are determining if a graph is k-colorable and determining if a graph is k-choosable for some positive integer k. An integer partition λ of k is a multiset of positive integers whose sum is k. Xuding Zhu describes a refinement of choosability using integer partitions which houses k-colorability and k-choosability in the same framework and reveals a complicated hierarchy of choosability between the two. A graph is tightly k-colorable if it is λ-choosable only when λ is k copies of 1. All tightly k-colorable complete k-partite graphs are characterized.