About the conference
The 53rd Czech-Slovak Conference Graphs 2018 will take place on May 28-30, 2018 at the Faculty of Mathematics and Physics of Charles University at Malostranské náměstí in Prague. The scope of the conference includes all topics related to graph theory. The conference languages are English, Slovak and Czech; it is recommended to accompany non-English talks with presentations written in English.
The conference continues a long tradition started by the conference in Liblice in 1961.
Information about prices and the registration form can be found on the Registration page, information about submitting the abstract of your talk on the Submissions page. Details about the available options regarding accommodation are to be found on the Accommodation page.
Invited speakers
| Jarek Grytczuk | Thue type problems for geometric graphs |
| A repetition is a finite sequence consisting of two identical blocks. In 1906 Thue proved that there exists a coloring of the integers by three colors such that no segment is a repetition. This result has been recently generalized into many directions leading to new exciting problems. Consider for instance the following question: how many colors are needed to color the plane so that every isometric copy of the integers is colored non-repetitively? It is known that 18 colors are enough and 5 colors are needed. I will present more problems and results of similar type. | |
| Přemysl Holub | Forbidden induced subgraphs |
| (abstract in PDF) | |
| Borut Lužar | Star edge-coloring |
| (abstract in PDF) | |
| Mária Maceková | Computational complexity of 3-coloring problem for claw-free graphs |
| Given an integer k, a k-coloring of a graph G is an assignment of colors 1,...,k to vertices of graph G in such a way that no two adjacent vertices receive the same color. The chromatic number, χ(G), of graph G is the smallest integer k such that G admits a k-coloring. Vertex coloring is the problem of determining the chromatic number of a graph; it is a well-known NP-hard problem. In fact, even determining if a graph is 3-colorable is NP-complete and it remains NP-complete also in the class of claw-free graphs in general. In the talk I will focus on the computational complexity of the problem in the subclasses of claw-free graphs defined by forbidding additional subgraphs. | |
| Martin Pergel | TBA |
| Alexander Rosa | Perfect 1-factorizations |
| A 1-factorization of a graph G is perfect if the union of any two of its distinct 1-factors is a Hamiltonian cycle of G. Some 55 years ago Kotzig conjectured that the complete graph K 2n has a perfect 1-factorization for all positive integers n. | |
| I will present a survey of what is known to-date on perfect 1-factorizations, not only of complete graphs but also of other regular graphs, primarily cubic graphs. | |
Organisers
This year's conference is organised by CE-ITI - Institute for Theoretical Computer Science in cooperation with Czech and Slovak centres of research in graph theory. The local organiser is Conforg, s.r.o.