GRACO 2005  

Invited speakers
Abstracts of invited talksTelecommunication, graphs, and combinatorial optimizationMartin Grötschel (ZIB and TU Berlin) ABSTRACT: Telecommunication is an area that offers an almost infinite number of opportunities for mathematics. There are, in particular, very many challenging tasks for discrete mathematicians. Some examples: design of devices and network components, location planning, design of network topologies, network capacity planning, traffic routing, interference reduction. From colouring to constraint satisfactionPavol Hell (Simon Fraser) ABSTRACT: I will describe a general problem setup which contains graph colourings, as well as homomorphisms, and general constraint satisfaction problems. The main focus will be on classifying the complexity of these problems according to the structure of the fixed target template. Emphasis will be on the so called "full" problems which correspond to homomorphisms of structures with coloured substructures. Fair bandwidth allocationRichard M. Karp (Berkeley) ABSTRACT: A fundamental goal of Internet congestion control is to ensure fairness by selectively dropping packets from flows that are receiving more than their fair share of bandwidth. The most effective known algorithms for detecting and selectively dropping highrate flows at a router are based on random hashing or random sampling of packets and give only probabilistic guarantees. The known deterministic algorithms either require excessive storage or fail to guarantee fairness. In a simplified theoretical setting we show that the detection and selective dropping of highrate flows can be accomplished deterministically without maintaining an excessive amount of state. Given an arriving stream of packets, each labeled with the name of its flow, our algorithm drops the minimum number of packets required to guarantee that, in every consecutive subsequence of the output stream, no flow has significantly more than its fair share of the packets. On a theorem of LuczakYoshiharu Kohayakawa (Săo Paulo) ABSTRACT: For graphs L1, . . . , Lk, the Ramsey number R(L1, . . . , Lk) is the minimum integer N such that, in any colouring of the edges of the complete graph on N vertices by k colours, there exists a colour i for which the corresponding colour class contains Li as a subgraph. Packings and coverings of odd cyclesBruce Reed (McGill) ABSTRACT: We discuss the relationship between the maximum size of a set of vertex disjoint odd cycles and the minimum number of vertices whose removal leaves the graph bipartite for various special classes of graphs. On the number of colorings of a graphCarsten Thomassen (Technical University of Denmark) ABSTRACT: The chromatic polynomial P(G,k) of a graph G is the number of colorings of G with k available colors. The chromatic polynomial was introduced by Birkhoff in 1912 in order to study the 4Color Problem. Although the chromatic polynomial has not been very successful for coloring problems, it has been studied for several other reasons, primarily by mathematicians but also by physicists. In this talk, some basic properties of the chromatic polynomial will be discussed. Special attention will be given to the case k=5 for graphs on a fixed surface, and the case k=3 for trianglefree planar graphs. 