Abstract | ||
---|---|---|
A colouring of a graph G is called distinguishing if its stabilizer in Aut G is trivial. It has been conjectured that, if every automorphism of a locally finite graph moves infinitely many vertices, then there is a distinguishing 2-colouring. We study properties of random 2-colourings of locally finite graphs and show that the stabilizer of such a colouring is almost surely nowhere dense in Aut G and a null set with respect to the Haar measure on the automorphism group. We also investigate random 2-colourings in several classes of locally finite graphs where the existence of a distinguishing 2-colouring has already been established. It turns out that in all of these cases a random 2-colouring is almost surely distinguishing. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1017/S0963548313000382 | COMBINATORICS PROBABILITY & COMPUTING |
Field | DocType | Volume |
Null set,Discrete mathematics,Random regular graph,Combinatorics,Nowhere dense set,Random graph,Vertex (geometry),Haar measure,Automorphism,Almost surely,Mathematics | Journal | 22 |
Issue | ISSN | Citations |
6 | 0963-5483 | 1 |
PageRank | References | Authors |
0.39 | 0 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Florian Lehner | 1 | 21 | 7.24 |