Graph Theory 2011

at Hotel Koldingfjord, Kolding, Denmark

Kolding, Denmark map              photo from the air of Kolding

Thursday April 28 - Sunday May 1,  2011

This is the web page for the meeting Graph Theory 2011to be held at Hotel Koldingfjord in Kolding, Denmark, April 28 - May 1, 2011.

The hotel building was built exactly one hundred years ago as a sanatorium for children (paid by funds originating from the sale of special Christmas stamps). The building was used as a hospital until 1988.

Kolding is situated close to Lillebælt (the small belt between Jutland and Funen), and it is accesible by train, both from the south (Hamburg) and the east (Copenhagen). If you travel by plane then Copenhagen Airport (2 hours and 50 minutes by train from Kolding) and Billund Airport (1hour and 10 min. by Bus 406 from Kolding) are the best possibilities.

There are trains from the airport in Copenhagen at 14:38 (15:38 etc.) arriving in Fredericia at  17:06 (18:06  etc.) , change in Fredericia to train to Kolding at 17:13 (18:13 etc.) arriving at 17:28 (18:28 etc.)
There are many trains from the airport in Copenhagen  to Copenhagen Main Station (for example 2 minutes past the hour) and from the main station there are trains directly to Kolding at 30 minutes past the hour, arriving in Kolding 130 minutes later.

From the airport in Billund there is a direct busline to Kolding (Bus 406) taking 70 minutes for the trip. Busses leave the airport at 14:05, 15:15, 15:40, 16:45, 18:10 and 22:00.

The conference site (Hotel Koldingfjord) is not within walking distance from the railwaystation in Kolding. A taxi from the railwaystation to the hotel charges around 150 DKK ( 1 EURO = 7.58 DKK; 1 US$ = 5.36 DKK).

The meeting will start in the evening of Thursday April 28 at 20:00 with a problem session. There is no dinner arranged for Thursday evening, but there will be sandwiches, softdrinks and beer available from around 18:00. Please think of a good problem to present.

The meeting will finish with lunch (starting at 12:30) on Sunday May 1.

Conference topics

Confirmed Participants


Preliminary program

Day of arrival.
There will be sandwiches, soft drinks and beer available from around 18:00.
20:00-22:00 Problem session (chair: Adrian Bondy).

09:00-09:30  Barát: Edge-decompositions of graphs into copies of a tree
09:35-10:05  Osthus: Edge-disjoint Hamiltonian cycles in graphs and digraphs
10:10-10:40  Trotignon: Decomposition theorems for classes of graphs defined by constraints on connectivity
11:10-11:40  Jackson: Rigidity of bar-and-joint frameworks in 3-space
11:45-12:15  Jordan: Geometric sensitivity of rigid graphs

12:30 Lunch

15:00-15:30  Kawarabayashi: Graph Minor Algorithm with the parity condition
15:40-16:10  Szegeti: An Excluded Minor Characterization of Seymour Graphs
16:20-16:50  Wullf-Nielsen: Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications
17:20-17:50  Kühn: Sumner's universal tournament conjecture
18:00-18:30  Thomassé: Disjoint Circuits in Tournaments, beyond the Bermond-Thomassen bound

19:00  Dinner

09:00-09:30  Bondy: Switching Reconstruction of Digraphs and Coloured Graphs and Related Problems
09:35-10:05  Král: Exponentially many perfect matchings in cubic bridgeless graphs
10:10-10:40  Pfender: Complete subgraphs in multipartite graphs
11:10-11:40  Brandt: Structural description of dense graphs with large odd girth
11:45-12:15  Open

12:30 Lunch
14:00-15:00  Boattrip

16:00-16:30  Esperet: A complexity dichotomy for the coloring of sparse graphs
16:40-17:10  Raspaud: (k,j)-colorability of sparse graphs
17:20-17:50  Yeo: 2-Colorings in k-regular k-uniform Hypergraphs and Cycles in Digraphs

19:00  Conference dinner

SUNDAY MAY 1, 2011
10:00-10:30  Rautenbach: The Potential of Greed in Independence
10:40-11:10  Plummer: Extendable structures in graphs
11:20-11:50  Stiebitz: Orientations of graphs with prescribed weighted out-degrees

12:30 Lunch

Departure from Koldingfjord


On Saturday there is an extended lunch break. It may be used for a one hour boattrip on the fjord, starting at 14:00 from the boat-landing-bridge of the hotel. Alternatively, the art and design museum Trapholt is within walking distance (between 1 and 2 kilometers) from the hotel. And very close by you have the Museum of Nursing (which like the hotel was also originally part of the Childrens Sanatorium, this part of it for small children). The Museum of Nursing is today part of the University of Southern Denmark.


The meeting will start in the evening of Thursday April 28 with a problem-session. We ask participants to bring good problems to present and discuss during the meeting. (There will be no common dinner in the evening of April 28, but sandwiches and softdrinks/beer will be available from around 18:00).

Best regards
Jørgen Bang-Jensen, Marco Chiarandini, Matthias Kriesell Bjarne Toft
IMADA, The University of Southern Denmark.
Last updated:  April 27, 2011