TU Graz Logo

Institute of Geometry

Contact   People   Courses & Exams   Events   Research   Lehramtsstudium  
Research in Graph Theory

This work is centered around the distinguishing number of graphs, which was formally introduced in 1996 by Albertson and Collins. It is the least number of colors needed in a coloring which is not preserved by any non-trivial automorphism. We are investigating the status of Tucker's infinite motion conjecture (a locally finite graph whose non-trivial automorphisms all move infinitely many vertices has distinguishing number 2). We also consider generalisations of Tucker's conjecture, e.g. to endomorphism monoids and graphs which are not locally finite. This research has been carried out in the period 2011–2015, in cooperation with W. Imrich (Univ. Leoben), under the auspices of the Doctoral college Discrete Mathematics which is funded by the Austrian Science Fund.

Additional References