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 rchromatic 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)
