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


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.