O konferenci
53. česko-slovenská konference Grafy 2018 se koná od 28. do 30. května 2018 na Matematicko-fyzikální fakultě UK na Malostranském náměstí v Praze. Konference zahrnuje všechna témata se vztahem k teorii grafů. Konferenčními jazyky jsou angličtina, slovenština a čeština, přičemž v posledních dvou případech se doporučuje připravit anglickou prezentaci.
Konference navazuje na dlouhou tradici, zahájenou konferencí v Liblicích v roce 1961.
Informace o cenách, termínech a registraci najdete na stránce Registrace, informace o zaslání abstraktu přednášky na stránce Příspěvky. Podrobnosti o ubytovacích možnostech jsou k dispozici na stránce Ubytování.
Pozvaní přednášející
| 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. | |
Pořadatelé
Konferenci v letošním roce pořádá CE-ITI - Institut teoretické informatiky ve spolupráci s dalšími českými a slovenskými centry výzkumu v teorii grafů. Lokálním organizátorem je Conforg, s.r.o.