A Computational Approach for Finding 6-List-Critical Graphs on the Torus
Félix Moreno Peñarrubia
Charles University and UPC
May 11, 2023, 12:20 in S6
Abstract
Coloring problems on graphs embedded on surfaces is an old and
well-studied area of graph theory. Thomassen proved that there are finitely
many 6-critical graphs on any fixed surface and provided the explicit list
of 6-critical graphs on the torus. Later, Postle proved that there are
finitely many 6-list-critical graphs on any fixed surface. With the goal of
finding the list of 6-list-critical graphs on the torus, we develop and
implement algorithmic techniques for computer search of critical graphs in
different list-coloring settings.