Predavatelj: Wilfried Imrich
Abstract: Thomas Tucker’s infinite motion conjecture asserts that the vertices of every connected, locally finite graph G can be colored with 2 colors such that the identity automorphism is the only automorphism that respects the coloring under the condition that every automorphism moves infinitely many vertices. We say G is 2-distinguishable if it has infinite motion.
The conjecture is true for many classes of graphs, but it is not known whether it holds for graphs with given maximum degree k, unless k=3.
Such graphs are called subcubic. However, there is evidence that infinite motion is not needed for subcubic graphs and that one can always find a 2-coloring that fixes all vertices with the exception of at most two pairs of interchangeable vertices. We show that this is true for trees, subcubic graphs without small cycles and vertex transitive cubic graphs.
In particular, we show that every subcubic infinite tree is 2-distinguishable and that every finite subcubic tree has a 2-coloring, which fixes all vertices, with the possible exception of two vertices of degree 1 with a common neighbor. We also show that the only vertex or edge-transitive finite or infinite subcubic graphs are the K_4, the K_{3,3} or the cube.
For finite or infinite trees of maximum valence k we show that there is a 2-coloring that fixes all vertices that have no endvertex within distance log_2 k +1 .
Acknowledgement: This joint work with Thomas Lachmann and Gundelinde Wiegel (vertex transitive graphs), Svenja Hüning, Judith Kloas and Hannah Schreiber (trees) and Thomas Tucker.
Speaker: Wilfried Imrich and possibly one of the co-authors.
