[DMO] Clément Legrand-Duchesne: The structure of quasi-transitive graphs

10 November 2023 14:00 till 15:00 - Location: Lecture Hall G, 36.HB.00.230 | Add to my calendar

An infinite graph is quasi-transitive if its vertex set has finitely many orbits under the action of its automorphism group. We obtain a structure theorem for locally finite quasi-transitive graphs avoiding a minor, which is reminiscent of the Robertson-Seymour Graph Minor Structure Theorem. As applications of this result, we prove that every locally finite quasi-transitive graph attains its Hadwiger number, that is, if such a graph contains arbitrarily large clique minors, then it contains an infinite clique minor. This answers a question of Thomassen from 1992. We also prove the minor-excluded case of a conjecture of Ballier and Stein (2018) on the domino problem.