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.