BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Distinguishing numbers of infinite graphs with bounded degrees Lehner, Florian


A graph is said to have infinite motion, if every automorphism moves infinitely many vertices. Tucker's Infinite Motion Conjecture asserts that if a locally finite graph has infinite motion, then there is a 2-colouring of its vertex set which is only preserved by the identity automorphism. We show that this is true for graphs whose maximum degree is at most 5. In case the maximum degree is 3, we can even drop the assumption of infinite motion. Coauthors: M. Pilsniak, M. Stawiski

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International