The seminar was devoted to the most important recent developments in the area of graph colorings. A non-expert definition of graph coloring is the following: We want to color several objects with the smallest possible number of colors, subject to collision constraints that forbid that some pairs of objects receive the same color. The definition for experts is quite similar, but one has to replace the word "objects" by "vertices of a graph", and "collision constraints" by "edges". The basic graph coloring problem is computationally intractable (NP-hard), and for that reason the combinatorics of graph colorings is quite messy and complicated and hard to handle, and it leads to many fascinating questions.

Over the last three decades, researchers in Discrete Matematics, in Combinatorial Optimization, and in Theoretical Computer Science have spent considerable effort on understanding the combinatorics and the computational complexity of various graph coloring problems. There are many reasons for this.

• Graph colorings are ubiquitious in the modelling of real world applications. For instance, they show up as frequency assignment problems in telecommunication; they show up as machine assignment problems in production scheduling; they show up as register allocation problems in operating systems etc, etc, etc.
• Most graph coloring problems are very easy to formulate, very easy to grasp, and very difficult to solve. Some graph coloring problems constitute attractive puzzles.
• Graph coloring problems form a keystone in the testing of various algorithmic approaches, like local search approaches, genetic algorithms, simulated annealing, Markov chain approaches, and so on. Computationally, graph coloring problems belong to the most difficult problems. Hence, if an algorithmic approach works out well for graph colorings, we expect it to work out well for many other algorithmic problems as well.
• Graph colorings show up in an incredible variety of forms. Just to name a few: There are lambda-colorings (= colorings with a condition at distance two in frequency assignment); alpha-colorings, sub-colorings, list-colorings, f-colorings, precoloring extensions, colorings with forbidden subgraphs, graph homomorphisms, Ramsey colorings, role assignments, equitable colorings, etc etc etc. Also all kinds of morphisms from structures into structures fall into this area.

The Dagstuhl workshop on graph colorings was attended by 45 particpants with affiliations in 17 countries (Austria, Canada, Czech Republic, Denmark, England, France, Germany, Malta, Netherlands, Norway, Poland, Slovakia, Slovenia, Spain, Sweden, Switzerland, USA).

All in all there were 29 scientific presentations. We decided right in the beginning to have a so-called "liquid" schedule: There are no fixed time slots; every speaker is allowed to talk as long as s/he likes; if questions come up in the middle of the talk, then the speaker may switch topic and discuss these questions. For every day, we only fixed a rough list of speakers; this list was flexible, and sometimes we had to remove the last speaker of the day and make him the first speaker of the following day. We also moved the coffee-breaks a lot. Here are the lists of speakers for the five days:

• Monday: Jiri Sgall, Dieter Kratsch, Roland Häggkvist, Jiri Fiala, Fedor Fomin, Andrei Bulatov, Jan Arne Telle
• Tuesday: Josep Diaz, Gasper Fijavz, Pavol Hell, Daniel Kral, Leslie Goldberg, Andreas Brandstaedt
• Wednesday: Winfried Hochstättler, Douglas West, Sascha Kostochka, Riste Skrekovski, Martin Skoviera
• Thursday: Arie Koster, Ivo Bloechliger, Andrei Krokhin, Dmitry Kozlov, Haiko Müller, Daniel Paulusma, Marc Noy
• Friday Alastair Farrugia, Oriol Serra, Van Bang Le, Jan van den Heuvel

On Tuesday evening and on Wednesday evening, we had open problem sessions. We are currently collecting these open problems, and we will add the resulting open problem list to a special issue of the journal "Theoretical Computer Science" that will be devoted to the "2003 Dagstuhl Seminar on Graph Colorings". We expect this special issue to appear in spring or summer 2005.

On Wednesday afternoon, there was a long hike through the woods around Dagstuhl. On Wednesday evening, Winfried Hochstättler amazed us with a demonstration on the German art of blackboard cleaning. Every evening, we had a lot of wine-and-cheese, and once the cheese was gone, we switched to wine-and-beer.

The meeting was held in a very pleasant and stimulating atmosphere. Thanks to everyone who made it a very interesting and enjoyable event! Thanks to the Dagstuhl office and to the local personnel for the efficient and competent support in all matters!