Martin Milanič (FAMNIT UP, Slovenija): On the plane-width of graphs

Datum objave: 9. 11. 2009
Seminar za teorijo grup in kombinatoriko
Četrtek, 12. 11. 2009, od 17h do 19h, učilnica 016, Pedagoška fakulteta Univerze v Ljubljani
Povzetek: Map the vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least a unit distance apart. The plane-width of a graph is the minimum diameter of the image of the vertex set over all such mappings. The plane-width of complete graphs has previously appeared in the literature in different contexts, for example in packing unit discs in the plane so as to minimize the maximum distance between any two disc centers. In this talk we will present some results about the plane-width of general graphs. We will establish a relation between the plane-width of a graph and its chromatic number. The plane-width of K_4 is known to be sqrt(2); we will show how to extend this result to all odd wheels. Using the notion of the circular chromatic number, we will discuss how one can construct sequences of k-chromatic graphs whose plane-widths converge to the maximum plane-width of (k-1)-chromatic graphs, or k = 4,5 or 8. We will conclude the talk by investigating how plane-width behaves under various graph operations and by discussing some generalizations. The talk is based on joint work with Marcin Kaminski and Paul Medvedev.