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 | Posets and graphs with geometric representations |
Graphs with geometric representation form a generalization of intersection graphs, i.e., graphs having such a representation that each vertex is represented by a set and an edge in a graph corresponds to the fact that the appropriate sets have a nonempty intersection. As each graph has (some) intersection representation, interesting applications were found for geometric intersection graphs where the sets are geometrically restricted, e.g., intervals on a line (yielding so called interval graphs), straight line segments (yielding segment graphs),... This concept of representation by sets can be generalized to obtain overlap graphs (to represent an edge, the appropriate sets must overlap) or containment graphs (an edge stands for a pair of sets where one contains another). | |
Posets are partially ordered sets. Dushnik-Miller dimension of a poset is defined as a minimum size of a realizer. Realizer of a poset is a set of linear orders such that the given poset is its intersection (i.e., a < b if and only if in all posets in the realizer a < b). Determining the poset-dimension was shown to be NP-hard by Yannakakis in 1979 for dimension at least 3, it is known to be polynomial otherwise. Yannakakis showed that poset-dimension is NP-hard even for posets of height 2 (i.e., without a < b < c) when the dimension is at least 4. To decide whether a poset of height 2 has dimension 3 was a well known open problem since. | |
In the talk we focus on graphs geometric representation. As one of the applications we show hardness of the recognition of posets with dimension 3 and height 2. | |
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.