Although not the first graph theory conference in the world (there were symposia on graph theory in Budapest 1958, Halle/Saale 1960 and Liblice 1961), the symposium in Smolenice is considered to be the world's first international meeting on graph theory, with the presence of both Western and Eastern mathematicians. It was organised by the Czechoslovak Academy of Sciences, being held from 17th to 20th June 1963. The programme consisted of six half-day sessions, with two sessions devoted to discussions on new problems in graph theory. In total, 31 problems were presented there (three of them were solved shortly after the conference by Erdõs, Gallai, Hajnal and Moon). It is worth mentioning that several problems posed in Smolenice Symposium (partially transformed below into modern graph theory language) had a large impact on the future development of graph theory.

Problem 2 (Ádám's Conjecture): For each finite directed graph, there exists a directed edge whose reversal decreases the total number of directed cycles.

The conjecture was disproved in general by Thomassen in 1987.

Problem 20 (presented by A. Kotzig): For each positive integer n, there exists a decomposition of the complete 2n-vertex graph into 1-factors such that the union of any two of those 1-factors is a Hamiltonian cycle.

The problem is still open in general.

Problem 25 (Ringel's Conjecture): For each tree T with n edges, there exists a decomposition of the complete (2n+1)-vertex graph into 2n+1 subgraphs which are all isomorphic to T.

The problem is still open in general.

Problem 27 (presented by J. Sedláček): Find a characterisation of magic graphs; find out whether every magic graph has a prime-valued magic valuation.

Two different characterizations of magic graphs were given by Jezný and Trenkler in 1983
and by Jeurissen in 1988, while the second question is still open.

Problem 30 (presented by A.A. Zykov): For a given graph H, determine all graphs G (or all finite graphs, respectively) such that all the subgraphs induced by neighbourhoods of vertices of G are isomorphic to H.

The problem was proved to be algorithmically undecidable by Bulitko in 1973.

The proceedings of the Smolenice Symposium were published in 1964 jointly by Academia, Prague and Academic Press, New York. It comprises, besides the presented problems, 12 lectures, 9 communications and 64 pages of graph theory bibliography.

© 2012 Institute of Mathematics, Faculty of Science, P. J. Šafárik University, Košice | design © 2012 Somsak