Algebra seminar in Lincoln on 12 October 2016: talk by Dr Florian Lehner

Florian Lehner (University of Hamburg) florian_lehnerwill speak at the Algebra seminar on Wednesday,  12 October 2016, at 16:30, room JBL0C05 (bldg. 22 on University of Lincoln campus map). He will speak about “Breaking graph symmetries by edge colourings”.

Abstract: An (edge or vertex) colouring of a graph is said to be distinguishing, if it is not preserved by any automorphism apart from the identity. Tucker conjectured that if every automorphism of an infinite locally finite graph moves infinitely many vertices, then there is a distinguishing vertex colouring with 2 colours. While this conjecture has been verified in many special cases it is still wide open in its full generality. Recently, Pilsniak and Broere proposed an analogous conjecture for edge colourings. We prove this conjecture which also implies Tucker’s conjecture for line graphs. We also indicate, why the problem of finding a distinguishing colouring is probably easier for edge colourings than for vertex colourings.

 

Advertisements

One Comment

  1. Posted October 6, 2016 at 22:48 | Permalink | Reply

    Reblogged this on Maths & Physics News.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: