Host Institution:

La Trobe University

Title of Seminar:

Crossings and colourings: beyond the 5 colour theorem

Speaker's Name:

Dr János Barát

Speaker's Institution:

Monash University

Time and Date:

Friday 21 October, 2011, 2:30 PM AEDT

Seminar Abstract:

A graph is planar, if it can be drawn in the plane without edge crossings. It follows from the Euler formula, that any planar graph has a vertex of degree at most 5. Therefore, using a greedy colouring algorithm, we can trivially colour the vertices of a planar graph by 6 colours. It is still easy to prove that 5 colours suffice. What happens if we allow some edge crossings in the drawing? Can we still 5 colour the vertices? Is there any connection between the minimum number of crossings  in a drawing of a graph G and its chromatic number? Both of these graph parameters are hard to compute. Still, Mike Albertson formulated a conjecture that for any r-chromatic G, the crossing number of G is at least the crossing number of K_r, the complete graph on r vertices. This conjecture is a weakening of Hajos conjecture and it includes the 4 colour theorem as a subcase. We will show that this conjecture follows from some known results up to a factor of 4. It is also true for r at most 16, despite the fact that we only know the crossing number of K_r for r at most 12.

This is joint work with Geza Toth (Renyi Institute, Budapest, Hungary)

Seminar Convenor:

This e-mail address is being protected from spambots. You need JavaScript enabled to view it

AGR IT support:

This e-mail address is being protected from spambots. You need JavaScript enabled to view it