TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 03391

Graph Colorings

( Sep 21 – Sep 26, 2003 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/03391

Organizers




Summary

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!


Participants
  • Karen Aardal (Georgia Institute of Technology, US) [dblp]
  • Jorgen Bang-Jensen (University of Southern Denmark - Odense, DK)
  • Ivo Bloechliger (EPFL - Lausanne, CH)
  • Andreas Brandstädt (Universität Rostock, DE) [dblp]
  • Graham R. Brightwell (London School of Economics, GB)
  • Andrei A. Bulatov (Simon Fraser University - Burnaby, CA) [dblp]
  • Maurice Cochand (ETH Zürich, CH)
  • Victor Dalmau (UPF - Barcelona, ES) [dblp]
  • Josep Diaz (UPC - Barcelona, ES)
  • Alastair Farrugia (University of Malta, MT)
  • Dmitry Feichtner-Kozlov (KTH Royal Institute of Technology, SE) [dblp]
  • Jiri Fiala (Charles University - Prague, CZ)
  • Gasper Fijavz (University of Ljubljana, SI)
  • Fedor V. Fomin (University of Bergen, NO) [dblp]
  • Leslie Ann Goldberg (University of Warwick - Coventry, GB) [dblp]
  • Roland Häggkvist (University of Umeå, SE)
  • Pavol Hell (Simon Fraser University - Burnaby, CA) [dblp]
  • Winfried Hochstättler (BTU Cottbus, DE) [dblp]
  • Tommy R. Jensen (Royal Holloway University of London, GB)
  • Bettina Klinz (TU Graz, AT)
  • Bernhard Korte (Universität Bonn, DE)
  • Arie Koster (Konrad-Zuse-Zentrum - Berlin, DE)
  • Alexandr V. Kostochka (University of Illinois - Urbana Champaign, US)
  • Daniel Král' (Charles University - Prague, CZ) [dblp]
  • Dieter Kratsch (University of Metz, FR) [dblp]
  • Andrei Krokhin (Durham University, GB) [dblp]
  • Sven O. Krumke (TU Kaiserslautern, DE)
  • Van Bang Le (Universität Rostock, DE) [dblp]
  • Tomasz Luczak (Adam Mickiewicz University - Poznan, PL) [dblp]
  • Haiko Müller (University of Leeds, GB) [dblp]
  • Jaroslav Nešetril (Charles University - Prague, CZ) [dblp]
  • Marc Noy (UPC - Barcelona, ES) [dblp]
  • Daniel Paulusma (University of Twente, NL) [dblp]
  • Bert Randerath (Universität Köln, DE)
  • Oriol Serra (UPC - Barcelona, ES)
  • Jiri Sgall (Czech Academy of Sciences - Prague, CZ) [dblp]
  • Martin Skoviera (Comenius University in Bratislava, SK)
  • Riste Skrekovski (Charles University - Prague, CZ)
  • Jan Arne Telle (University of Bergen, NO) [dblp]
  • Dimitrios M. Thilikos (UPC - Barcelona, ES) [dblp]
  • Jan van den Heuvel (London School of Economics, GB) [dblp]
  • Margit Voigt (TU Ilmenau, DE)
  • Jens Vygen (Universität Bonn, DE) [dblp]
  • Douglas West (University of Illinois - Urbana Champaign, US)
  • Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]