Discrete Mathematics 308 (2008) 1347 – 1349
www.elsevier.com/locate/discPrefaceThis volume contains papers solicited from talks presented at the third European Conference on Combinatorics, Graph
Theory and Applications (EuroComb05) held in Berlin, September 5–9, 2005. The contributions for the conference
were selected by the Program Committee, consisting of the following colleagues:• Graham Brightwell (London)• Reinhard Diestel (Hamburg)• Stefan Felsner (Berlin)• András Frank (Budapest)• Gil Kalai (Jerusalem)• Christian Krattenthaler (Lyon)• Monique Laurent (Amsterdam)• Tomasz Łuczak (Posnan)• Jaroslav Nešetřil (Prague)• Alexander Pott (Magdeburg)• Oriol Serra (Barcelona)• Carsten Thomassen (Lyngby)• Emo Welzl (Zürich)
Abstracts were published as volume AE in the proceedings series of the electronic journal Discrete Mathematics& Theoretical Computer Science (DMTCS). The contributions to this volume mostly consist of ﬁnal versions of a
selection of papers presented at EuroComb05. Some of the authors have submitted a follow-up to the work presented
at the conference.
Most of the papers we collected in this volume have a distinct algorithmic ﬂavor, and all of them are connected tograph theory in its broadest sense. Several articles relate to applications either in practice or in other areas of discrete
mathematics. The papers by Kang, Mueller, and Sereni; by Gonçalves; and by Golumbic, Lipsteyn, and Stern are
motivated by the design of communication networks. These applications usually deal with coloring problems, variantsof which are also the topic of papers by Barjas and Serra and by Alon and Grytczuk, both in a more structural setting,and also by Bartnicki, Grytczuk, and Kierstead in a game theoretic interpretation. The active area of combinatorial
optimization is represented in this volume via papers by Makai and Pap, who generalize and unify classical theorems, andby Zaragoza, who settles a graph theoretic conjecture.Approximation algorithms are treated by Manic and Wakabayashi.
Lee and Streinu use algorithms (games) to obtain a graph theoretic characterization. Extremal combinatorics is treatedin the paper by Tarui and in a hypergraph context in the paper by Frankl and Kantona.
We thank all members of the Program Committee and all our reviewers for their commitment and support, enabling
us to see this volume completed for submission to the publisher close to one year after the conference. We also take theopportunity to thank the Organizing Committee and all the persons who have helped run the conference in a smoothand very pleasant way.

0012-365X/$ - see front matter © 2007 Elsevier B.V. All rights reserved.
doi:10.1016/j.disc.2007.09.029

1348

S. Felsner et al. / Discrete Mathematics 308 (2008) 1347 – 1349

The conference and the publication of this volume was made possible by the support of the Deutsche Forschungsgemeinschaft (DFG) and the European Research and Training Network COMBSTRU.
Invited talks at EuroComb05 were given by• Ron Aharoni (Technion, Haifa)
Menger’s theorem for inﬁnite graphs• Mireille Bousquet-Mélou (LaBRI, Bordeaux)
On the shape of binary trees• Hein van der Holst (TU Eindhoven)Some recent results in topological graph theory• Nati Linial (Hebrew University, Jerusalem)
Lifts of Graphs• László Lovász (Microsoft Research and Eötvös Loránd University)
Graph Algebras• Bruce Reed (McGill, Montréal)
The Evolution of The Mixing Time
• Alexander Schrijver (CWI, Amsterdam)
New code bounds with noncommutative algebra and semideﬁnite programming• Madhu Sudan (MIT, Cambridge)
Modelling errors and recovery for communication• Gábor Tardos (Rényi, Budapest)
Toward an extremal theory of ordered graphs• Günter M. Ziegler (TU Berlin)
On the Complexity of Space Tilings

European Prize in Combinatorics awarded
The European Prize in Combinatorics was established by the European Research and Training Network COMBSTRU
and by the center DIMATIA to recognize excellent contributions in combinatorics by young researchers, not older than35. It is awarded biannually in conjunction with the EuroComb meeting. The prize was awarded for the second time atEuroComb05, carrying a monetary award of 2500 Euros. The prize was funded with contributions from DIMATIA andCOMBSTRU.
The Prize Committee consisted of Martin Aigner (Berlin), Peter Cameron (London), and Jaroslav Nešetřil (Prague).
The prize was awarded to Dmitry Feichtner–Kozlov for deep combinatorial results obtained by algebraic topology
and particularly for the solution of a conjecture of Lovász.
Stefan Felsner, Marco Lübbecke, Jarik NešetřilBerlin and Prague, December 2006

S. Felsner et al. / Discrete Mathematics 308 (2008) 1347 – 1349

1349