Workshop on Graph colorings and their generalizations

Budapest, Hungary, April 21-22, 2005

Workshop on Combinatorial search

Budapest, Hungary, April 23-26, 2005

The first workshop is the third meeting of Group III of DIMACS/DIMATIA/Renyi Tripartite Partnership

The second workshop is part of FIST Marie Curie Host Fellowship for the Transfer of Knowledge project supported by the European Community

Organizing committee

Information for participants


We have booked rooms for those participants who asked us to at
Ibis Budapest Centrum , located near Kálvin tér, approximately 10 minutes walk from the Institute. The price is 88,25 Euros/night with breakfast. You can find information on getting to the hotel on their homepage, on getting to the Institute here.

Registration, banquet

There is no registration fee for the workshops.

A banquet for the participants of both conferences will be held on the 22th, Friday. Its cost will be paid on the spot. For details please return later.


There are machines in the guest rooms, at the entrance of the library and on the 3rd floor. Each participant is assigned a personal account on our system, since we do not have guest accounts. You'll get your account name and password at the registration. If you bring your laptop, you can connect it to our network via DHCP, either by plugging in to network plug, or by a wireless card.

Opening hours

The Institute is open Sunday from 8:30 till about 7:00 P.M., weekdays from 7:30 A.M. till 8:00 P.M.


You will be able to use the library, but only for reading there, unfortunately, you will not be able to borrow books.


April 21, Thursday

10:00 Fred Roberts On Balanced Signed Graphs and Consistent Marked Graphs
10:50 coffee break
11:10 Daniel Kral Channel assignment problem with variable weights
11:35 Bill Cuckler TBA
12:00 Lunch
14:00 Zsolt Tuza Unique colorings of mixed hypergraphs
14:25 Mariusz Wozniak General neighbour-distinguishing index of a graph
14:50 coffee break
15:10 Gábor Simonyi Circular, local, and wide colorings
15:35 Attila Sali Color critical hypergraphs and forbidden configurations

April 22, Friday

10:00 Martin Loebl Jamming and geometric representations of graphs
10:50 coffee break
11:10 János Barát TBA
11:35 Peter Mihok Critical graphs in generalized graph colourings
12:00 Lunch
14:00 Mieczyslaw Borowiecki Game generalize colouring
14:25 Ela Sidorowicz Game list colouring of graphs
14:50 coffee break
15:10 Gábor Tardos The local chromatic number of quadrangulations of surfaces
15:35 Robert Samal Tension-continuous mappings

April 23, Saturday

10:00 Rudolf Ahlswede Identification entropy
10:50 Zsuzsanna Lipták Searching for submasses in weighted strings
11:20 coffee break
11:40 Ferdinando Cicalese A New Strategy for Querying Priced Information
12:10 Miklós Ruszinkó TBA
13:00 Lunch

April 25, Monday

10:00 Stefan Dodunekov Optimization problems in coding theory
10:50 coffee break
11:10 Anatolij Zhigljavsky Probabilistic existence theorems for nonadaptive search with lies
11:40 Gregory Kabatyansky TBA
12:10 Lunch
14:00 Christian Deppe Q-ary search with lies and/or localized errors
14:30 Tsonka Baycheva Linear covering codes
15:00 coffee break
15:20 István Nagy TBA
15:50 Open problems, discussion

April 26, Tuesday

10:00 Volodia Lebedev Uniqueness of some optimal cover-free codes
10:30 Rossitza Dodunekova Proper and good error-detecting codes
11:00 coffee break
11:20 Gyula O. H. Katona When the lie depends on the target
12:00 Lunch
14:00 Open problems, discussion

List of participants

  • Rudolf Ahlswede
  • Martin Aigner
  • Gábor Bacsó
  • Attila Balogh
  • Imre Bárány
  • János Barát
  • Tsonka Baycheva
  • Mieczyslaw Borowiecki
  • Ferdinando Cicalese
  • Bill Cuckler
  • Peter Damaschke
  • Annalisa De Bonis
  • Christian Deppe
  • Stefan Dodunekov
  • Rossitza Dodunekova
  • Aneta Dudek
  • Gábor Elek
  • Péter Erdős L
  • Dániel Gerbner
  • András Gyárfás
  • Ervin Győri
  • Mihály Hujter
  • Gregory Kabatyanski
  • Marcin Kaminski
  • Gyula Katona O.H.
  • Balázs Keszeg
  • Zoltán Király
  • Ákos Kisvölcsey
  • János Komlós
  • Daniel Kral
  • Brenda Latka
  • Volodia Lebedev
  • Zsuzsanna Lipták
  • Martin Loebl
  • Philip Matchett
  • Péter Mihók
  • Dezső Miklós
  • Daniele Mundici
  • István Nagy
  • Jaroslav Nesetril
  • Huu Hoi Nguyen
  • Dömötör Pálvölgyi
  • Balázs Patkós
  • Monika Pilsniak
  • Michael Richter
  • Fred Roberts
  • Miklós Ruszinkó
  • Attila Sali
  • Robert Samal
  • Ela Sidorowicz
  • Miklós Simonovits
  • Gábor Simonyi
  • Vera T. Sós
  • Gábor Tardos
  • Zsolt Tuza
  • Gábor Wiener
  • Mariusz Wozniak
  • Anatolij Zhigljavsky
  • Irmina Ziolo

    If you are interested in participating, please contact us at


    The event is supported by the 6th NSF, OTKA, the Hungarian Academy of Sciences and the European Community's 6th Framework Programme (through our FIST project)

    Mailing Address:

    Alfréd Rényi Institute of Mathematics,
    Hungarian Academy of Sciences
    POB 127
    H-1364 Budapest, Hungary

    Phone:(36 1) 483 8300
    Fax: (36 1) 483 8333