Events

DMS Combinatorics Seminar

Time: Nov 17, 2022 (02:00 PM)
Location: 328 Parker Hall

Details:

leonard.jpg

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.