5th Workshop on the Matthews-Sumner Conjecture and Related Problems

Domazlice, October 6-10, 2008

After the workshop

Slides to all the talks are available:

• Hajo Broersma: Any conjecture will do: a warming-up survey
• Roman Cada: 2-connected claw-free graphs are prism-hamiltonian
• Tomas Kaiser: Three problems on dominating cycles
• Roman Kuzel: 2-edge-Hamilton connectivity in 4-connected line graphs
• Hao Li: Cyclability in graphs (PDF version here)
• Edita Macajova: Hypohamiltonian cubic graphs
• Arthur Hoffmann Ostenhof: A counterexample to the Bipartizing Matching Conjecture
• Moshe Rosenfeld: Cubic subgraphs: Why? Why not? (PDF version here)
• Zdenek Ryjacek: Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs
• Ingo Schiermeyer: Forbidden induced subgraphs and colourings
• Jakub Teska: 3-trestles in 2-connected claw-free graphs
• Petr Vrana: Compatible mappings and the Dominating Cycle Conjecture for snarks
• Kiyoshi Yoshimoto: On 2-factors of claw-free graphs
• Bing Wei: Some results on paths and cycles in claw-free graphs

Articles about the event appeared in the local newspaper Domazlicky denik (English translation here) and in Klatovsky denik.

Many thanks to all the participants for their contribution to the inspiring atmosphere of the workshop.

About the workshop

The workshop was focused on problems and results related to the celebrated Matthews-Sumner Conjecture whose equivalent forms assert:

• Every 4-connected claw-free graph is hamiltonian. (Matthews, Sumner 1984)
• Every 4-connected line graph is hamiltonian. (Thomassen 1984)
• Every cyclically 4-edge-connected cubic graph has either a 3-edge-colouring or a dominating cycle. (Fleischner 1984)
• Every cyclically 4-edge-connected cubic graph has a dominating cycle. (Ash and Jackson 1989)

Topics within the scope of the workshop included:

• Hamiltonian properties of line graphs and claw-free graphs
• Forbidden induced subgraphs
• Closure operations, contractibility, collapsibility
• Graph toughness
• Cubic graphs, snarks

The event was the fifth in a series of workshops held in Nectiny (1999 and 2000), Hannover (2002) and Hajek (2003).

Location and dates

Domazlice is a charming town about 50 kms southwest of Pilsen (see here for some photos). The workshop began with lunch on October 6 (noon) and ended with lunch on October 10. It took place in the hotel Sokolsky dum on the main square of Domazlice.

Accommodation was arranged in Sokolsky dum and two hotels situated very close to it:

• Penzion U Chodskeho hradu
• Pension Family

Participants

The workshop (which was by invitation only) was attended by the following participants:

Ljiljana Brankovic	Hajo Broersma	Igor Fabrici	Ralph Faudree
Evelyne Flandrin	Herbert Fleischner	Grzegorz Gancarzewicz	Arthur Hoffmann Ostenhof
Heinz Jung	Jan Kratochvil	Hao Li	Edita Macajova
Mirka Miller	Jaroslav Nesetril	Daniel Paulusma	Moshe Rosenfeld
Joe Ryan	Ingo Schiermeyer	Bing Wei	Kiyoshi Yoshimoto

plus the Pilsen group:

Zdenek Ryjacek	Jan Brousek	Roman Cada	Jan Ekstein
Ruslan Gumerov	Premysl Holub	Tomas Kaiser	Roman Kuzel
Ondrej Rucky	Khikmat Saburov	Milena Sebkova	Radek Sliva
Jakub Teska	Libuse Teskova	Petr Vrana

Organizers

The workshop was organized by the Department of Mathematics at the University of West Bohemia in Pilsen. Support from the Research Plan MSM 4977751301 of the Czech Ministry of Education, and from the Institute for Theoretical Computer Science (ITI), is gratefully acknowledged.

The organizing committee was chaired by Zdenek Ryjacek. For additional information, please email to ryjacek [@] kma [.] zcu [.] cz.