Midsummer Combinatorial Workshop XIX

July 29 - August 2, 2013, Prague

List of lectures

Peter CameronSynchronizing Automata
Geňa HahnCops and Robers on infinte graphs
Maria AxenovichClumsy Packings
Dan KráľFinitely forcible graphons
Juanjo Rué PernaThe probability of planarity of random graph near the critical point
Steve ButlerTwo of my favorite problems
Delia Garijo RoyoA red-blue intersection problem
Jirka FinkOptimization problems in smart grids
János BarátList Hadwiger conjecture and extremal K5-minor free graphs with fixwd girth
Leo van IerselReconstructing phylogenetic networks
Sandi KlavžarDomination Game
Dominique AndresPerfect digraphs: answers and questions
Yared NigussieProblems on K6-minor free graphs
Ondřej SuchýParametrized complexity of directed Steiner tree on sparse graphs
Robert ŠámalHedetniemi for \vartheta
Hans Raj TiwaryExtension complexity of combinatorial polytopes
Andrew GoodallGraph polynomials from graph homomorphisms
Dragan Mašulovic'The arithmetic of the random poset
Silvia GagoBoundary value problems on weighted paths
Ramiro Feria-PuronOn the degree-diameter problem for graphs on surfaces
Wiaslaw Kubis'Katětov expanders
Michael PayneGeneral position subset selection
Ross KangArrangements of pseudocircles and circles
Tamás KirályOpen questions on matroids and list colouring
Anita A. SillasenExistence of friendship hypergraphs
Friday START AT 9:00
Vít JelínekSplittability of Permutation Classes
Hossein HajiabolhassanGraph homomorphism through graph powers
Snjezana MajstorovicSpectrum of modularity matrix of graphs
Michel PocchiolaArrangements of ribbons
Andrea JimenezCubic vertices in min bricks
Jozsef SolymosiTBA
Peter L. ErdosRealization of restricted degree sequences
Krzysztof ChoromanskyTBA


We kindly ask all speakers to send us a short note with overview of their talk. The note should be written in standard (La)TeX. The lenght should be one to two A4 pages.

Please, send your note as soon as possible (not later than 30. 8. 2013) to Dušan Knop (knop at kam.mff.cuni.cz). All notes will be published in KAM-DIMATIA Series.

First announcement

The workshop continues the tradition of Prague Combinatorial Workshops held since 1993. Oriented on problems of all fields of graph theory, combinatorics and discrete geometry, it will continue in the spirit and informal working atmosphere of the previous meetings.

The workshop takes place at DIMATIA and the Department of Applied Mathematics of Charles University, Malostranske namesti 25, Prague 1, which is located in a historic building in the center of Old Prague. The workshop is also supported by Computer Science Institute of Charles University.

The workshop participation is by invitation only. If in doubt please contact organizers. In case you need an invitation letter (for example for your visa), please let us know and we will be happy to write one for you.

The accommodation and part of the meals are provided by the organizers. We will collect a modest fee of EUR 70 towards the expenses.

The program will be determined from day to day. The afternoons are reserved for discussions and other program. If you intend to give a talk, please let us know few days in advance so that we may schedule Monday program.


The workshop starts every day in the morning at 9:30, there will be up to 5 roughly 30 minute talks and a coffee break roughly at 10:30. The morning program ends before 1 p.m. and is followed by a lunch. Afternoons are reserved for individual discussions and problem solving.

The schedule of the Tuesday – Friday talks will be decided on Monday, you are welcome to give (preferably a problem-oriented) talk. Only the title is required, the abstracts will be collected afterwards for the workshop booklet. We will also collect transparencies (if any).

The registration starts on Monday at 9:00 in the hallway of 2nd floor, just in front of lecture room S5. The talks will begin around 9:30 in S5. If you arrive later, please register with Mrs. Nana Giorgadze (KAM and IUUK secretary, room 222).

On Wednesday afternoon, there will be an awesome social event. We will visit the Klementinum library, see the map of important places.


All e-mail correspondence concerning the workshop (e.g. registration and accommodation booking) should be directed to mcw2013@kam.mff.cuni.cz.

Senior organizers: Jan Kratochvíl, Jaroslav Nešetřil, Pavel Valtr

Junior organizer: Dušan Knop


We have reserved accommodation in the following hotels:

Travel info (public transport)

For the public transportation you can buy a 90-minute ticket for 32 CZK or 30-minute for 24 CZK in a newsstand or in a vending machine. You have to validate it (in a magic yellow validating machine with a shining arrow) as you enter the (first) tram or bus or as you enter the subway zone.

For connection searching, use site http://www.dpp.cz. Stop of the department is Malostranske namesti, the Prague airport is Terminal 2 and the main train station is Hlavni nadrazi.

Modified: 26. 08. 2013