Neprihlásený používateľ
Cesta: Menu > Semináre > Bratislavský seminár z teórie grafov
6. mája 2021 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Jozef Rajník (Comenius University, Bratislava): Decomposition of cubic graphs with cyclic connectivity 5

Abstrakt:

Let G be a cyclically 5-connected cubic graph with a 5-edge-cut separating G into two cyclic components G_1 and G_2. We prove that each component G_i can be completed to a cyclically 5-connected cubic graph by adding three vertices, unless G_i is a cycle of length five.
Our work extends similar results by Andersen et al. for cyclic connectivity 4 from 1998. Our results enable us to use inductive arguments in the class of the cubic graphs with cyclic connectivity 5. Also, this inductive approach can be used in computer-assisted constructions of cubic graphs with cyclic connectivity 5 and other prescribed properties such as large girth or oddness. This is a joint work with Edita Máčajová.

♦ ♦ ♦

29. apríla 2021 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Tamas Héger (Lorand Eotvos University, Budapest): New results for the bipartite Ramsey number of the four-cycle versus stars

Abstrakt:

Let $b(n)$ denote the smallest integer $b$ such that each red-blue edge coloring of the complete bipartite graph $K_{b,b}$ contains a red $C_4$ or blue $K_{1,n}$. This variation of the Ramsey problem was studied by Carnielli, Goncalves and Monte Carmelo (2000, 2008). They obtained the upper bound b(n) <= n + [sqrt(n)], and provided constructions that prove this bound sharp in infinitely many cases. They also posed two conjectures about $b(n)$. We give further constructions that give equality in this bound, and refute both conjectures. The results rely on projective planes, some Zarankiewicz numbers and the non-existence of certain nearly generalized polygons.
This work is joint with Imre Hatala and Sam Mattheus.

♦ ♦ ♦

22. apríla 2021 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Tomas Kaiser (University of West Bohemia, Pilsen): Independent transversals in graph

Abstrakt:

An independent transversal in a graph G with a given partition P of its vertex set is an independent set in G intersecting each block of P in a single vertex. Given a lower bound on the size of blocks of P, which conditions on the degrees in G imply the existence of an independent transversal? We will discuss topological and probabilistic aspects of this classical problem as well as recent developments related to the entropy compression method. Includes joint work with Carla Groenland, Matt Wales and Oscar Treffers.

♦ ♦ ♦

15. apríla 2021 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Davide Mattiolo (University of Verona): On Z-continuous mappings between cubic graphs

♦ ♦ ♦

8. apríla 2021 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Peter Zeman (Charles University, Prague): Jordan-like characterization of automorphism groups of planar graphs and its subclasses

Abstrakt:

We investigate automorphism groups of planar graphs. The main result is a complete recursive description of all abstract groups that can be realized as automorphism groups of planar graphs. The characterization is formulated in terms of inhomogeneous wreath products. In the proof, we combine techniques from combinatorics, group theory, and geometry. This significantly improves the Babai's description (1975).

♦ ♦ ♦

25. marca 2021 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Maria Macekova (P. J. Safarik University, Kosice): Structure of edges in embedded graphs

Abstrakt:

The weight w(e) of an edge is the degree-sum of its end-vertices. In 1955, Kotzig proved that every 3-connected plane graph contains an edge of weight at most 13. Later, Borodin proved the existence of such an edge in plane graphs with minimum degree at least three. If we consider a graph embedded on a surface with non-positive Euler characteristic, minimum degree three and sufficiently large number of vertices, then the existence of an edge of weight at most 15 can be proved. In the talk we describe types of edges in connected graphs with minimum degree at least 2, minimum face size at least 3 and sufficiently large number of vertices embedded on a surface with non-positive Euler characteristic. We will also discuss the quality of our results.
Joint work with K. Cekanova and R. Sotak.

♦ ♦ ♦

11. marca 2021 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Petr Kovář (VSB - Technická univerzita Ostrava): A nice application of complete graph decomposition

Abstrakt:

Graph decompositions, graceful labelings, perfect difference sets - all these are well established topics in Graph Theory or in Number Theory. They have a surprising and nice application in memory distribution of a parallel numerical solution of a large system of equations with dense matrices, which arise e.g. when using Boundary Element Method.
In this talk we present a brief overview of the classical results and explain the method, that allowed us to solve larger problems than traditional parallelization would allow. We have successfully used cyclic graph decompositions when solving systems with millions of variables.
Prezentácia

♦ ♦ ♦

25. februára 2021 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Heidi Van den Camp (University of Ghent): The Effect of Local Symmetry-Preserving Operations on the Connectivity of Embedded Graph

Abstrakt:

Symmetry-preserving operations on polyhedra have been studied for a very long time. However, it was only recently that a general description of all 'local symmetry-preserving operations' (lsp-operations) was presented. With this description it becomes possible to prove general results about all lsp-operations instead of studying every operation separately. We use this approach to investigate the effect of lsp-operations on the (3-)connectivity of embedded graphs.
Historically, symmetry-preserving operations have mostly been applied to polyhedra (3-connected plane graphs), but there is no mathematical reason why the new definition of lsp-operations could not be applied to more general embedded graphs. For plane graphs, all lsp-operations preserve 3-connectivity, but once we start looking at graphs with a higher genus this is no longer the case. The dual is the most striking example of an lsp-operation that can greatly reduce the connectivity of an embedded graph, but there are other operations that can destroy 3-connectivity in certain embedded graphs. We characterise exactly which lsp-operations always preserve 3-connectivity and which operations do not.
Prezentácia

♦ ♦ ♦

10. decembra 2020 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Štefko Miklavič (University of Primorska, Koper): Terwilliger algebra of a graph

Abstrakt:

The aim of this talk is to introduce Terwilliger algebra of a graph. We will first define Terwilliger algebra of an arbitrary connected simple graph, and its (irreducible) modules. We will show that in the context of Terwilliger algebras, distance-(bi)regular graphs arise quite naturally. We will be interested in the interplay between certain combinatorial properties of graphs and the module structure of the associated Terwilliger algebras

♦ ♦ ♦

3. decembra 2020 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Jakub Przybylo, AGH Univ. of Science and Technology, Krakow): The irregularity strength of regular graphs is usually small

Abstrakt:

The irregularity strength of a graph G, s(G), is the least k admitting a [k]-weighting of the edges of G assuring distinct weighted degrees of all vertices, or equivalently the least possible maximal edge multiplicity in an irregular multigraph obtained of G via multiplying some of its edges. The most well-known open problem concerning this graph invariant is the conjecture posed in 1987 by Faudree and Lehel that there exists a constant C such that s(G) is at most n/d+C for each d-regular graph G with n vertices and d at least 2. However, the best published result thus far implies an upper bound 6n/d+C. We shall show that the conjecture of Faudree and Lehel holds asymptotically in the cases when d is neither very small nor very close to n.

♦ ♦ ♦

26. novembra 2020 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Jonathan Narboni (LABRI University of Bordeaux): On Vizing's edge coloring question

Abstrakt:

In his 1965 seminal paper on edge coloring, Vizing proved that a (Delta+1)-edge coloring can be reached from any given proper edge coloring through a series of Kempe changes, where Delta is the maximum degree of the graph. He concludes the paper with the following question: can an optimal edge coloring be reached from any given proper edge coloring through a series of Kempe changes? In other words, if the graph is Delta-edge-colorable, can we always reach a Delta-edge-coloring? We discuss a key ingredient in Vizing's original paper, namely the use of fans; we show how to extend the notion and answer his question in the affirmative for all triangle-free graphs.
This is a joint work with M. Bonamy, O. Defrain, T. Klimosova, and A. Lagoutte.

♦ ♦ ♦

19. novembra 2020 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Martin Knor (STU Bratislava): Distance based indices in nanotubical graphs

Abstrakt:

Nanotubical graphs are obtained by wrapping a hexagonal grid, and then possibly closing the tube with caps. We derive asymptotics for several distance-based generalized chemical indices which are of the form $$I^{\lambda}(G)=\sum_{u\ne v}f(u,v)dist^{\lambda}(u,v),$$ where $\lambda$ is a real number and $f(u,v)$ is a nonnegative symmetric function which is non-decreasing and which depends only on degrees of $u$ and $v$. All our results are obtained using double integrating and they show that the leading term depends on the circumference of the nanotube and not on its particular type.
This is a joint work with Vesna Andova and Riste Skrekovski

♦ ♦ ♦

12. novembra 2020 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
František Kardoš (FMFI UK, LABRI University of Bordeaux): On the 4-color theorem for signed graphs

Abstrakt:

Macajova, Raspaud and Skoviera defined the chromatic number of a signed graph which coincides for all-positive signed graphs with the chromatic number of unsigned graphs. They conjectured that in this setting, for signed planar graphs four colors are always enough, thereby generalising The Four Color Theorem. We disprove the conjecture.

♦ ♦ ♦

5. novembra 2020 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Giuseppe Mazzuoccolo (Universita di Verona): Normal edge-colorings of cubic graphs

Abstrakt:

A k-edge-coloring of a graph G is an assignment of colors {1,...,k} to edges of G, such that adjacent edges receive different colors. If α is an edge-coloring of G, then for a vertex v of G, let Sα(v) be the set of colors that edges incident to v receive. If G is a cubic graph, then a normal k-edge-coloring of G is a k-edge-coloring with the property that for any edge uv |Sα(u) ∪ Sα(v)| ≠ 4. The normal chromatic index of a cubic graph (denoted by γ′N(G)) is the smallest k, for which G admits a normal k-edge-coloring. Jaeger conjectured in 1985 that all bridgeless cubic graphs have normal chromatic index at most five. Even if the original conjecture of Jaeger is for bridgeless cubic graphs, we can define the normal chromatic index for any simple cubic graph. We show that γ′N(G) ≤ 7 for any simple cubic graph G, and this bound is best-possible. Moreover, we discuss other possible approximation results, where we insist to use exactly five colours but we admit to have some "abnormal" edges.
This is a joint work with Vahan Mkrtchyan.
Prezentácia

♦ ♦ ♦

22. októbra 2020 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
Martin Škoviera (FMFI UK): Strong edge colourings of regular graphs and the covers of Kneser graphs

Abstrakt:

A proper edge colouring of a graph is strong if it creates no bichromatic path of length three. It is well known that for a strong edge colouring of a k-regular graph at least 2k-1 colors are needed. We show that a k-regular graph admits a strong edge couloring with 2k-1 colors if and only if it covers the Kneser graph K(2k-1,k-1). In particular, a cubic graph is strongly 5-edge-colorable whenever it covers the Petersen graph.
One of the implications of this result is that a conjecture about strong edge colourings of subcubic graphs proposed by Faudree et al. [Ars Combin. 29 B (1990), 205--211] is false.
This is a joint work with Borut Lužar, Edita Máčajová and Roman Soták.

♦ ♦ ♦

15. októbra 2020 o 9:50 cez MS Teams (Prístupový kód do MS Teams je: gglxxc7)
František Kardoš (FMFI UK, LABRI University of Bordeaux): Islands in planar graphs

Abstrakt:

Thomassen (1995) showed that every planar graph of girth at least 5 is 3-choosable (i.e., can be properly colored from any assignment of lists of at least 3 allowed colors at each vertex). However, it has been open whether this statement can be proven via reducible configurations and discharging (such an argument would be easier to generalize to coloring graphs embedded on other surfaces). We find such a proof: we show that each planar graph of girth at least 5 and minimum degree at least 3 contains a small subgraph H such that each vertex of H has at most one neighbor outside of H (an island), and we find an unavoidable set of islands which are reducible using the polynomial method of Alon and Tarsi. We also consider analogous questions for planar graphs in general, without the girth condition.
This is a joint work with Marthe Bonamy, Michelle Delcourt, Zdeněk Dvořák, and Luke Postle.

♦ ♦ ♦

8. októbra 2020 o 9:50 v miestnosti M-213
Jozef Rajník (FMFI UK): Decomposition of cyclically 4-connected cubic graphs

Abstrakt:

Let $G$ be a cyclically $4$-connected cubic graph with a cycle separating $4$-edge-cut $S$ and let $H$ be one component of $G - S$. We give the necessary and sufficient condition under which the component $H$ can be extended to a cyclically $4$-connected cubic graph of the same order by adding two edges. Our work completes the result of Goedgebeur, Máčajová and Škoviera, who showed that the component $H$ can be extended to a cyclically $4$-connected cubic graph by adding two adjacent vertices and restoring $3$-regularity. These results provide useful induction methods for cyclically $4$-connected cubic graphs.
This is a joint work with Edita Máčajová. The same results were also published by Andersen, Fleischner and Jackson.

♦ ♦ ♦

1. októbra 2020 o 9:50 v miestnosti M-213
Robert Jajcay (FMFI UK): Extremal edge-girth-regular graphs

Abstrakt:

The aim of the talk is to generalize properties satisfied by highly symmetric (vertex-, edge- or arc-transitive) graphs to larger classes of graphs and to look for families of graphs that share some of the properties of symmetric graphs but are not themselves symmetric.
One such class is the class of edge-girth-regular $egr(v,k,g,\lambda)$-graphs which are $k$-regular graphs of order $v$ and girth $g$ in which every edge is contained in $\lambda$ distinct $g$-cycles. Beside the obvious edge-transitive graphs, examples include other important classes of graphs such as Moore graphs, as well as many of extremal $k$-regular graphs of prescribed girth or diameter. Infinitely many $egr(v,k,g,\lambda)$-graphs are known to exist for sufficiently large parameters $(k,g,\lambda)$, and in line with the well-known Cage Problem we attempt to determine the smallest graphs among all edge-girth-regular graphs for given parameters $(k,g,\lambda)$.
We derive lower bounds in terms of the parameters $k,g$ and $\lambda$. We also determine the orders of the smallest $egr(v,k,g,\lambda)$-graphs for some specific parameters $(k,g,\lambda)$, and address the problem of the smallest possible orders of bipartite edge-girth-regular graphs.
Joint work with A. Zavrtanik Drglin, S. Filipovski, and T. Raiman.

♦ ♦ ♦

21. septembra 2020 o 9:50 v miestnosti M-213
Jozef Širáň (STU Bratislava/The Open University, U.K.): Regular self-dual and self-Petrie-dual maps of arbitrary valency

Abstrakt:

Existence of a regular, self-dual and self-Petrie-dual map of any given even valency was established by Archdeacon, Conder and the presenter in 2014. In the talk we will give details about an extension of this result to odd valencies greater than 3 (joint work with O. Jeans and J. Fraser).

♦ ♦ ♦

5. marca 2020 o 9:50 v miestnosti M-213
Martin Škoviera (KI FMFI UK): Binary snarks with rotation symmetry

Abstrakt:

A binary snark is a cubic graph which cannot be properly 3-edge-coloured and is spanned by the balanced cubic tree T_d of depth d for some d. A binary snark G is called a rotation snark if an automorphism of T_d that cyclically permutes the edges incident with the root of T_d extends to an automorphism of G. One motivation for the study of rotation snarks comes from the intention to find small snarks of girth 7 and even cyclically 7-connected snarks. So far, only very few binary snarks have been found (one of them being the Petersen graph), mostly as a result of an extensive computer search. We present a construction of infinitely many rotation snarks with cyclic connectivity 5.
This is a joint work with Edita Macajova.

♦ ♦ ♦

19. decembra 2019 o 9:50 v miestnosti M-213
Milan Lekár (FMFI UK): Brief History of the Graph Theory Seminar in Bratislava

Abstrakt:

In ths talk we will discuss the beginnings of the seminar, reasons for the establishment of the seminar, and the reasons for the emigration of prof. Rosa and prof. Kotzig.

♦ ♦ ♦

12. decembra 2019 o 9:50 v miestnosti M-213
Peter Zeman (MFF UK Praha): On H-topological intersection graphs

Abstrakt:

Biró, Hujter, and Tuza (1992) introduced the concept of H-graphs, intersection graphs of connected subregions of a graph H thought of as a one-dimensional topological space. They relate to and generalize many important classes of geometric intersection graphs, e.g., interval graphs, circular-arc graphs, split graphs, and chordal graphs.
Surprisingly, we negatively answer a 30-year-old question of Biró, Hujter, and Tuza which asks whether H-graphs can be recognized in polynomial time, for a fixed graph H. Moreover, our paper opens a new research area in the field of geometric intersection graphs by studying H-graphs from the point of view of fundamental computational problems of theoretical computer science: recognition, graph isomorphism, dominating set, clique, and colorability.
(joint work with: Steven Chaplick, Martin Töpfer, Jan Voborník)

♦ ♦ ♦

5. decembra 2019 o 9:50 v miestnosti M-213
Róbert Jajcay (FMFI UK, Bratislava): Bipartite Biregular Cages and Block Designs

♦ ♦ ♦

28. novembra 2019 o 9:50 v miestnosti M-213
Róbert Lukoťka (FMFI UK, Bratislava): Circular flow number of cubic graphs in O(1.5^n) time

Abstrakt:

We show that the circular flow number of a cubic graph can be determined in time O(1.94^n). The running time can be improved to O(1.5^n) if we do not need to distinguish the circular flow number values between 5 and 6. Finally, we observe that it is possible to decide the flow number of a cubic graph in O(1.26^n) time. We discuss how the results transfer to circular colourings.

♦ ♦ ♦

21. novembra 2019 o 9:50 v miestnosti M-213
Jozef Rajnik (FMFI UK, Bratislava): Constructions of critical and strictly critical snarks

Abstrakt:

Critical snarks are non-3-edge-colourable cubic graphs such that the removal of any two adjacent vertices leaves a 3-edge-colourable graph. A vast majority of them is also bicritical -- i.e. removing any two vertices leaves a colourable graph. Therefore, critical snarks that are not bicritical form a rather interesting class of snarks -- they are called strictly critical snarks and were studied by Chladný and Škoviera along with their relation to bicriticality of cyclically 4-connected snarks. Inspired by the analysis of small cases, we construct an infinite family of strictly critical snarks with girth 6. Furthermore, by proving that a certain type of superposition preserves criticality, we construct an infinite class of cyclically 6-connected strictly critical snarks, which solves a problem proposed by Chladný and Škoviera.

♦ ♦ ♦

14. novembra 2019 o 9:50 v miestnosti M-213
Adam Kabela (Masarykova univerzita, Brno): Quasirandom-forcing tournaments

Abstrakt:

We recall that a tournament is a directed graph having precisely one arc between each pair of its nodes. Following Chung and Graham (1991), we say that a tournament T is quasirandom if for every X ⊆ V(T),
v ∈ X| d+(v;X) - d-(v;X) = o(n2)
(in fact, they provided a number of equivalent definitions of quasirandomness of tournaments). We say that a tournament F is quasirandom-forcing if the following is satisfied for every tournament T. If the density of F in T is the same as the expected density of F in a random tournament, then T is quasi-random. We recall that a tournament is transitive if it contains no directed cycle. Coregliano and Razborov (2017) showed that every transitive tournament on at least 4 nodes is quasirandom-forcing (see also exercise 10.44(b) in Lovász (1993)). For completeness, we recall that no tournament on 3 nodes is quasirandom-forcing (it follows, for instance, from the result of Goodman (1959)). Regarding non-transitive tournaments on n nodes, it is known that none is quasirandom-forcing for n = 4, and Coregliano, Parente and Sato (2019) showed that there is one for n = 5 (and the combination of their results and the result of Hancock, Kráľ, Skerman and Volec (2019+) gives that it is the only one for n = 5), and Bucić, Long, Shapira and Sudakov (2019+) observed that there is none for n ≥ 7. We close the remaining case by showing that there is none for n = 6.
This is a joint work with Robert Hancock, Dan Kráľ, Taísa Martins, Roberto Parente, Fiona Skerman and Jan Volec.

♦ ♦ ♦

24. októbra 2019 o 9:50 v miestnosti M-213
Anna Kompišová (UK Bratislava): Short cycle covers of graphs with minimum degree 3 with loops

Abstrakt:

Let $G$ be a bridgeless graph and let $cc(G)$ denote the length of a shortest cycle cover of $G$. The best known result for the general case, $cc(G) \leq {5 \over 3}|E(G)|$ $(\approx 1.6667|E(G)|)$, was established over 35 years ago. Recently, Fan proved that $cc(G) < 1.6258|E(G)|$ for graphs with minimum degree at least 3 (loops being allowed) and $cc(G) < 1.6148|E(G)|$ for loopless graphs with minimum degree at least 3. We improve his first result by proving that $cc(G) < 1.0741|S| + 1.6148|E(G)-S|$ where $S$ denotes the set of loops of a graph $G$. This implies that if $G$ has minimum degree at least 3, then $cc(G) < 1.6148|E(G)|$.
This is a joint work with Robert Lukoťka.

♦ ♦ ♦

17. októbra 2019 o 9:50 v miestnosti M-213
Jean Paul Zerafa (Università degli Studi di Modena e Reggio Emilia): An equivalent formulation of the Fan-Raspaud Conjecture and related problems

Abstrakt:

In 1994, it was conjectured by Fan and Raspaud that every simple bridgeless cubic graph has three perfect matchings whose intersection is empty. In this talk we solve a problem recently proposed by Mkrtchyan and Vardanyan by giving an equivalent formulation of the Fan-Raspaud Conjecture. We also study a possibly weaker conjecture which states that in every simple bridgeless cubic graph there exist two perfect matchings such that the complement of their union is a bipartite graph. We here show that this conjecture can be equivalently stated using $H$-colourings, we prove it for graphs having oddness at most four and extend it to bridgeless cubic multigraphs and certain cubic graphs having bridges. Other related conjectures and their connection to the above will also be discussed.
This is a joint work with Giuseppe Mazzuoccolo.

♦ ♦ ♦

10. októbra 2019 o 9:50 v miestnosti M-213
Edita Máčajová (UK Bratislava): Cubic graphs with no short cycle covers

Abstrakt:

The shortest cycle cover conjecture suggests that every bridgeless cubic can have its edges covered with a collection of cycles of total length not exceeding (7/5).m where m is the number of edges. The covering ratio 7/5 is best possible, being reached by the Petersen graph. However, all cyclically 4-connected cubic graphs where the length of a shortest cycle cover is known have covering ratio close to the natural lower bound which equals 4/3. In line with this observation, Brinkmannn et al. (JCTB, 2013) made a conjecture that every cyclically 4-connected cubic graph has a cycle cover of length at most (4/3)m+o(m). We disprove this conjecture by exhibiting an infinite family of cyclically 4-connected cubic graphs whose shortest cycle cover has length at least (4/3 + 1/69)m.

♦ ♦ ♦

3. októbra 2019 o 9:50 v miestnosti M-213
Daniel Kraľ (Masaryk University, Brno and University of Warwick): Extremal problems concerning graphs and tournament

Abstrakt:

One of the most classical themes in extremal graph theory is the study of the interplay of subgraph densities. We will present two results that belong to this theme. The first concerns the following conjecture of Lovasz: any finite feasible set of subgraph density constraints can be extended to a finite set such that the asymptotic structure of graphs satisfying the constraints is unique. We will disprove the conjecture.
The second result is inspired by the Erdos-Rademacher Problem on the minimum possible triangle density in a graph with a given edge density. A conjecture of Linial and Morgenstern which asserts that, among all tournaments with a given density d of cycles of length three, the density of cycles of length four is minimized by tournaments with a structure analogous to that of graphs appearing in the Erdos-Rademacher Problem. We prove this conjecture for d>=1/36 using methods from spectral graph theory, and demonstrate that the structure of extremal examples is more complex than expected by giving its full description for d>=1/16.
The talk is based on results obtained in joint work with Timothy Chan, Andrzej Grzesik, Laszlo Miklos Lovasz and Jonathan Noel.

♦ ♦ ♦

9. mája 2019 o 9:50 v miestnosti M-213
Fan Wei (Stanford Unversity, CA, USA): Counting the number of cliques in hereditary minor-closed families of graphs

Abstrakt:

Reed and Wood, and independently Norine, Seymour, Thomas, and Wollan, showed that for each $t$ there is $c(t)$ such that every graph on $n$ vertices with no $K_t$ minor has at most $c(t)n$ cliques. Wood asked in 2007 if $c(t) < c^t$ for some absolute constant $c$. This problem was recently solved by Lee and Oum. In this paper, we determine the exponential constant. We prove that every graph on $n$ vertices with no $K_t$ minor has at most $3^{2t/3+o(t)}n$ cliques. This bound is tight for $n \geq 4t/3$. The method and result can generalize to any minor-closed family of graphs.
We use the similar idea to give an upper bound on the number of cliques in an $n$-vertex graph with no $K_t$-subdivsion. Easy computation will give an upper bound of $2^{3t+o(t)}n$; a more careful examination gives an upper bound of $2^{1.48t+o(t)}n$. We conjecture that the optimal exponential constant is $3^{2/3}$ as in the case of minors.
This is a joint work with Jacob Fox.

♦ ♦ ♦

2. mája 2019 o 9:50 v miestnosti M-213
Erika Fecková Škrabuľáková (TU Košice): On nonrepetitive colourings of graphs

Abstrakt:

A sequence r1, r2,...,r2n such that ri = rn+i for all 1 ≤ i ≤ n, is called a repetition. A sequence S is called nonrepetitive if no subsequence of consecutive terms of S forms a repetition.
In 1906 Norwegian mathematician Axel Thue started a systematic study of word structure. In his seminal paper he showed that there are arbitrarily long nonrepetitive sequences over three symbols. Since then Thue's non- repetitive sequences have repetitively occurred also in mathematics and various questions concerning nonrepetitive colourings of graphs have been formulated.
Alon at al. introduced a natural generalization of Thue's sequences for colouring of graphs. An edge-colouring / vertex-colouring of a graph G is nonrepetitive if the sequence of colours on any path in G is nonrepetitive. A natural question is whether there is a finite bound for the number of colours needed to colour the edges / vertices of G in such a way, that the colours of no path of G form a repetition.
There are several ways how to relax the requirements in this problem and several kinds of so called problems of Thue's type. Hence, many graph colouring parameters of Thue's type: the Thue chromatic number and index, the Thue choice number and index, the facial Thue chromatic number and index, the facial Thue choice number and index, the strong and weak total Thue chromatic number, the total Thue choice number, have been defined. All of these are connected with colourings of graphs that omit repetitions. Here you come familiar with some of them.

♦ ♦ ♦

25. apríla 2019 o 9:50 v miestnosti M-213
Marcel Abas (STU Bratislava): Metric Dimension of Cayley Digraphs of Metacyclic groups

Abstrakt:

The metric dimension of a (di)graph $G$ is the minimum cardinality of a subset $R$ (resolving set) of vertices of $G$ such that all vertices of $G$ are uniquely determined by their distances to (or from) the vertices of $R$. In this talk we deal with metric dimension of 2-generated Cayley digraphs of split metacyclic groups. We show some interesting results for general metacyclic groups. For some special parameters we give exact values of metric dimension.

♦ ♦ ♦

11. apríla 2019 o 9:50 v miestnosti M-213
Soňa Pavlíková (STU Bratislava): Inverting non-invertible labeled trees

Abstrakt:

If a graph with non-zero edge labels has a non-singular adjacency matrix, then one may use the inverse matrix to define a (labeled) graph that may be considered to be the inverse graph to the original one. It has been known that an adjacency matrix of a labeled tree is non-singular if and only if the tree has a unique perfect matching. In the opposite case one may use a generalized inverse (which, in the symmetric case, coincides with Moore-Penrose, Drazin, or group inverse) of the adjacency matrix to 'invert' a tree. A formula for entries of such a generalized inverse of a tree follows from the work of Britz, Olesky and van den Driessche (2004), based on a general formula for determining the Moore-Penrose inverse.
In our talk we will briefly introduce various approaches to 'inverting' non-invertible matrices, state a formula for a generalized inverse of (an adjacency matrix of) a labeled tree, and outline principles leading to a new proof of validity of this formula (based solely on considering eigenvectors).
This is a joint work with Jozef Širáň.

♦ ♦ ♦

4. apríla 2019 o 9:50 v miestnosti M-213
Katarína Hriňáková (STU Bratislava): The structure of graphs with given number of blocks and the maximum Wiener index

Abstrakt:

The Wiener index (the distance) of a graph is the sum of distances between all pairs of vertices. We study the maximum possible value of this invariant among graphs on $n$ vertices with fixed number of blocks $p$. It is known that among graphs on $n$ vertices that have just one block, the $n$-cycle has the largest Wiener index. And the $n$-path, which has $n-1$ blocks, has the maximum Wiener index in the class of graphs on $n$ vertices. We show that among all graphs on $n$ vertices which have $p\ge 2$ blocks, the maximum Wiener index is attained by a graph composed of two cycles joined by a path (here we admit that one or both cycles can be replaced by a single edge, as in the case $p=n-1$ for example). Finally, for each $n$ and $p$ we specify the lengths of the cycles in the extremal graph.
This is a joint work with S. Bessy, F. Dross, M. Knor and R. Skrekovski.

♦ ♦ ♦

21. marca 2019 o 9:50 netradične v posluchárni C
Riste Skrekovski (University of Ljubljana): Some results on the unique-maximum coloring of plane graphs

Abstrakt:

A unique-maximum coloring of a plane graph is a proper vertex coloring by natural numbers where on each face $\alpha$ the maximal color appears exactly once on the vertices of $\alpha$. Fabrici and Göring proved that six colors are enough for any plane graph and conjectured that four colors suffice. Thus, this conjecture is a strengthening of the Four Color Theorem. Wendland later decreased the upper bound from six to five.
We first show that the conjecture holds for various subclasses of planar graphs but then we disprove it for planar graphs in general. So, we conclude that the facial unique-maximum chromatic number of the sphere is not four but five.
Joint work with Vesna Andova, Bernard Lidicky, Borut Luzar, and Kacy Messerschmidt.

♦ ♦ ♦

7. marca 2019 o 9:50 v miestnosti M-213
Martin Máčaj (UK Bratislava): Color digraphs, coherent configurations and the Weisfeiler-Leman stabilization

Abstrakt:

A color digraph is a complete digraph in which every dart is assigned a color. Color digraphs are an important tool in various areas, e.g., combinatorics, group theory, sports, and others.
Association schemes and coherent configurations form special classes of color (di)graphs, with significant applications in graph theory, group theory, statistics, coding theory ...
The Weisfeiler-Leman stabilization is a polynomial time algorithm which, given a color graph $S$, provides the smallest coherent configuration $S'$ such that each color class of $S$ is union of classes of $S'$.
In this talk we recall basic properties of association schemes and coherent configurations and we present the Weisfeiler-Leman stabilization.

♦ ♦ ♦

21. februára 2019 o 9:50 v miestnosti M-213
Robert Lukoťka (UK Bratislava): Three results on cubic graphs

Abstrakt:

THe oddness of a bridgeless cubic graph $G$ is the minimal number of odd circuits in a $2$-factor of $G$. The weak oddness of $G$ is the minimal number of odd components in an even factor of $G$. The resistance of $G$ is the minimal number of vertices that have to be deleted in order to get a $3$-edge-colourable graph from $G$.
As the first result we show that there exist graphs with weak oddness $4$, resistance $4$, and arbitrarily large oddness [I. Allie: Oddness to resistance ratios in cubic graphs, Discrete Mathematics 342 (2019), 387 392].
Second, we show how to decide $3$-edge-colourability, determine the oddness, the weak oddness, and the resistance of a $n$ vertex cubic graph $G$ in time ${\cal O}^*(3^{(1/6+\varepsilon)\cdot n})$. [Joint work with a group of people from KAMAK problem solving seminar].
Third, we show that that if a cubic graph has nowhere-zero $A$-flow (where $A$ is an abelian group) or $k$-flow then it has also a nowhere-zero $A$-flow or $k$-flow where the edges incident with one vertex have their flow values and orientations prescribed (subject to obvious necessary conditions) [M. DeVos: Flows on Bidirected Graphs, arXiv:1310.8406; Y. Lu, R. Luo, C.-Q. Zhang: Multiple weak $2$-linkage and its applications on integer flows of signed graphs, European Journal of Combinatorics 69 (2018), 36 48].

♦ ♦ ♦

22. novembra 2018 o 9:50 v miestnosti M-213
Katarína Hriňáková (STU Bratislava): An inequality between variable Wiener index and variable Szeged index

Abstrakt:

For a simple graph $G=(V,E)$, the Wiener index is defined as the sum of distances between all pairs of vertices, i.e. $W(G)=\sum_{\{u, v\} \subseteq V(G)} d(u,v)$. The Szeged index is defined as $\Sz(G)= \sum_{e=ij \in E}n_{e}(i)\cdot n_{e}(j)$, where $n_{e}(i)$ is the number of vertices strictly closer to $i$ than $j$, and analogously, $n_{e}(j)$ is the number of vertices strictly closer to $j$. A well-know inequality between the Szeged and Wiener indices says that $\Sz(G)=\sum_{e=ij\in E(G)} n_e(i)n_e(j) \ge \sum_{\left\{u,v\right\}} d(u,v)= W(G)$ for every graph~$G$. In the past, variable variations of the standard topological indices were defined. Following this line, we study a natural generalisation of the above inequality, namely $\sum_{e=ij\in E(G)} (n_e(i)n_e(j))^\alpha \ge \sum_{\left\{u,v\right\}} d(u,v)^\alpha$. We show that for all trees the inequality is true if $\alpha>1$, and the opposite inequality holds if $0\le \alpha<1$. In fact, the first result also holds for bipartite graphs and for graphs on $n$ vertices with at most $n+3$ edges, but the opposite one does not. For general graphs we solve also the case $\alpha<0$ and we present interesting conjectures. Observe, that both the sums are interesting on their own, and in accordance with the usual terminology they can be called the variable Szeged and variable Wiener indices.
This is a joint work with Martin Knor and Riste Škrekovski.

♦ ♦ ♦

15. novembra 2018 o 9:50 v miestnosti M-213
Martin Knor (STU Bratislava): On the anti-radius of a graph

Abstrakt:

Let $G$ be a graph. By the $k,l$-antiradius of $G$, $p_{k,l}(G)$, we mean the value $$\max_{K\subseteq V(G)}\{\min_{L\subseteq L}\{d_l(L);\,|L|=l\}; |K|=k\},$$ where by $d_l(L)$ we mean the sum of distances between all pairs of vertices in $L$.This parameter is in a way dual to radius and we focus on $l=2$, i.e., we consider the $k,2$-anti-radius. We give a tight upper bound for $k,2$-anti-radius over the class of connected graphs on $n$ vertices. Such a bound states, how large the smallest distance among $k$ distinct vertices in an $n$-vertex graph can be. Also, we solve the corresponding problem for 2-connected graphs for $k=3$.

♦ ♦ ♦

8. novembra 2018 o 9:50 v miestnosti M-213
Robert Jajcay (FMFI UK Bratislava):

Abstrakt:

We discuss a new family of cubic graphs, which we call SGP-graphs, that bears a close resemblance to the family of generalized Petersen graphs, both in definition and properties. The focus of our presentation is on determining the algebraic properties of graphs from our new family. We look for highly symmetric graphs, e.g., graphs with large automorphism groups, vertex- or arc-transitive graphs. In particular, we present arithmetic conditions for the defining parameters that guarantee that graphs with these parameters are vertex-transitive or Cayley, and we find one arc-transitive SGP-graph which is not a generalized Petersen graph.

♦ ♦ ♦

25. októbra 2018 o 9:50 v miestnosti M-213
Anna Kompišová (FMFI UK Bratislava): Flow and circular flow number of signed cubic graphs

Abstrakt:

A signed graph $(G,\sigma)$ is a graph $G$ with a signature $\sigma \colon E \to \{1,-1\}$. The flow number $\Phi(G,\sigma)$ of a flow-admissible signed graph $(G,\sigma)$ is the smallest integer $k$, for which there exists an integer nowhere-zero $k$-flow on $(G,\sigma)$. The circular flow number $\Phi_c(G,\sigma)$ of a flow-admissible signed graph $(G,\sigma)$ is the infimum of real numbers $r$ for which there exists an $\mathbb{R}$-flow on $(G,\sigma)$ satisfying that absolute values of all the flow values are in the interval $[1,r-1]$.
The relationship between the flow number $\Phi(G)$ and the circular flow number $\Phi_c(G)$ in the unsigned case is simple: $\Phi(G) = \lceil \Phi_c(G)\rceil$. Based on this result Raspaud and Zhu conjectured, that $\Phi(G,\sigma) - \Phi_c(G,\sigma) < 1$ for every flow-admissible signed graph $(G,\sigma)$. This conjecture was disproved using noncubic signed graphs with bridges.
In this talk we disprove the conjecture even for bridgeless signed cubic graphs. We also determine all possible pairs of flow and circular flow number of signed cubic graph if flow number is $3, 4$ or $5$ and prove that every pair is achievable. Finally, we prove that every known signed graph with $\Phi(G,\sigma) = 6$ has also $\Phi_c(G,\sigma) = 6$.

♦ ♦ ♦

18. októbra 2018 o 9:50 v miestnosti M-213
Jozef Rajník (FMFI UK Bratislava): Structure of small snarks

Abstrakt:

Snarks are bridgeless cubic graphs which are not 3-edge-colourable. We analyse the structure of all critical cyclically 5-connected snarks up to order 36. The remaining snarks on at most 36 vertices can be constructed from them by using simple operations. Based on this analysis, we generalize certain individual snarks into infinite families and construct a rather rich infinite class of cyclically 5-connected irreducible snarks.

♦ ♦ ♦

11. októbra 2018 o 9:50 v miestnosti M-213
Martin Knor (STU Bratislava): Trees with the maximal value of Graovac-Pisanski index

Abstrakt:

Let $G$ be a graph. Its Graovac-Pisanski index is defined as $GP(G)=\frac{|V(G)|}{2|Aut(G)|}\sum_{u\in V(G)}\sum_{\apha\in Aut(G)}d_G(u,\alpha(u))$, where $Aut(G)$ is the group of automorphisms of $G$. It is easy to see that $G$ has the smallest Graovac-Pisanski index if its group of automorphisms is trivial, in which case $GP(G)=0$. The question is to find graphs with the largest value of Graovac-Pisanski index. We found graphs with the maximum value of Graovac-Pisanski index in the class of trees and in the class of unicyclic graphs.

♦ ♦ ♦

4. októbra 2018 o 9:50 v miestnosti M-213
Edita Mačajová (UK Bratislava): Smallest nontrivial snarks of oddness 4

Abstrakt:

The oddness of a cubic graph is the smallest number of odd circuits in a 2-factor of the graph. Oddness constitutes one of the most important measures of uncolourability of cubic graphs. In a previous talk (delivered earlier this year by M. Skoviera) we showed that the smallest number of vertices of a snark with cyclic connectivity 4 and oddness 4 is 44. In this talk we show that there are exactly 31 such snarks. These snarks are built up from subgraphs of the Petersen graph and a small number of additional vertices. Depending of their structure they fall into six classes. We indicate the reasons why these snarks have oddness 4 and sketch the proof that the 31 snarks form a complete set snarks with cyclic connectivity 4 and oddness 4 on 44 vertices.
(This is joint work with Jan Goedgebeur and Martin Škoviera)

♦ ♦ ♦

19. júna 2018 o 15:00 v miestnosti M-213
Jan Goedgebeur (University of Ghent, Belgium): Bounds for the smallest k-chromatic graphs of given girth

Abstrakt:

A graph with chromatic number k is called k-chromatic. Using computational methods, we show that the smallest triangle-free 6-chromatic graphs have at least 32 and at most 40 vertices.
We also determine the complete set of all triangle-free 5-chromatic graphs up to 23 vertices and all triangle-free 5-chromatic graphs on 24 vertices with maximum degree at most 7. This implies that Reed's conjecture holds for triangle-free graphs up to at least 24 vertices. Next to that, we determine that the smallest regular triangle-free 5-chromatic graphs have 24 vertices. Finally, we show that the smallest 5-chromatic graphs of girth at least 5 have at least 29 vertices and that the smallest 4-chromatic graphs of girth at least 6 have at least 25 vertices.

♦ ♦ ♦

17. mája 2018 o 9:50 v miestnosti M-213
Roman Soták (UPJŠ Košice): Star and List star edge-coloring of graphs

Abstrakt:

A star edge-coloring of a graph is a proper edge-coloring without bichromatic paths and cycles of length four. In this talk, we present bounds for various classes of graphs. In particular, we focus to the list version of this edge-coloring and prove that the list star chromatic index of every subcubic graph is at most 7, answering the question of Dvořák et al. (Dvořák, Mohar, and Šámal, Star chromatic index, J. Graph Theory 72 (2013), 313-326).

♦ ♦ ♦

10. mája 2018 o 9:50 v miestnosti M-213
Robert Jajcay (FMFI UK, Bratislava): Bermond-Bollobas Problem and Ramanujan Graphs

Abstrakt:

If we denote by $n(k, d)$ the order of the largest undirected graph of maximum degree $k$ and diameter $d$, and by $M(k,d)$ the corresponding Moore bound, then $n(k,d) \leq M(k,d)$, for all $k \geq 3, d \geq 2$. While the inequality has been proven strict for all but very few pairs $k$ and $d$, the exact relation between the values $n(k,d)$ and $M(k,d)$ is unknown, and the uncertainty of the situation is captured by a question of Bermond and Bollobas who asked whether it is true that for any a positive integer $c>0$ there exist a pair $k$ and $d$, such that $n(k, d)\leq M(k,d)-c$.
We show a surprising connection of this question to the value $2\sqrt{k-1}$, which is also essential in the definition of the Ramanujan graphs which are $k$-regular graphs having the property that their second largest eigenvalue (in modulus) does not exceed $2 \sqrt{k-1}$. We further reinforce this surprising connection by showing an interesting consequence of a negative answer to the problem of Bermond and Bollobas. Namely, we show that if there exists a $c > 0$ such that $n(k,d) \geq M(k,d) - c$, for all $k \geq 3, d \geq 2$, then for any fixed $k$ and all sufficiently large $d$'s, the largest undirected graphs of degree $k$ and diameter $d$ must be Ramanujan graphs. Since Ramanujan graphs are scarce, our result seems to suggest a positive answer to the question of Bermond and Bollobas.
This is a joint work with Slobodan Filipovski.

♦ ♦ ♦

26. apríla 2018 o 9:50 v miestnosti M-213
Primož Potočnik (University of Ljubljana): Existence of a graph cover whose automorphism group is as we want it to be

Abstrakt:

Suppose one is given a finite connected graph X and a group of automorphisms G acting on it. Can one find a regular covering projection onto X such that G is the maximal group that lifts and such that the full automorphism group of the graph is the lift of G? A recent partial answer proved recently by Pablo Spiga and the speaker will be presented.

♦ ♦ ♦

19. apríla 2018 o 9:50 v miestnosti M-213
Martin Máčaj (UK Bratislava): On a class of self-dual and self-Petrie-dual maps

Abstrakt:

It is known that the class of regular maps can be identified with the class of groups with a presentation G=$. Generally we expect that the group elements 1, a, b, c and bc are pairwise distinct. In the first part of the talk we give the classification of the maps which fail to meet such expectation, based on the results of C. H. Li and J. Siran. In the second part of the talk we discuss the construction which gives a self-dual and self-Petrie-dual regular map from any given regular map and study the properties of self-dual and self-Petrie-dual regular maps ♦ ♦ ♦ 12. apríla 2018 o 9:50 v miestnosti M-213 Martin Vodička (UK Bratislava): Local embeddability of groups into finite loops Abstrakt: The concept of a group locally embeddable into finite groups (LEF-group) was introduced by Vershik and Gordon in 1998 to be a group where every finite square cut out of its multiplication table can be extended to a multiplication table of a finite group. Glebsky and Gordon showed (2005) that a group is locally embeddable into finite semigroups if and only if it is an LEF-group, and that every group is locally embeddable into finite quasigroups, and even into finite loops. Improving on their result Ziman in 2005 proved that every group, as well as every loop having antiautomorphic two-sided inverses is locally embeddable into finite AAI~loops. However, the AAI loops are still "rather far away from groups" in general. A much closer class to groups is formed by the loops satisfying the so called inverse property. We show that every IP-loop, henceforth every group, is locally embeddable into finite IP-loops. The proof makes use of Steiner triple systems and Dirac's theorem for graphs containing a Hamilton cycle. ♦ ♦ ♦ 5. apríla 2018 o 9:50 v miestnosti M-213 Jozef Širáň (STU Bratislava): Regular self-dual and self-Petrie-dual maps of a given valency Abstrakt: We will discuss ways of establishing the existence of a finite regular self-dual and self-Petrie-dual map of valency k for every positive integer k>3 (a joint work with Olivia Jeans and Jay Fraser). ♦ ♦ ♦ 22. marca 2018 o 9:50 v miestnosti M-213 Roman Nedela (ZCU Plzeň): Hamilton cycles in cubic Cayley graphs and Thomassen's conjecture Abstrakt: Thomassen's conjecture claims the existence of a constant c such that every cubic graph of cyclic connectivity at least c is hamiltonian. In fact, the only known cyclically 7-connected cubic graph that is not hamiltonian is the Coxeter graph. In 1996, Nedela and Skoviera proved that for cubic vertex-transitive graphs the cyclic connectivity is equal to the girth. By a folklore conjecture, all cubic Cayley graphs are hamiltonian. Suppose that the Thomassen's conjecture holds for c=7. Then to prove hamiltonicity of the cubic Cayley graphs one needs to deal with graphs of girth at most six. The existence of small cycles in a Cayley graph put restrictions on the structure of the underlying group. In our talk we discuss the structure of the cubic Cayley graphs of girth at most six and in many cases show their hamiltonicity. The remaining "hard cases" will be described. ♦ ♦ ♦ 15. marca 2018 o 9:50 v miestnosti M-213 Martin Škoviera (UK Bratislava): Smallest snarks with oddness 4 Abstrakt: The oddness of a bridgeless cubic graph$G$is the smallest number of odd circuits in a 2-factor of$G$. Oddness is one of the most important invariants of snarks because several important conjectures in graph theory can be reduced to snarks of oddness 4 or larger. In this talk we deal with the problem of determining the smallest order of a nontrivial snark of oddness 4. (Here nontrivial' means girth at least 5 and cyclic connectivity at least 4.) We prove that the smallest order of a nontrivial snark with oddness 4 and cyclic connectivity 4 is 44, and characterise all snarks of order 44 with this property. The proof relies on a detailed analysis of 3-edge-colourings conflicting on a cycle-separating 4-edge-cut, an extensive computer search, and a closure theorem for cubic graphs with cyclic connectivity 4 due to Andersen, Fleischner, and Jackson (1988). This is a joint work with Jan Goedgebeur and Edita Mačajová. ♦ ♦ ♦ 22. februára 2018 o 9:50 v miestnosti M-213 Metod Saniga (Astronomical Institute, Slovak Academy of Sciences, Tatranská Lomnica): Finite Geometries Relevant for Quantum Information Abstrakt: The past decade has witnessed an increasing role of finite geometry in quantum information theory. In this talk we shall focus on projective ring lines, polar spaces and (extended) generalized polygons. First, we shall show how projective lines over modular rings are related to single-qudit Pauli groups. Then, it will be demonstrated how symplectic and orthogonal polar spaces describe properties of multi-qubit Pauli groups. Finally, it will be outlined how certain black-hole entropy formulas are encoded in the structure of generalized quadrangles with lines of size three and their extensions. ♦ ♦ ♦ 14. decembra 2017 o 9:50 v miestnosti M-213 Sara Zemljic (Comenius University, Bratislava): The Sierpinski product of graphs Abstrakt: The family of Sierpinski graphs has been studied very often in the past few decades for different reasons. One of them is definitely their relation to the famous Sierpinski tringle fractal and their fractal-like structure. Main building block of Sierpinski graphs are complete graphs and each next iteration is built in the fractal-like manner of a complete graph. This idea was recently generalized to generalized Sierpinski graphs, where instead of initially taking a complete graph, we start with an arbitrary graph G. Next iterations are then build in the same manner as graph G is constructed. We have generalized this idea even further by defining a Sierpinski product of two arbitrary graphs G and H, where we take |G| copies of a graph H and connect these according to edges in graph G. So intuitively we get a graph with local structure of H, but global structure of G. That is if we contract all copies of H, we get a copy of graph G. In the talk I will describe the Sierpinski product and related constructions, and list some of their basic properties and examples. ♦ ♦ ♦ 7. decembra 2017 o 9:50 v miestnosti M-213 Leila Parsaei Majd (Shahid Rajaee University, Teheran / UK Bratislava): Signed graphs cospectral with the path Abstrakt: A signed graph G is said to be determined by its spectrum if every signed graph with the same spectrum as G is switching isomorphic with G. It will be proved that the path P_n, interpreted as a signed graph, is determined by its spectrum if and only if n = 0, 1, or 2 (mod 4), unless n \in {8, 13, 14, 17, 29}, or n = 3. This is a joint work with Saieed Akbari, Willem H. Haemers, and Hamid Reza Maimani. ♦ ♦ ♦ 30. novembra 2017 o 9:50 v miestnosti M-213 Robert Šámal (Univerzita Karlova, Praha): 3-Flows with Large Support Abstrakt: We prove that every 3-edge-connected graph has a 3-flow that takes on a zero value on at most one sixth of the edges. The graph$K_4$demonstrates that this$1/6$ratio is best possible; there is an infinite family where$1/6$is tight. The proof involves interesting work with connectivity of the graph (relaxing to subdivisions of 2-edge-connected graphs and then reducing to cyclically 4-edge-connected ones). Joint work with M. DeVos, J. McDonald, I. Pivotto, and E. Rollova. ♦ ♦ ♦ 23. novembra 2017 o 9:50 v miestnosti M-213 Radek Hušek (Univerzita Karlova, Praha): On two flow problems Abstrakt: I will cover two main topics. The first one is group connectivity namely proving that Z_4-connectivity does not imply Z_2^2-connectivity, which answers a question suggested by Jaeger et al. [Group connectivity of graphs – A nonhomogeneous analogue of nowhere-zero flow properties, JCTB 1992]. Our proof is computer aided but uses a nontrivial enumerative algorithm. In the second part I will present our approach to the following conjecture of Matt DeVos: If there is a graph homomorphism from Cayley graph Cay(M, B) to another Cayley graph Cay(M', B') then every graph with (M, B)-flow has (M', B')-flow. This conjecture was originally motivated by the flow-tension duality. We show that a natural strengthening of this conjecture does not hold in all cases but we conjecture that it still holds for an interesting subclass of them and we prove a partial result in this direction. We also show that the original conjecture implies the existence of oriented cycle double cover with a small number of cycles. ♦ ♦ ♦ 9. novembra 2017 o 9:50 v miestnosti M-213 Dalibor Froncek (University of Minnesota Duluth): Decompositions of complete bipartite graphs into prisms revisited or Odvolávavám, co jsem odvolal, a slibuji, co jsem slíbil ♦ ♦ ♦ 26. októbra 2017 o 9:50 v miestnosti M-213 Rastislav Královič (UK Bratislava): Editovanie grafu na dve triedy Abstrakt: V prednáške nás bude zaujímať výpočtová zložitosť nasledujúceho problému, parametrizovaného dvoma triedami grafov G1, G2: pre daný graf G treba nájsť minimálny počet operácií vymazanie hrany / pridanie hrany tak, aby sme získali graf pozostávajúci z dizjunktného zjednotenia nejakého grafu z G1 a nejakého grafu z G2. Najprv ukážeme, že pre špeciálny prípad, keď G1 je trieda úplných grafov a G2 trieda grafov bez hrán je problém NP-ťažký, aj keď vstupný graf obmedzíme na triedu bipartitných grafov. Naopak, pre triedu planárnych grafov je polynomiálne riešiteľný. Ďalej spomenieme zovšeobecnenia pre editovanie na triedu "hustých" a "riedkych" grafov a budeme skúmať ich parametrizovanú zložitosť. ♦ ♦ ♦ 19. októbra 2017 o 9:50 v miestnosti M-213 Robert Lukoťka (UK Bratislava): Short cycle covers in cubic graphs and 5-cycles Abstrakt: A cycle cover of a graph is a collection of cycles such that each edge of the graph is contained in at least one of the cycles. The length of a cycle cover is the sum of all cycle lengths in the cover. We prove that every bridgeless cubic graph on m edges has a cycle cover of total length less than 1.571m. If the graph has no non-trivial 3-edge-cuts, then a cycle cover of total length less than 1.567m exists. ♦ ♦ ♦ 12. októbra 2017 o 9:50 v miestnosti M-213 Martin Máčaj (UK Bratislava): On minimal kaleidoscopic regular maps with trinity symmetry Abstrakt: It is known that the monodromy group of any regular unoriented map${\cal M}$can be uniquely (up to isomorphism) represented as an abstract group$G$with a triple$(a,b,c)$of involutory generators such that$ac=ca$. In this representation operators of duality, Petrie-duality and$e$th-hole operator can be interpreted as the change of the generating triple to the triple$(c,b,a)$,$(ac,b,c)$and$(a,(bc)^{e-1},c)$, respectively. Regular map${\cal M}$which is invariant with respect to all of the above operators (for$e$co-prime to the valency of${\cal M}$) is said to be {\em kaleidoscopic regular map with trinity symmetry (KRT)}. We say that a KRT is {\em minimal} if it covers no KRT besides itself and the trivial map. In this talk we recall how the algebraic description of regular maps and their operators can be obtained. Further, we characterize minimal KRTs as least common covers of special families of regular maps with simple monodromy groups. We also presents results of exhaustive computer search with focus on KRTs of odd valency and KRTs with simple monodromy groups. ♦ ♦ ♦ 5. októbra 2017 o 9:50 v miestnosti M-213 Edita Mačajová (UK Bratislava): Nowhere-zero flows on signed eulerian graphs Abstrakt: We generalise the well-known fact about the existence of nowhere-zero 2-flows in Eulerian graphs by showing that every signed Eulerian graph which admits an integer nowhere-zero flow has a nowhere-zero 4-flow. We also describe signed Eulerian graphs with flow number 2, 3, and 4, as well as those that do not have an integer nowhere-zero flow. The most difficult part of the proof is to characterise signed Eulerian graphs whose flow number equals 3, which requires proving a decomposition theorem for unsigned 6-regular graphs of odd order. In turn, the proof of latter result calls for the use of signed graphs as a technical tool. Finally, we discuss the existence of nowhere-zero A-flows on signed Eulerian graphs for an arbitrary Abelian group A. The talk is based on a joint work with Martin Škoviera. ♦ ♦ ♦ 11. mája 2017 o 9:50 v miestnosti M-213 Martin Máčaj (UK Bratislava): Improvements to Moore bounds for vertex-transitive graphs of given degree and diameter ♦ ♦ ♦ 27. apríla 2017 o 9:50 v miestnosti M-213 Michail Klin (Ben Gurion University, Beer Sheva, Israel): Constructive enumeration of some classes of coherent configurations: an attempt at a brief survey Abstrakt: We report about recent results, related to constructive enumeration (up to isomorphism) of some classes of coherent configurations (CC). Computer aided techniques, used by younger colleagues, goes back to the traditions of Soviet school, and in particular to Igor A.Faradzev. Special attention is payed to so-called non-Schurian objects, those, which are not related to the centralizer algebra of a suitable permutation group. For a long while the smallest known non-Schurian objects were on 15, 16 and 18 points. Non-Schurian doubly regular tornament on 15 points, due to Dima Pasechnik, will be mentioned. At the beginning, enumeration of small strongly regular designs (SRDs), in the sense of Donald Higman, will be briefly discussed, basing on the results of MK with Sven Reichard. The cantral part of the talk will be related to the enumeration of all CCs on up to 15 points (MZA). The main consequence of this enumeration is that all CCs on up to 13 points are Schurian. There exists exactly one new rank 11 non-Schurian CC M with two fibres on 14 points. There are two non_Schurian CCs on 15 points. A friendly computer free interpretation of the new CC M will be given in terms of an SRD with 8 vertices and 6 blocks. If time will allow, a history of enumeration of Schur rings over groups of order up to 64 will be considered, with special emphasis on results by MZA and Sven Reichard. ♦ ♦ ♦ 20. apríla 2017 o 9:50 v miestnosti M-213 Leila Parsaei Majd (Shahid Rajaee University, Teheran / UK Bratislava): Spectra of signed graphs Abstrakt: Let G be a signed complete or complete bipartite graph. We state some properties of the spectrum of the adjacency matrix of G. Also, if the negative edges of G form a matching, we determine the spectrum exactly. Moreover, we give two types of constructions of signed complete graphs whose spectra are symmetric. ♦ ♦ ♦ 6. apríla 2017 o 9:50 v miestnosti M-213 Petr Kovář (VŠB - Technical University of Ostrava): Applications of Magic-type Labelings Abstrakt: Magic-type labelings of graphs have been studied for about 50 years. There are literally hundreds of papers in this area. The dynamic survey on graph labelings maintained by Joe Gallian has about 90 pages just on magic-type labelings. The results include general techniques for constructions, mostly based on algebraic properties, special techniques developed for particular classes of graphs as well as necessary conditions based on parity, modularity or graph structure. In this talk we present two applications of certain magic-type labelings: scheduling tournaments and storing sparse matrices. Moreover, we summarize related results on regular distance magic graphs. ♦ ♦ ♦ 30. marca 2017 o 9:50 v miestnosti M-213 Robert Lukoťka (FMFI UK, Bratislava): 6-circuits in 2-factors of cubic graphs Abstrakt: We prove that a bridgeless cubic graph$G$of girth$6$on$n$vertices has a$2$-factor$F$such that at most$9/13 \cdot n$vertices of$G$are in circuits of length$6$of$F$. Dvořák, Kráľ, and Mohar [Z. Dvořák, D. Kráľ, B. Mohar: Graphic TSP in cubic graphs, arXiv:1608.07568] proved that every simple$2$-connected cubic graph on$n$vertices contains a spanning closed walk of length at most$9/7 \cdot n-1$. We use the technique from our proof to provide an alternative and shorter proof of this statement. Our analysis of$6$-circuits is sufficiently strong, so that limiting aspect for further improvement is the lack of analysis of the$7$-circuits. We provide a very basic analysis of$7$-circuits to show that there exists$\epsilon>0$such that every simple$2$-connected cubic graph on$n$vertices contains a spanning closed walk of length at most$(9/7 - \epsilon) \cdot n-1$. ♦ ♦ ♦ 23. marca 2017 o 9:50 v miestnosti M-213 Ján Mazák (FMFI UK, Bratislava): Circumference deficit of cubic graphs Abstrakt: The circumference deficit of a graph G is the difference between order and circumference of G. The circumference ratio of a graph G is the ratio of circumference to order of G. We observe that a snark with large resistance has large circumference deficit. By applying several recent results on resistance of snarks, we are able to construct infinite families of cyclically k-connected cubic graphs with circumference ratio less than 1 for each k between 2 and 6. We extend these results to snarks of large girth, solving a problem proposed by Markstrom. In addition, we construct a non-trivial snark of order 8k and circumference 7k+2 for each integer k above 2. This result contrasts a corollary of the dominating cycle conjecture saying that each non-trivial snark G contains a cycle of length at least 0.75|V(G)|. ♦ ♦ ♦ 9. marca 2017 o 9:50 v miestnosti M-213 Robert Jajcay (FMFI UK, Bratislava): Symmetry properties of generalized graph truncations Abstrakt: In the generalized truncation construction, one replaces each vertex of a k-regular graph G with a copy of a graph H of order k. We investigate the symmetry properties of the graphs constructed in this way, especially in connection to the symmetry properties of the graphs G and H used in the construction. We demonstrate the usefulness of our results by using them to obtain a classification of cubic vertex-transitive graphs of girths 3, 4, and 5. We also address the question of the hamiltonicity of the obtained graphs. This is joint work with Primoz Sparl from the University of Ljubljana. ♦ ♦ ♦ 2. marca 2017 o 9:50 v miestnosti M-213 Martin Škoviera (FMFI UK, Bratislava): Hamilton cycles in embedded cubic graphs Abstrakt: In this talk we develop the idea that embedding a cubic graph into a closed surface can serve as a convenient tool for finding a Hamilton cycle in it. We establish a necessary and sufficient condition for a cubic graph embedded in a closed surface, orientable or not, to have a bounding Hamilton cycle. With this characterisation and its consequences we can guarantee Hamilton cycles in wide classes of cubic graphs. Among others, we provide a unified and relatively short proof of a result due to Glover, Marusic, Kutnar, and others proved in a series of four papers published over the years 1996-2012 that cubic Cayley graphs of finite quotients of the modular group have a Hamilton path and, except in one special case, they also have a Hamilton cycle. We further show that in the remaining case these graphs have no bounding Hamilton cycle. This is a joint work with Roman Nedela. ♦ ♦ ♦ 12. decembra 2016 o 9:50 v miestnosti M-213 Robert Lukoťka (FMFI UK, Bratislava): Perfect matchings in highly cyclically connected regular graphs Abstrakt: Let$G$be a$d$-regular cyclically$(d-1+2k)$-edge-connected graph (with$k\geq 0$) of even order. A leaf matching operation (LMO) on$G$consists of removing a vertex of degree$1$together with its neighbour from$G$. We show that for any given set$X$of$d-1+k$edges, there is no$1$-factor of$G$avoiding$X$if and only if either an isolated vertex can be obtained by a series of LMO operations in$G-X$or$G-X$has an independent set that contains more than half of the vertices of$G$. We show how signed graphs are useful to verify the two conditions of the statement by proving several statements on cubic graphs. We prove that for every integer$k$, if$G$is sufficiently cyclically edge-connected, then for any three distant paths, there exists a$2$-factor of$G$that contains one of these paths. For paths of length$3$and$4$we analyse the cases when only one or two (possibly intersecting) paths are given. As a consequence, we obtain that for cyclically 7-edge-connected cubic graph$G$and a vertex$v$of$G$there exists a$2$-factor such that$v$is in cycle of length greater than$7$. This is joint work with Edita Rollová (University of West Bohemia, Pilsen, Czech Republic). ♦ ♦ ♦ 1. decembra 2016 o 9:50 v miestnosti M-213 Robert Lukoťka (FMFI UK, Bratislava): Short cycle covers of graphs Abstrakt: Let G be a bridgeless graph. A circuit cover \CC of G is a collection of circuits such that each edge of G is contained in some circuit from \CC. The length of \CC is the sum of the lengths of the circuits from \CC. The problem of finding short circuit cover can be reduced to weighted cubic graph (where the weights represent lengths of the edges). We show that a bridgeless cubic unweighted graph G has a circuit cover of total length at most 1.6 |E(G)|. Stronger bounds can be obtained if the structure of 5-circuts in G is restricted or when higher cyclic connectivity is assumed. ♦ ♦ ♦ 24. novembra 2016 o 9:50 v miestnosti M-213 Roman Nedela (University of West Bohemia, Pilsen): Cayley recognition problem for graphs on 4p vertices Abstrakt: In the context of several algorithmic problems, we shall discuss results about the complexity of the Cayley recognition and the Cayley isomorphism problems. We shall present a new result, done in the collaboration with I. Ponomarenko, that for graphs on 4p vertices these problems can be solved in a polynomial time. In our proof, as is the case also in the recent Babai's result on the complexity of the graph isomorphism problem, the Weisfeiler-Leman stabilisation algorithm producing the smallest coherent algebra for a prescribed set of integer matrices plays an important role. ♦ ♦ ♦ 10. novembra 2016 o 9:50 v miestnosti M-213 Stefko Miklavic (University of Primorska, Koper): Matching extendability of Deza graphs Abstrakt: Let$\Gamma$be a connected graph. A matching$M$of$\Gamma$is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex. A vertex of$\Gamma$is matched by a matching$M$if it is an endpoint of one of the edges in$M$. A perfect matching of$\Gamma$is a matching which matches all vertices of$\Gamma$. Graph$\Gamma$of even order is$n$-extendable, if (i) it contains a matching of size$n$and (ii) every such matching is contained in a perfect matching of$\Gamma$. In this talk we will review known results about extendability of strongly regular graphs, distance-regular graphs and Deza graphs. ♦ ♦ ♦ 27. októbra 2016 o 9:50 v miestnosti M-213 Primož Šparl (University of Ljubljana): On n-distance-balanced graphs Abstrakt: Distance-balanced graphs (that is graphs in which for every pair of adjacent vertices u and v the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u) have been studied to some extent in recent years, investigating different structural properties of such graphs and also the connection of this property to symmetries of graphs. In this talk we present a very natural generalization of the concept of distance-balanced graphs to so-called n-distance-balanced graphs, which was first introduced by Boštjan Frelih in 2014. We discuss some basic properties of n-distance-balanced graphs, give examples of such graphs and present a characterization of such graphs of small diameter. We also discuss the n-distance-balanced property for some well-known families of graphs such as the family of generalized Petersen graphs and pose a number of open problems. This is joint work with Štefko Miklavič. ♦ ♦ ♦ 20. októbra 2016 o 9:50 v miestnosti M-213 Soňa Pavlíková (STU, Bratislava): Inverses of graphs Abstrakt: In the first part of the talk we deal with simple labeled graphs with non-zero labels in a ring. If the adjacency matrix of such a graph is invertible, its inverse is an adjacency matrix of another graph, the inverse of the original graph. If the ring is ordered, then balanced inverses - those with a positive product of labels along every cycle - are of interest. We introduce the concept of a derived labeled graph and show how it can be embedded into an inverse. We also prove a new result on balanced inverses of labeled trees and present a construction of new labeled graphs with balanced inverses from old. In the second part we investigate the so-called positively and negatively invertible graphs. The class of negatively invertible graphs turns out to contain models of important organic molecules and invertibility allows to derive bounds on the binding energy of such molecules. We will present a fairly general construction of new invertible graphs based on bridging' a pair of invertible graphs, which, informally, means joining' the pair by a new bipartite graph attached to the two graphs at suitable subsets of vertices. This is a joint work with Daniel Ševčovič. ♦ ♦ ♦ 13. októbra 2016 o 9:50 v miestnosti M-213 Christian Rubio-Montiel (UK, Bratislava): On crossing families Abstrakt: A geometric graph is a graph drawn in the plane such that its n vertices are points in general position, and its edges are straight-line segments. Two edge-disjoint geometric subgraphs *cross* if there is an edge in the first subgraph and an edge in the second subgraph that have an interior point in common. A set of edge-disjoint geometric subgraphs is called *mutually crossing* if any two of their elements cross. We show that for any geometric complete graph there always exists a set of mutually crossing 2-paths (paths of length 2) of size at least \sqrt{n/2}, and a set of mutually crossing claw graphs (a star of tree leaves) of size at least n/6. This is a joint work with Dolores Lara (Departamento de Computación, CINVESTAV, Mexico). ♦ ♦ ♦ 29. septembra 2016 o 9:50 v miestnosti M-213 Robert Jajcay (FMFI UK, Bratislava): Improving Moore bounds through counting cycles Abstrakt: The Cage Problem is the problem of finding the smallest$k$-regular graphs of girth$g$, called$(k,g)$-cages, for any parameter pair$k,g \geq 3$. Moore bounds are very natural lower bounds on the orders of cages that have been around since the introduction of the Cage Problem in the 1960's. Even though they are generally assumed to be rather poor predictors of the actual orders of cages, no significant improvements on these lower bounds are known to date. In our talk, we present a technique for improving the Moore bounds based on counting cycles of lengths close to the girth$g$in graphs of orders close to the Moore bounds. The numbers of these cycles together with certain divisibility constraints allow us to exclude specific orders of potential cages for infinite families of parameter pairs$k,g$. We present an overview of the use of this technique in the context of cages as well as some recent results obtained in collaboration with Tatiana Jajcayova and Slobodan Filipovski. ♦ ♦ ♦ 19. mája 2016 o 9:50 v miestnosti M-213 Gyorgy Kiss (Eotvos Lorand University (ELTE), Budapest): Resolving sets in finite geometries Abstrakt: A resolving set for a graph is a collection of its vertices such that all vertices are uniquely determined by their distances to the chosen vertices. The metric dimension of a graph G is the smallest size of a resolving set for G. The resolving sets are interesting objects in their own right, but their study is also motivated by the straightforward inequality stating that the metric dimension of a graph gives an upper bound on the base size of its automorphism group. In the talk we consider resolving sets for the incidence graphs of various symmetric designs, in particular projective, affine and biaffine planes and generalized quadrangles. We give lower estimates on their metric dimensions and construct several different resolving sets. The estimates come from nontrivial double counting arguments and from deep theorems about the sizes of double blocking sets, while the constructions are based on the geometric properties of the designs. This is a joint work with D. Bartoli, T. Heger and M. Takats. ♦ ♦ ♦ 12. mája 2016 o 9:50 v miestnosti M-213 Roman Nedela (UMB Banská Bystrica): Constructive approach to automorphism groups of planar graphs Abstrakt: By Frucht's Theorem, every abstract finite group is isomorphic to the automorphism group of some graph. In 1975, Babai characterized which of these abstract groups can be realized as the automorphism groups of planar graphs. In the talk, we give a more detailed and understandable description of these groups. We describe stabilizers of vertices in connected planar graphs as the class of groups closed under the direct product and semidirect products with symmetric, dihedral and cyclic groups. The automorphism group of a connected planar graph is obtained as semidirect product of a direct product of these stabilizers with a spherical group. As a result we get a characterization similar to the Jordan's characterization of automorphism groups of trees. Our approach is based on the decomposition to 3-connected components (a modified Trachtenbrot decomposition) and gives a quadratic-time algorithm for computing the automorphism group of a planar graph. This is a joint work with P. Klavik and P. Zeman. ♦ ♦ ♦ 5. mája 2016 o 9:50 v miestnosti M-213 Edita Rollová (ZCU Plzeň): New proof of Seymour's 6-flow theorem Abstrakt: In 1981, Seymour proved that it is possible to assign values 1,2,3,4,5 to edges of an oriented graph in such a way that for every vertex the sum of incoming values equals the sum of outgoing ones. In this talk we will present a new proof of this theorem that uses induction. This is a joint work with Matt DeVos and Robert Šámal. ♦ ♦ ♦ 28. apríla 2016 o 9:50 v miestnosti M-213 Štefan Gyűrki (UMB Banská Bystrica): From strongly regular graphs to directed strongly regular graphs Abstrakt: In this talk we discuss strongly regular graph from combinatorial and algebraic points of view. We review their main properties, related open problems, and their impact on other areas of mathematics. A possible generalization to the directed case will be given at the end of the talk. ♦ ♦ ♦ 14. apríla 2016 o 9:50 v miestnosti M-213 Marcel Abas (STU Bratislava): Large Cayley graphs of diameter two Abstrakt: In this talk we present a construction of Cayley graphs of diameter two with order 200/289 (d+1)^2 for every degree d=17n-1, where n=1 (mod 10) is a prime. In addition, using explicit estimates for the distribution of primes in arithmetic progressions, we show that for every degree d>=360756 there is a Cayley graph of diameter two and of order at least 0.684 d^2. ♦ ♦ ♦ 7. apríla 2016 o 9:50 v miestnosti M-213 Anna Dresslerová (FMFI UK, Bratislava): L(2,1)-labelling of cacti Abstrakt: An L(2,1)-labelling is a labelling of the vertex set of graph with non-negative integers such that the labels of adjacent vertices differ by at least 2 and the labels of vertices at distance 2 are distinct. It is required to determine, for a given graph G, the smallest integer k such that G admits an L(2,1)-labelling with integers not exceeding k; this invariant is denoted by$\lambda(G)$. Determining$\lambda(G)$is known to be a hard problem. To test whether$\lambda(G) \leq k$is NP-complete even for series-parallel graphs. On the other hand, there exist classes of graphs where this problem is polynomially solvable (e.g. trees or their mild generalisations). In this talk we derive tight upper and lower bounds for the$\lambda$-number of cacti. We also present a polynomial-time algorithm which computes the$\lambda$-number of an arbitrary cycle-tree (cactus with disjoint cycles). ♦ ♦ ♦ 31. marca 2016 o 9:50 v miestnosti M-213 Jitka Doležalová (Univerzita Palackého, Olomouc): Eye-tracking technology and scanpath comparison using graph visualization Abstrakt: Eye Tracking technology is a rapidly developing area used in manyscientific disciplines. The presentation will be about basic concepts of Eyetracking, interesting practical uses and applications of graph theory in the data evaluation. ♦ ♦ ♦ 17. marca 2016 o 9:50 v miestnosti M-213 Lev Glebsky (Universidad Autonoma, San Luis Potosi, Mexico): Approximations of discrete groups by finite ones Abstrakt: The plan of my talk is as follows: 1. Almost homomorphisms and approximations of groups. 2. Metric approximations of discrete groups. Topological approximations. Equivalent definitions. 3. Sofic groups. Hyperlinear groups. Weakly sofic groups. Linear sofic groups. 4. Equations over groups. Kervaire-Laudenbach conjecture. 5. SQ-universality, congruence extension property, and soficity. The nonstandard extension of a free group. 6. If time permits I will touch the approximations of topological groups. ♦ ♦ ♦ 10. marca 2016 o 9:50 v miestnosti M-213 Christian Rubio-Montiel (Instituto de Matematicas, UNAM, Mexico a UK, Bratislava): "ab-Perfect graphs" Abstrakt: A graph G is called ab-perfect if a(H) equals b(H) for any induced subgraph H of G and any two different parameters "a" and "b" of G. With this definition, perfect graphs are the wX-perfect graphs where "w" is the clique number and "X" is the chromatic number. In this presentation, we give forbidden graphs characterizations for several classes of ab-perfect graphs when "a" and "b" are parameters related to the clique number, complete colorings - any two colors have an edge in common - and the Hadwiger number - the order of the largest complete minor of a graph. We also show that some classes of graphs such as chordal graphs, cographs and trivially perfect graphs are a type of ab-perfect graphs. ♦ ♦ ♦ 3. marca 2016 o 9:50 VÝNIMOČNE v posluchárni C Jan Goedgebeur (Ghent University, Belgium): Generation of cubic graphs and snarks Abstrakt: In this talk we will present a new algorithm for the efficient generation of all non-isomorphic cubic graphs. We will also show how this algorithm can be extended for the efficient generation of all non-isomorphic snarks. Snarks are of interest since for a lot of interesting open conjectures it can be proven that if the conjecture is false, the smallest possible counterexamples will be snarks. Our implementation of this algorithm to generate snarks is more than 30 times faster than former generators for snarks. Using this generator we were able to generate all snarks up to 36 vertices. The new list of snarks allowed us to find counterexamples for several published open conjectures. ♦ ♦ ♦ 25. februára 2016 o 9:50 v miestnosti M-213 Martin Škoviera (FMFI UK Bratislava): A reduction theorem for 6-connected eulerian graphs Abstrakt: We prove that every 6-edge-connected eulerian graph of order n >= 2 containing a vertex of degree 6 can be transformed into a 6-edge-connected eulerian graph of order n-1 by removing the vertex and reinstating regularity. A similar result also holds when 6 is replaced with 4 or 2. We conjecture that 6 can be replaced by any even positive number. This is a joit work with Edita Macajova. ♦ ♦ ♦ 10. decembra 2015 o 9:50 v miestnosti M-213 Mariusz Meszka (AGH Kraków): Block colorings of designs Abstrakt: A Steiner system S(2,k,v) is a design (V,β) where V is a set of v points and β is a collection of k-element subsets of V called blocks such that every 2-element subset of V is contained in exactly one block. In a system (V,β), any set of pairwise disjoint blocks makes a partial parallel class. A partial parallel class that partitions V is a parallel class ; if a partial parallel class partitions V \ {x} for some point x then it is called an almost parallel class. A proper block coloring of a design (V,β) is a mapping c : β → C such that for any two blocks B,B′ ∈ β, if c(B) = c(B′) then B ∩ B′ = Ø. The minimum number of colors needed to color blocks in (V,β) is called its chromatic index. Basic results and open problems in proper block colorings of designs will be discussed, mostly in the case of Steiner systems S(2,k,v) for k = 3 (i.e. Steiner triple systems) and for k = 4. In particular, classes of systems for which the chromatic index attains its minimum will be presented. Special attention will be given to projective triple systems. Let Wm be an (m + 1)-dimensional vector space over F2 and ⊕ be an operation of vector addition in Wm (performed modulo 2 componentwise). A projective triple system (V,β) is a Steiner triple system in which each point in V is represented by a non-zero vector in Wm and every two distinct points, corresponding to vectors x and y, define a unique triple formed by {x,y,x⊕y}. The exact value for the chromatic index of projective triple systems will be determined, together with a polynomial time algorithm to obtain such a coloring. In relation to proper block coloring, main results on the existence of parallel classes and almost parallel classes in Steiner systems S(2,k,v) will be discussed. ♦ ♦ ♦ 26. novembra 2015 o 9:50 v miestnosti M-213 Robert Jajcay (FMFI UK, Bratislava): k-regular families of automorphisms and generalized Cayley graphs Abstrakt: A family F of automorphisms of a vertex-transitive graph G is said to be k-regular if for every pair u,v of vertices of G there exist k automorphisms in F mapping u to v. Every vertex-transitive graph admits a k-regular family for some positive k, and quasi-Cayley graphs are vertex-transitive graphs admitting a 1-regular family of automorphisms. We investigate the class of merged Johnson graphs with regard to the parameter k, classify merged Johnson graphs that are Cayley, and relate this topic to that of the existence of a uniform routing. ♦ ♦ ♦ 19. novembra 2015 o 9:50 v miestnosti M-213 Katarína Hrináková (SvF STU): Orientably-regular maps on the group$M(q^2)$Abstrakt: A map is a cellular embedding of a graph into a compact surface. Regular maps are those with highest possible level of symmetry - whose automorphism groups act regularly on their flag sets. In this talk we will present an enumeration of orientably-regular maps with automorphism group isomorphic to the group$M(q^2)$- so called twisted linear fractional group. We will also mention some open questions about external symmetries (e.g. self-duality) of these regular maps. (This is a joint work with G. Erskine and J. Širáň.) ♦ ♦ ♦ 12. novembra 2015 o 9:50 VÝNIMOČNE v posluchárni C Primož Potočnik (University of Ljubljana): Cubic vertex-transitive graphs Abstrakt: A few years ago, Gabriel Verret, Pablo Spiga, and myself compiled a complete list of all connected vertex-transitive graphs of valence 3 on not more than 1280 vertices. In my talk, I will try to explain how this was done. ♦ ♦ ♦ 5. novembra 2015 o 9:50 v miestnosti M-213 Martin Škoviera (FMFI UK): Permutation snarks Abstrakt: A permutation snark is a cubic graph with no 3-edge-colouring that contains a 2-factor consisting of two induced circuits. In the talk we analyse the basic properties of permutation snarks, focusing on the structure of edge-cuts of size 4 and 5. As an application of our knowledge we provide rich families of cyclically 4-edge-connected and 5-edge-connected permutation snarks of order 8n+2 for each integer n >= 2 and n >= 4, respectively, superseding a recent work of J. Hagglund and A. Hoffmann-Ostenhof. This talk reports an ongoing research with Edita Macajova. ♦ ♦ ♦ 22. októbra 2015 o 9:50 v miestnosti M-213 Roman Nedela (UMB, Banská Bystrica): Celočíselné toky na grafoch, Jakobián a počet kostier grafu" Abstrakt: V prednáške zavedieme dôležitý algebraický invariant grafu - Jakobián. Pre daný graf G jeho Jakobián Jac(G) je istá konečná abelovská grupa definovaná grafom G. Ukážeme, ako Jakobián grafu súvisí s celočíselnými tokmi na grafoch a ako ho vypočítať. Je známe, že počet kostier súvislého grafu je rovný počtu prvkov Jakobiánu. Teda na kostrách grafu môžeme definovať operáciu sčitovania, avšak nie je jasné, ako to urobiť prirodzeným spôsobom. Kombinatorický význam ďalších invariantov Jakobiánu nie je známy (napríklad rank, alebo maximálny rád prvku). Jakobián grafu sa pekne správa vzhľadom na isté špeciálne typy grafových epimorfizmov, ktoré nazývame harmonické morfizmy. Otvorená je aj otázka odvodenia Jakobiánu v tvare rozkladu na cyklické grupy pre niektoré jednoduché triedy grafov. ♦ ♦ ♦ 15. októbra 2015 o 9:50 v miestnosti M-213 Martin Máčaj (FMFI UK): Siamese color graphs on 40 vertices Abstrakt: A Siamese color graph on$40$is an edge decomposition of$K_{40}$into the spread (i.e.,$10$vertex disjoint cliques of order$4$)$S$and four$6$-valent distance regular graphs (DRGs) such that each DRG together with the spread form a strongly regular graph with parameters$(40,12,2,4)$. We present a motivanion for the study of Siamese color graphs stemming from generalized quadrangles and Steiner system and provide the full classification of objects on$40$points. Talk is based on a joint project with M. Klin, S. Reichard and A. Woldar. ♦ ♦ ♦ 1. októbra 2015 o 9:50 VÝNIMOČNE v posluchárni C Alexander Rosa (McMaster University, Kanada): "Decomposing complete graphs into circulants" Abstrakt: Circulants are important class of vertex-transitive graphs. They have a vast number of applications, for example in telecommunication networking, they are used as models for interconnection networks etc. We discuss the problem of when does the complete graph admit a decomposition into subgraphs each of which is isomorphic to a fixed given circulant. ♦ ♦ ♦ 15. júna 2015 o 9:50 v miestnosti M-213 Joe Ryan (University of Newcastle, Australia): "The Degree Diameter Problem in a Host Architecture" Abstrakt: The degree diameter problem is concerned with finding the largest order graph subject to constraints on degree and diameter. This problem celebrated its 50th birthday last year and the paucity of results indicates that it will be around for much longer. Apart from the trivial cases (degree = 1 or 2, and diameter = 1) only 7 graphs are known to be largest possible. A sub-problem is to look at the degree diameter problem as subgraphs of some host architecture. We present here some results and open problems on the degree diameter subgraph problem as applied to the multi-dimensional rectangular mesh, multi-dimensional honeycomb mesh and the triangular grid. The problem is also well suited to families of directed, oriented and mixed graphs. We will present bounds on the oriented rectangular and oriented triangular grids. Recent work in the field can be accessed in [1, 2, 3, 4]. References: 1. A. Dekker, H. Perez-Roses, G. Pineda-Villavicencio, and P. Watters: "The maximum degree & diameter-bounded subgraph and its applications", Journal of Mathematical Modelling and Algorithms 11 no. 3, pp.249268, 2012 2. Holub, P., Miller, M., Perez-Roses, H., Ryan, J.: "Degree Diameter Problem on Honeycomb Networks", Discrete Applied Mathematics, Vol 179 31 pp.139-151, 2014 3. Holub, P., Ryan, J.: "Degree Diameter Problem on Triangular Networks", Australasian Journal of Combinatorics, in print 4. Miller, M., Perez-Roses, H., Ryan, J.: "The maximum degree & diameter-bounded subgraph in the mesh", Discrete Applied Mathematics, Vol.160, pp.1782-1790, 2012 ♦ ♦ ♦ 21. mája 2015 o 9:50 v miestnosti M-213 Steve Wilson (University of Primorska (SI) a Northern Arizona University (USA)): "Semi-Transitive Orientations of Dart-transitive Graphs" Abstrakt: A semi-transitive orientation of a graph$\Gamma$is a digraph$\Delta$, disjoint from its reverse, such that$Aut(\Delta)$is transitive on the vertices and on the edges of$\Gamma$. If$Aut(\Gamma) = Aut(\Delta)$then we say that$\Gamma$is 1/2-transitive ( or 1/2-arc-transitive). These are graphs of interest to a lot of us. But in this talk, I would like to explore the opposite direction: Given a graph whose group is known to be transitive on darts (directed edges), when does it have a semi-transitive orientation? How many might it have? Can it have non-isomorphic orientations? etc. ♦ ♦ ♦ 14. mája 2015 o 9:50 v miestnosti M-213 Alena Bachratá (FMFI UK): "Využitie teórie grafov pri hľadaní optimálnych návrhov experimentov" Abstrakt: Navrhovanie experimentov slúži na optimalizáciu množstva informácie získanej z experimentu, pri daných vstupných podmienkach a ohraničeniach. Potreba optimalizácie množstva získanej informácie vznikla kvôli finančnej a časovej náročnosti niektorých experimentov. My sa zameriame na blokové návrhy experimentov, ktoré vieme reprezentovať pomocou párovacích grafov. Vďaka tomu vieme niektoré úlohy z teórie navrhovania experimentov previesť na úlohy z teórie grafov a naopak. Na ilustráciu využitia tohto prepojenia predstavíme výsledky pánov Constantineho a Kelmansa. Týkajú sa grafov s max. počtom kostier a sú založené na práci s vlastnými číslami Laplaciánov. Využitím a rozšírením postupov týchto pánov sme odvodili nové triedy optimálnych návrhov experimentu. Na záver ukážeme namerané výsledky z algoritmu na hľadanie optimálnych návrhov, vďaka ktorým sme vyvrátili jednu hypotézu o silno regulárnych grafoch. ♦ ♦ ♦ 30. apríla 2015 o 9:50 VÝNIMOČNE v posluchárni C Gareth Jones (University of Southampton, Veľká Británia): "Enumerating regular objects using Moebius inversion in groups" Abstrakt: The enumeration and classification of many regular objects, such as maps, hypermaps, polytopes and covering spaces, with a given automorphism group G, can be reduced to the problem of counting epimorphisms from a certain finitely generated group \Gamma onto G. Philip Hall's theory of Moebius inversion in groups, an algebraic analogue of the inclusion-exclusion principle, reduces this further to the simpler problem of counting homomorphisms from \Gamma to G, and this can often be solved directly or by using character theory. I shall describe the general theory, followed by recent progress, and applications to maps on surfaces, where G belongs to certain families of finite simple groups, such as the Suzuki groups. (Joint work with Martin Downs.) ♦ ♦ ♦ 23. apríla 2015 o 9:50 v miestnosti M-213 Istvan Estelyi (University of Primorska & University of Ljubljana): "Which Haar graphs are Cayley graphs?" Abstrakt: Haar graphs are regular covering graphs of dipoles. They can also be constructed in a Cayley graph-like manner, in terms of a group G and its subset S. Just like Cayley graphs, these graphs frequently appear in various constructions, due to their desirable symmetry properties. For example, Haar graphs were used for constructing families of semi-symmetric graphs and cages. If G is an abelian group, then its Haar graphs are well-known to be Cayley graphs; however, there are examples of non-abelian groups G and subsets S when this is not the case. Thus it might be worth investigating the Cayley-ness and more generally the vertex-transitivity of Haar graphs. In this talk we address the problem of classifying finite non-abelian groups G with the property that every Haar graph of G is a Cayley graph. We will deduce an equivalent condition for a Haar graph of G be a Cayley graph of a group containing G in terms of G, S, and Aut(G). Moreover, the above problem will be solved for dihedral groups. ♦ ♦ ♦ 16. apríla 2015 o 9:50 v miestnosti M-213 Yan Wang (Yantai University, Yantai, China): "Frobenius maps" Abstrakt: A graph is called Frobenius if it is a connected orbital regular graph of a Frobenius group. A Frobenius map is a regular Cayley map whose underlying graph is a Frobenius graph. In this talk we show that almost all low-rank Frobenius graphs admit regular embeddings and enumerate non-isomorphic Frobenius maps for a given Frobenius graph. As a result, we produce some Frobenius maps with trivial exponent groups. This is a joint work with Jin Ho Kwak. ♦ ♦ ♦ 9. apríla 2015 o 9:50 v miestnosti M-213 Martin Bachratý (FMFI UK): "Approaching the Moore bound for diameter 2 and 3 by Cayley graphs" Abstrakt: The largest order of a graph of maximum degree$d$and diameter$k$cannot exceed the Moore bound, which has the form$M(d,k)=d^k - O(d^{k-1})$for$d$going to infinity and any fixed$k$. Known results in finite geometries on generalised polygons imply, for$k=2,3,5$, the existence of an infinite sequence of values of$d$such that$n(d,k)=d^k - o(d^k)$. This shows that for$k=2,3,5$the Moore bound can be approached asymptotically; moreover, no such result is known for any other value of$k>1$. The corresponding graphs are, however, far from vertex-transitive, and there appears to be no obvious way to extend them to vertex-transitive graphs giving the same type of asymptotic result. We show that for diameters$2$and$3$the Moore bound can be approached asymptotically by Cayley graphs using generalized polygons. This is a joint work with Jozef Siran and Jana Siagiova. ♦ ♦ ♦ 26. marca 2015 o 9:50 v miestnosti M-213 Kenta Ozeki (National Institute of Informatics, Tokio): "Spanning bipartite quadrangulations of triangulations of surfaces" Abstrakt: The well-known Four Color Theorem can be translated to the following statement: "Every plane triangulation G has two spanning (bipartite) quadrangulations such that each edge in G belongs to at least one of them." For triangulations of non-spherical surfaces, although 4 colors do not suffice, we would like to find some properties that are "close" to the 4-colorability. Then, in this talk, as an analogy to the Four Color Theorem in the sense of the above, we will consider whether a triangulation of a surface has a spanning bipartite quadrangulation. Note that this is the dual form of the problem of finding a perfect matching M in a cubic graph on a surface such that M satisfies a certain topological property (namely Z_2-homology). We will explain the above problem for the case of even triangulations of the projective plane and the torus, and introduce several problems. This is a joint work with Atsuhiro Nakamoto (Yokohama National University) and Kenta Noguchi (Keio University). ♦ ♦ ♦ 19. marca 2015 o 9:50 v miestnosti M-213 Martin Škoviera (FMFI UK): "The cyclic connectivity of a "snipped" cubic graph" Abstrakt: We study the effect of removing a pair of adjacent vertices on the cyclic connectivity of a cubic graph. In general, removing a pair of adjacent vertices cannot decrease cyclic connectivity by more than two. Our main result states that - apart from three exceptional graphs that include the Petersen graph - every bridgeless cubic graph contains a pair of adjacent vertices whose removal decreases cyclic connectivity by at most one. Our research is motivated by the study of the existence of long cycles in embedded cubic graphs and its relationship to maximum genus of a graph. This is a joint work with M. Kotrbcik and R. Nedela. ♦ ♦ ♦ 5. marca 2015 o 9:50 v miestnosti M-213 Martin Máčaj (FMFI UK): "On small strongly regular graphs with an automorphism of order$3$" Abstrakt: A$k$-regular graph of order$n$is said to be strongly regular with parameters$(n,k,\lambda,\mu)$if each pair of adjacent vertices has exactly$\lambda$common neighbors and each pair of non-adjacent vertices has exactly$\mu$common neighbors. There exist several necessary conditions for parameter sets to admit the existence of a strongly regular graph. Parameter sets satisfying all of them are called feasible. Although the existence of a strongly regular graph is solved for all feasible parameter sets with$n\leq 50$, the complete classification is still open for parameter sets$(37,18,8,9)$,$(41,20,9,10)$,$(45,22,10,11)$,$(49,24,11,12)$,$(49, 18, 7,6)$and$(50,21,8,9)$. By exhaustive computer search we obtain a full list of strongly regular graphs on up to$50$vertices with an automorphism of order$3$. Further, for parameter sets$(37,18,8,9)$,$(41,20,9,10)$,$(45,22,10,11)$,$(49,24,11,12)$,$(49, 18, 7,6)$and$(50,21,8,9)$we determine a class of strongly regular graphs which contains all the$Z_3$graphs and is closed under particular instances of partial switching defined by Godsil-McKay and Behbahani-Lam-Ostergaard, respectively. As a corollary, we significantly extend list of known regular two-graphs on at most$50$vertices. (Joint work with A. Koval.) ♦ ♦ ♦ 26. februára 2015 o 9:50 v miestnosti M-213 prof. Alexander Mednykh (Sobolev Institute of Mathematics, Novosibirsk State University, Russia): "On the Hurwitz type theorems for groups acting on a graph" Abstrakt: During the past decade, many papers devoted to discrete versions of the theory of Riemann surfaces have appeared. The role of Riemann surfaces and holomorphic mappings in these theories is played by finite graphs and harmonic mappings. For these theories, various versions of the Riemann-Hurwitz for mula have been obtained and analogues of the Riemann-Roch theorem have been proved. Many other theorems of the classical theory of Riemann surfaces have also been carried over to the discrete case. In particular, the upper and lower bounds for the order of a group acting harmonically (i.e., without fixed semiedges) on a graph of given genus were found. This result can be regarded as a discrete analogue of well known theorems of Hurwitz (1893) and Accola-Maclachlan (1968), which give sharp upper and lower bounds for the order of an automorphism group acting on a Riemann surface. The purpose of this report is to provide discrete versions of theorems of Wiman (1895), Oikawa (1956), and Arakawa (200), which sharpen Hurwitz' upper bound for various classes of groups acting on a Riemann surface of given genus. ♦ ♦ ♦ 18. decembra 2014 o 9:50 VÝNIMOČNE v posluchárni C Martin Máčaj (FMFI UK): "Two-graphs, regular two-graphs and related topics" Abstrakt: A two-graph is a set of (unordered) triples chosen from a finite vertex set X, such that every (unordered) quadruple from X contains an even number of triples of the two-graph. A regular two-graph has the property that every pair of vertices lies in the same number of triples of the two-graph. In the talk we present connections between two-graphs and various other combinatorial objects, for example Eulerian graphs, conference matrices, and systems of equiangular lines. ♦ ♦ ♦ 11. decembra 2014 o 9:50 VÝNIMOČNE v posluchárni C Martin Škoviera (FMFI UK): "The chromatic number of a signed graph" Abstrakt: In 1982, Zaslavsky introduced the concept of a proper vertex colouring of a signed graph G as a mapping f:V(G) >Z such that for each edge uv the colour f(u) is different from the colour s(uv)f(v), where is s(uv) is the sign of the edge uv. The substantial part of Zaslavsky's research concentrated on polynomial invariants related to signed graph colourings rather than on the behaviour of colourings of individual signed graphs. We continue the study of signed graph colourings by proposing the concept of a chromatic number for signed graphs as a natural extension of the chromatic number of an unsigned graph. We establish the basic properties of this invariant, provide bounds in terms of the chromatic number of the underlying unsigned graph, investigate the chromatic number of signed planar graphs, and prove an analogue of the celebrated Brooks theorem. This is a joint work with Edita Macajova and Andre Raspaud. ♦ ♦ ♦ 4. decembra 2014 o 9:50 VÝNIMOČNE v posluchárni C Stanislav Jendroľ (UPJŠ, Košice): "A unified approach to several types of edge colourings of plane graphs" ♦ ♦ ♦ 13. novembra 2014 o 9:50 VÝNIMOČNE v posluchárni C Robert Jajcay (FMFI UK, Bratislava): "On r-regular families of graph automorphisms" Abstrakt: An$r$-regular family$\F$of permutations on a set$V$contains for each pair of vertices$u,v \in V$exactly$r$permutations$f \in \F$mapping$u$to$v$,$f(u)=v$. Previously,$1$-regular families of graph automorphisms were used by Gauyacq to characterize the quasi-Cayley graphs; a class of vertex-transitive graphs that properly contains the class of Cayley graphs, shares many characteristics of the Cayley graphs, and is properly contained in the class of vertex-transitive graphs. We introduce the concept of$r$-regular families to cover all vertex-transitive graphs, and to serve as a measurement of how far a vertex-transitive graph is from being Cayley. As any automorphism group of a graph$ \Gamma=(V,E)$acting transitively on$V$with a vertex-stabilizer of order$r$can be easily seen to form an$r$-regular family on$V$, every vertex-transitive graph admits an$r$-regular family of automorphisms for some$r \geq 1$. ♦ ♦ ♦ 30. októbra 2014 o 9:50 VÝNIMOČNE v posluchárni C Ján Mazák (FMFI UK, Bratislava): "Circumference of cubic graphs" Abstrakt: The talk focuses on the circumference of cubic graphs with given cyclic edge-connectivity. The circumference deficit of a graph$G$is the difference between order and circumference of$G$. The circumference ratio of a graph$G$is the ratio of its circumference to the order.We observe that a snark with large resistance has a large circumference deficit. Together with our recent results on resistance, this gives a construction of infinite families of cyclically$k$-edge-connected cubic graphs with circumference ratio less than$1$for each$k\in\{2,3,4,5,6\}$. We extend these results for snarks of large girth, solving a problem proposed by Markstrom et al. In addition, we construct a family of non-trivial snarks of order$8k$and circumference$7k+2$for each integer$k\ge 3$. This result contrasts a corollary of the well-known dominating cycle conjecture saying that each non-trivial snark$G$contains a cycle of length at least$3/4\cdot |V(G)|$. This is a joint work with Edita Máčajová. ♦ ♦ ♦ 23. októbra 2014 o 9:50 VÝNIMOČNE v posluchárni C Robert Lukoťka (FMFI UK, Bratislava): "Short cycle covers of cubic graphs" Abstrakt: A cycle cover of a graph G is a collection of cycles in G such that every edge from E(G) is contained in at least one of the cycles. A long open conjecture of Alon and Tarsi states that every bridgeless graph on m edges has a cycle cover of length at most 1.4m. The best known general result for bridgeless graphs is a cycle cover of total length at most 5m/3 [Alon and Tarsi 1985; Bermond, Jackson, and Jaeger 1983]. The nowhere zero 5-flow conjecture implies existence of a cycle cover of length at most 1.6m [Jamshy, Raspaud, and Tarsi 1987]. The best result for bridgeless cubic graphs up to date is by Kaiser et al. (2010) giving a cycle cover of length at most 34m/21 ~ 1.619m. We show that a bridgeless cubic graph G with m edges has a cycle cover of length at most 1.6m. If G contains no circuits of length 5, then it has a cycle cover of length at most 14/9m ~ 1.556m. This is a joint work with B. Candrakova. ♦ ♦ ♦ 9. októbra 2014 o 9:50 VÝNIMOČNE v posluchárni C Barbora Candráková (FMFI UK, Bratislava): "Traveling salesman problem on cubic graphs" Abstrakt: The traveling salesman problem (TSP) is to find a Hamilton cycle of minimum cost in a complete weighted graph. We consider a special case of TSP, a graphic TSP, where the weights of edges in the complete graph correspond to the lengths of the shortest paths between vertices of some graph$G$. Hence we are looking for the shortest trail in$G$that contains all vertices of$G$. We call such trail a traveling salesman tour. We further restrict ourselves to bridgeless cubic graphs. We show that if$G$is a simple connected bridgeless cubic graph on$n \ge 8$vertices, then$G$has a traveling salesman tour of length at most$1.3n - 2$. This tour can be constructed in polynomial time. ♦ ♦ ♦ 2. októbra 2014 o 9:50 VÝNIMOČNE v posluchárni C Edita Mačajová (FMFI UK, Bratislava): "Bridgeless cubic graphs are (7,2)-edge-choosable" Abstrakt: A graph G is called (r, s)-edge-choosable if for every assignment of sets of size r to the edges of G it is possible to choose for every edge an s-element subset from its set such that the subsets chosen for any pair of adjacent edges are disjoint. The list fractional chromatic index of a graph G is the infimum of all numbers r/s for which G is (r, s)-edge-choosable. Mohar http://www.fmf.uni-lj.si/~mohar--> (June 2003) posed a problem asking whether every cubic graph is (7,2)-edge-choosable. In 2009, Cranston and West [SIAM J. Discrete Meth., 23 (2009), pp. 872–881] showed that every 3-edge-colorable cubic graph is (7,2)-edge-choosable and gave a sufficient condition with the help of which they proved that many non-3-edge-colorable cubic graphs are (7,2)-edge-choosable. In this paper we prove that every bridgeless cubic graph is (7,2)-edge-choosable. We show that this result cannot be improved in the family of all cubic graphs, in the sense that there exists a cubic graph with list fractional chromatic index 7/2. The original question of Mohar remains open, and we further pose several related problems. ♦ ♦ ♦ 29. mája 2014 o 9:50 v miestnosti M-213 Andre Raspaud (LaBRI, Universite de Bordeaux): "Incidence coloring of graphs with high maximum average degree" Abstrakt: An incidence of an undirected graph G is a pair$(v,e)$where$v$is a vertex of$G$and$e$an edge of$G$An incidence of an undirected graph G is a pair$(v,e)$where$v$is a vertex of$G$and$e$an edge of$G$incident with$v$. Two incidences$(v,e)$and$(w,f)$are adjacent if one of the following holds: (i)$v=w$, (ii)$e=f$or (iii)$vw=e$or$f$. An incidence coloring of$G$assigns a color to each incidence of$G$in such a way that adjacent incidences get distinct colors. In this talk we present bounds for incidence chromatic number of graphs having high maximum average degree. In particular we prove that every graph with maximum degree at least$7$and with maximum average degree strictly less than$4$admits a$(\Delta+3)$-incidence coloring. This result implies that every triangle free planar graph with maximum degree at least$7$is$(\Delta+3)$-incidence colorable. ♦ ♦ ♦ 15. mája 2014 o 9:50 v miestnosti M-213 Martin Knor (STU Bratislava): "Wiener index of iterated line graphs of trees" Abstrakt: We study the equation$W(L^i(T))=W(T)$, where$T$is a tree,$L^i$is the$i$-iterated line graph operator and$W$stands for the Wiener index, that is, the sum of all distances in a graph. Melnikov and Dobrynin conjectured that the equation has no solution for$i\ge 3$. We prove their conjecture for$i\ge 4$, while for$i=3$we find a class of trees$T$satisfying$W(L^3(T))=W(T)$. Moreover, we prove that trees not belonging to this strictly determined class do not satisfy the equality. The work is based on 7 joint papers with Riste Skrekovski, Primoz Potocnik and Martin Macaj. ♦ ♦ ♦ 10. apríla 2014 o 9:50 v miestnosti M-213 Eduard Eiben (UK, Bratislava): "Structure of equimatchable graphs" Abstrakt: A graph G is equimatchable if any matching of G is a subset of a maximum-size matching. It is well known that any 2-connected equimatchable graph is either bipartite, or factor critical, and that these two classes are disjoint. The structure of factor-critical equimatchable graphs with a cut-vertex and 2-cut was investigated in [J. Graph Theory, 10(4):439-448, 1986.]. We extend these results and for all$k\ge 3$we describe the structure of factor-critical equimatchable graphs with a k-vertex-cut. For every$k\ge 3$, we prove that if a k-connected equimatchable factor-critical graph G has at least 2k+3 vertices and a k-cut S such that G-S has two components with sizes at least 3, then G-S has exactly two components and both are complete graphs. Consequently, such graphs have independence number 2 and differ from an union of two complete graphs by at most k^2/3 edges. Additionally, we provide also a characterisation of k-connected equimatchable factor-critical graphs with a k-cut S such that G-S has a component with size at least k and a component with size 1 or 2. Finally, we show that if every minimum cut S separates a component with size at most two, then the independence number can be arbitrarily high and the number of components can be as high as |V(S)|. ♦ ♦ ♦ 3. apríla 2014 o 9:50 v miestnosti M-213 Martin Škoviera (UK, Bratislava): "Hamiltonovské kružnice v osekaných trianguláciách uzavretých plôch (Hamilton cycles in truncated triangulations of closed surfaces)" Abstrakt: A truncated triangulation is a 3-valent map on a closed surface S arising from a triangulation of S by truncating each vertex, that is, by expanding it into a contractible cycle. Several years ago, Glover and Marusic implicitly employed truncation of highly symmetrical triangulations of orientable surfaces as a tool for proving the existence of Hamilton cycles in large classes of cubic Cayley graphs. We generalise their method by replacing high symmetry with a somewhat surprising weaker condition - upper embeddability of the dual cubic graph. Our result enables us to construct Hamilton cycles in much wider classes of cubic graphs. For example, we show that the truncation of a triangulation of any closed surface with no separating 3-cycle has a Hamilton cycle whenever the number of faces is 2 (mod 4) and has a cycle missing only two adjacent vertices whenever the number of faces is 0 (mod 4). This is a joint work with Michal Kotrbcik and Roman Nedela. ♦ ♦ ♦ 20. marca 2014 o 9:50 v miestnosti M-213 Robert Lukoťka (Trnavská univerzita): "Zakázané a prikázané hrany v perfektných páreniach vo vysoko súvislých regulárnych grafoch" Abstrakt: Známy výsledok Plesníka hovorí, že v (d-1)-hranovo-súvislom d-regulárnom grafe existuje perfektné párenie, ktoré neobsahuje žiadnu z d-1 dopredu zvolených hrán. V prednáške sa budeme zaoberať otázkou, či a za akých podmienok je možné zakázať viac hrán za predpokladu vyššej cyklickej hranovej súvislosti. Dokážeme, že v d-regulárnom cyklicky k-hranovo-súvislom grafe (k>=d-1) môžeme nájsť perfektné párenie neobsahujúce dopredu zvolenú množinu X nanajvýš (d+k-1)/2 hrán okrem dvoch situácií: 1. Po odstránení množiny X vieme pomocou niekoľkých operácií spárovania vrchola stupňa 1 dostať izolovaný vrchol (t.j. odstránením množiny X sme vytvorili malú konfiguráciu vylučujúcu perfektné párenie, napr. izolovaný vrchol). 2. Bez množiny X graf obsahuje nezávislú množinu obsahujúcu viac ako polovicu vrcholov (t.j. graf je takmer bipartitný). Výsledok podobného typu získame o prikázaných hranách. Ako aplikáciu výsledku ukážeme, že pre každý vrchol v cyklicky 7-súvislom kubickom grafe existuje 2-faktor taký, že tento vrchol je v cykle dĺžky aspoň 8. V záverečnej časti prednášky ukážeme, že v takomto grafe existuje 2-faktor, v ktorom je lineárne veľa vrcholov v kružniciach dĺžky väčšej ako 7. ♦ ♦ ♦ 13. marca 2014 o 9:50 v miestnosti M-213 Barbora Candráková (UK, Bratislava): "Avoiding 5-circuits in a 2-factor of a cubic graph" Abstrakt: We show that every bridgeless cubic graph G on n vertices other than the Petersen graph has a 2-factor with at most 2(n-2)/15 circuits of length 5. An infinite family of graphs attains this bound. We also show that G has a 2-factor with at most n/5.83 odd circuits. This improves the previously known bound of n/5.41 [Lukotka, Macajova, Mazak, and Skoviera: Small snarks with large oddness, arXiv:1212.3641 ♦ ♦ ♦ 6. marca 2014 o 9:50 v miestnosti M-213 Katarína Tureková (UK, Bratislava): " Grafy blízke moorovským grafom" Abstrakt: Moorovský graf s priemerom dva je silno regulárny graf s parametrami (n,k,0,1). Takýto graf má k^2+1 vrcholov a je to aj najväčší možný k-regulárny graf s priemerom 2 a súčasne najmenší možný k-regulárny graf s obvodom 5. Budeme demonštrovať výsledky a techniky spektrálnej teórie grafov na probléme existencie moorovských grafov priemeru dva z článku A.J. Hoffman and R.R. Singleton. On moore graphs with diameter 2 and 3. IBM J. Res. Develop., 4:497 504, 1960. Podobne na základe článkov P. Erdös, S. Fajtlowicz, and A. J. Hoffman. Maximum degree in graphs of diameter 2. Networks, 10(1):87 90, 1980 W.G. Brown. On the non-existence of a type of regular graphs of girth 5. Canadian Journal of Mathematics, 19:644 648, 1967. preskúmame existenciu k-regulárnych grafov s priemerom 2 s k^2 vrcholmi a k-regulárnych grafov s obvodom 5 s k^2 + 2 vrcholmi. ♦ ♦ ♦ 27. februára 2014 o 9:50 v miestnosti M-213 Martin Máčaj (UK, Bratislava): "Blokové grafy steinerovských systémov trojíc" Abstrakt: Blokový graf steinerovského systému trojíc S=(V,B) je graf, ktorého vrcholmi sú práve bloky systému S a v ktorom sú dva bloky spojené hranou práve vtedy, keď majú spoločný bod. Na vlastnostiach takýchto blokových grafov ilustrujeme metódy a výsledky z článku R. C. Bose: Strongly Regular Graphs, Partial Geometries, and Partially Balanced Designs, Pac. J. Math. 13 (1963), 389-419 týkajúce sa geometrických a pseudogeometrických silne regulárnych grafov. Prednáška neobsahuje algebru. ♦ ♦ ♦ 5. decembra 2013 o 9:50 v miestnosti M-213 Katarína Hrináková (Skrovinová) (STU, Bratislava): "Self-dual, self-Petrie-dual, and Möbius regular maps on linear fractional groups" Abstrakt: Maps are cellular embeddings of graphs on compact surfaces. Regular maps are maps with highest possible level of symmetry. A map is regular if its automorphism group acts regularly on the set of its flags. Enumeration and classification of regular maps is usually approached in three different ways - by supporting surfaces, by underlying graphs, and by automorphism groups. In this talk we focus on regular maps whose automorphism group is isomorphic to${\rm PSL}(2,q)$and${\rm PGL}(2,q)$and will characterize those maps which are self-dual, self-Petrie-dual, or Möbius. ♦ ♦ ♦ 28. novembra 2013 o 9:50 v miestnosti M-213 Marthe Bonamy (LIRMM, Montpellier, Francúzko): "Coloring the squares of graphs" Abstrakt: The problem of coloring squares of graphs (or square coloring graphs) has been extensively studied since a 1977 conjecture by Wegner, still widely open. The square of a graph is the same graph with additional edges between every pair of vertices that share a neighbor. After introducing the topic, we focus on three questions on which progress was recently made: • Does list coloring make a difference? (Kostochka, Woodall '01) We overview examples of squares of graphs on which list coloring makes a difference, which were discovered this year by Kim and Park, and later generalized by two different groups of people. • How sparse does a graph have to be, for its square to be colorable with very few colors? (Wang, Lih '03) We survey results on planar graphs with large girth by Borodin et al. over the last few years, and present joint work with Benjamin Lévêque and Alexandre Pinlou which generalizes them to graphs with no assumption on planarity. • Do many squares of graphs require a lot of colors? (Cranston, Kim'08) We discuss the question, which was answered negatively by Cranston and Rabern this month, and mention joint work with Nicolas Bousquet which generalizes the result to any powers of graphs. ♦ ♦ ♦ 21. novembra 2013 o 9:50 v miestnosti M-213 Štefan Gyűrki (STU, Bratislava): "Directed strongly regular graphs as Cayley digraphs over wreath product groups" Abstrakt: The notion of a directed strongly regular graph was introduced by Duval as a possible generalization of classical strongly regular graphs. A directed strongly regular graph (DSRG) with parameters$(n,k,\mu,\lambda,t)$is a regular directed graph on$n$vertices with degree$k$such that every vertex is incident with$t$undirected edges, and the number of paths of length 2 directed from a vertex$x$to a vertex$y$is$\lambda$if there is an arc from$x$to$y$, and$\mu$otherwise. It had been proven by J\o rgensen that a DSRG cannot be a Cayley digraph over an Abelian group. However, there are known several infinite families of DSRGs as Cayley digraphs over semidirect product groups. In this talk we will introduce the first two infinite families over wreath product groups. ♦ ♦ ♦ 7. novembra 2013 o 9:50 v miestnosti M-213 Prof. Eckhard Steffen (Universität Paderborn): "Circular flows on regular graphs" Abstrakt: The following two results of Tutte will be the starting point of the talk. 1. A cubic graph$G$is bipartite if and only it has a nowhere-zero 3-flow. 2. A cubic graph is 3-edge-colorable if and only if it has a nowhere-zero 4-flow. In the first part of the talk we generalize these results to nowhere-zero circular flows on (2t+1)-regular graphs. In the second part we consider related results on signed (2t+1)-regular graphs. ♦ ♦ ♦ 24. októbra 2013 o 9:50 v miestnosti M-213 Kristína Kováčiková (Univerzita Komenského): "Two disjoint odd cycles theorem (K. Kawarabayashi & K. Ozeki)" Abstrakt: The talk will present a result of K. Kawarabayashi and K. Ozeki. They give a new proof of the disjoint odd cycle theorem which characterizes graphs without two vertex-disjoint odd cycles. The advantage of this proof is its length and simplicity. Unlike the original one from 1990, it does not depend on any result for matroids. The authors use only the well known two path theorem. ♦ ♦ ♦ 10. októbra 2013 o 9:50 v miestnosti M-213 Robert Jajcay (Univerzita Komenského): "Where to go with cages" Abstrakt: Cages are extremal graphs with respect to given degree and diameter. During the last ten years, we have seen a revival of interest in this topic partially due to the introduction of algebraic and topological methods into the area. In our presentation, we will present a review of these recent developments, mention some of the harder and more fundamental problems that should be addressed next, and generally discuss the direction for further research of the Cage Problem. The talk is meant to attract both colleagues and graduate students into the area. ♦ ♦ ♦ 3. októbra 2013 o 9:50 v miestnosti M-213 Robert Lukoťka (Trnavská univerzita): "Entropy compression method" Abstrakt: Entropy compression je metóda založená na fakte, ze náhodnú postupnosť n bitov nemožno injektívne zobraziť tak, aby mal výsledok menej ako n bitov. V posledných niekoľkých rokoch bola táto metóda použitá pri dôkazoch viacerých zaujimavých výsledkov. Použitie metódy ukážeme na dvoch tvrdeniach. 1. Ukážeme, že logická formula v konjunktívnej normálnej forme, ktorej klauzy majú dĺžku nanajvýš$k$a pretínajú sa nanajvýš s 2^(k-C) inými klauzami (kde C je vhodná konštanta), je splniteľná. 2. Každý graf s maximálnym stupňom \Delta možno zafarbiť 4(\Delta-1) farbami tak, že neexistuje cyklus používajúci iba dve farby. ♦ ♦ ♦ 26. septembra 2013 o 9:50 v miestnosti M-213 Martin Škoviera (FMFI UK Bratislava): "Nikde-nulové toky na signovaných kubických grafoch" Abstrakt: Klasické výsledky Williama Tutta o tokoch na kubických grafoch z 50-tych rokov minulého storočia charakterizujú kubické grafy, ktoré pripúšťajú nikde-nulový 3-tok alebo 4-tok. Podobné výsledky pre signované grafy, čo je prekvapujúce, neboli doteraz známe. V prednáške odvodíme charakterizácie kubických signovaných grafov, ktoré pripúšťajú nikde-nulový 3-tok alebo 4-tok alebo toky v abelovských grupách rádu 3 a 4. Väčšina našich charakterizácií využíva signatúru ekvivalentnú s konštantne negatívnou signatúrou známou ako "antibalansovaná". Poukážeme aj na nezvyčajné správanie tokov na signovaných grafoch s hodnotami v konečných abelovských grupách a vyslovíme niekoľko problémov pre ďalší výskum. Prednáška je založená na spoločnej práci Edity Máčajovej a prednášajúceho. ♦ ♦ ♦ 20. júna 2013 o 9:50 v miestnosti M-213 Prof. Gabriela Araujo-Pardo (Instituto de Matematicas, Universidad Nacional Autonoma de Mexico): "Some topics related to projective planes" Abstrakt: We define projective planes and present several results on colorations and graph theory related with them. In particular, we give an overview of the following topics: 1. The upper chromatic number and specifically the balanced upper chromatic number in projective planes. 2. The notion of the achromatic and pseudoachromatic numbers for the linear graph of the complete graph and their relation to projective planes and, 3. A brief description of cages of girth six and their relation with projective planes. ♦ ♦ ♦ 16. mája 2013 o 9:50 v miestnosti M-213 prof. Roman Nedela (Univerzita Mateja Bela): "Maximálny rod, decyklačné číslo a hamiltonicita kubických grafov" Abstrakt: Autor vo svojej prednáške predstaví niektoré známe aj menej známe súvislosti týkajúce sa vlastností kubických grafov uvedených v názve. ♦ ♦ ♦ 9. mája 2013 o 9:50 v miestnosti M-213 prof. Wilfried Imrich (Montanuniversitaet, Leoben, Rakúsko): "Motion conjectures for infinite graphs" Abstrakt: This talk is concerned with automorphism breaking of finite and infinite graphs. In 1996, Albertson and Collins introduced the distinguishing number D(G) of a graph G as the least cardinal d such that G has a labeling with d labels that is only preserved by the trivial automorphism. This concept has spawned numerous papers on finite and infinite graphs. Here we focus on the infinite motion conjecture of Tom Tucker and generalizations. In particular, we present results pertaining to the conjecture, a generalization to uncountable graphs, and results that support the conjecture and its generalizations. ♦ ♦ ♦ 25. apríla 2013 o 9:50 v miestnosti M-213 Marcel Abas (STU, Bratislava): "Cayley graphs of diameter two and order$1/2 d^2$for all degrees$d$" Abstrakt: The number of vertices of a graph of diameter two and maximum degree$d$is at most$d^2+1$. This number is the Moore bound for diameter two. The order of largest Cayley graphs of diameter two and degree$d$is denoted by$C(d,2)$. The only known construction of Cayley graphs of diameter 2 valid for all degrees$d$gives$C(d,2)>\frac14 d^2+d$. However, there is a construction yielding Cayley graphs of diameter 2, degree$d$and order$d^2-O(d^{\frac32})$for an infinite set of degrees$d$of a special type. In our talk we present a construction giving$C(d,2)\geq\frac12 d^2-k$for$d$even and of order$C(d,2)\frac12(d^2+d)-k$for$d$odd,$0\leq k\leq 8$. In addition, we show that, in asymptotic sense, the most of record Cayley graphs of diameter two are obtained by our construction. ♦ ♦ ♦ 18. apríla 2013 o 9:50 v miestnosti M-213 Robert Jajcay (FMFI UK, Bratislava): "Improving Moore bounds through counting cycles" Abstrakt: The Cage Problem is the problem of finding the smallest$k$-regular graphs of girth$g$, called$(k,g)$-cages, for any parameter pair$k,g \geq 3$. Moore bounds are very natural lower bounds on the orders of cages that have been around since the introduction of the Cage Problem in the 1960's. Even though they are generally assumed to be rather poor predictors of the actual orders of cages, no significant improvements on these lower bounds are known to date. In our talk, we present a technique for improving the Moore bounds based on counting cycles of lengths close to the girth$g$in graphs of orders close to the Moore bounds. The numbers of these cycles together with certain divisibility constraints allow us to exclude specific orders of potential cages for infinite families of parameter pairs$k,g$. We present an overview of the use of this technique in the context of cages as well as some recent results obtained in collaboration with Tatiana Jajcayová. ♦ ♦ ♦ 11. apríla 2013 o 9:50 v miestnosti M-213 Martin Máčaj (FMFI UK, Bratislava): "Vertex-transitive graphs of given degree and diameter" Abstrakt: A$(k;D)$-graph is a (finite, simple)$k$-regular graph of diameter$D$. The Degree/Diameter Problem is the problem of determining the order$n(k;D)$of the largest$(k;D)$-graphs. The well-known Moore bound serves as an upper bound on the order of$(k;D)$-graphs. In terms of$k$and$D$, it can be stated as follows:$M(k; g) = 1 + k + k(k - 1) + \dots + k(k-1)^{D-1}.$In our talk we show that for any fixed degree$k\geq 3$and any positive integer$K$the largest vertex-transitive$(k;D)$graph has size at most$M(k;D)-K$for almost all (in the asymptotic sense) diameters$D$. This is a joint work with G. Exoo, R. Jajcay and J. Širáň. ♦ ♦ ♦ 4. apríla 2013 o 9:50 v miestnosti M-213 Štefan Gyűrki (STU, Bratislava): "On certain directed strongly regular graphs of order 18, 36 and 10" Abstrakt: The notion of a directed strongly regular graph was introduced by Duval as a possible generalization of classical strongly regular graphs. A directed strongly regular graph (DSRG) with parameters$(n,k,\mu,\lambda,t)$is a regular directed graph on$n$vertices with degree$k$such that every vertex is incident with$t$undirected edges, and the number of paths of length 2 directed from a vertex$x$to a vertex$y$is$\lambda$if there is an arc from$x$to$y$, and$\mu$otherwise. In this talk, first we repeat several feasibility conditions for parameter sets given by Duval. We will focus on a special case of DSRGs, namely, if$\lambda=0$and$\mu=1$. Besides an infinite family of such DSRGs there are known just two more digraphs with these parameters: one of order 18, the second of order 108. The latter was just recently constructed by L. Jorgensen. We are also giving an explanation of these graphs in the terms of biaffine planes. Finally, we show how we obtained new DSRGs on 36 vertices from these digraphs using several different techniques (voltage assignments, mergings in association schemes) known from algebraic graph theory. (This is joint work with M. Klin, Ben Gurion University, Beer Sheva, Israel) ♦ ♦ ♦ 21. marca 2013 o 9:50 v miestnosti M-213 Eduard Eiben (FMFI UK, Bratislava): "2-Connected Equimatchable Graphs on Surfaces" Abstrakt: A graph$G$is equimatchable if every maximal matching of$G$is maximum. It is known that any$2$-connected equimatchable graph is either bipartite or factor-critical. We prove that for any vertex$v$of a$2$-connected factor-critical equimatchable graph$G$and a minimal matching$M$that isolates$v$the graph$G-(M\cup v)$is either$K_{2n}$or$K_{n,n}$for some$n$. We use this result to improve the upper bounds on the maximum size of$2$-connected equimatchable factor-critical graphs embeddable in the orientable surface of genus$g$to$c\sqrt g+5$if$g\ge 3$where$c\le 12$is constant for any fixed$g\ge 3$and to$4\sqrt g+17$if$g\le 2$. Moreover, for any nonnegative integer$g$we construct a$2$-connected equimatchable factor-critical graph with genus$g$and more than$4\sqrt{2g}$vertices, which estabilishes that the maximum size of such graphs is$\Theta(\sqrt g)$. Similar bounds are obtained for nonorientable surfaces. In addition, we construct arbitrarily large$2$-connected equimatchable bipartite graphs with orientable genus$g$, and similar graphs with nonorientable genus$h$, for all nonnegative integers$g$and$h$. Finally, we investigate planar$2$-connected factor-critical equimatchable graphs. ♦ ♦ ♦ 14. marca 2013 o 9:50 v miestnosti M-213 Jakub Daubner (ESET, spol. s r.o., Bratislava): "Neighbourhood of Constant Order in the Interval Graph of a Random Boolean Function" Abstrakt: We estimate the size of the neighbourhood of constant order$u$in the interval graph of an$n$-ary random Boolean function. The interval graph is useful for finding a minimal DNF of a Boolean function. Its vertices correspond to maximal sub-cubes in the graph of a Boolean function, and two vertices are joined by an edge whenever the corresponding sub-cubes have a non-empty intersection. The neighbourhood of order$u$of a given vertex is the set of all vertices whose minimal distance from the vertex is at most$u$. Our estimate on the size of the neighbourhood is approximately$n^{u.lg(log_{1/p}(n)}$where$lg$denotes the binary logarithm. So far, no reasonable bound of this parameter has been known. ♦ ♦ ♦ 7. marca 2013 o 9:50 v miestnosti M-213 Ján Mazák (Trnavská univerzita): "Small snarks with large oddness" Abstrakt: We estimate the minimum number of vertices of a cubic graph with given oddness and cyclic connectivity. We prove that a bridgeless cubic graph$G$with oddness$\omega(G)$other than the Petersen graph has at least$(5+1/4)\omega(G)$vertices, and for each integer$k$with$2\le k\le 6$we construct an infinite class of cubic graphs with cyclic connectivity$k$and small oddness ratio$|V(G)|/\omega(G)$. In particular, for cyclically$4$-connected snarks we improve the upper bound on oddness ratio to$13$from the previously known bound of$15$, and for cyclically$6$-connected snarks we improve the ratio to$99$from$118$. In addition, we construct a cyclically$4$-connected snark of girth$5$with oddness$4$on$44$vertices, improving the best previous value of$46$. ♦ ♦ ♦ 28. februára 2013 o 9:50 v miestnosti M-213 Alexander Mednykh (Sobolev Institute of Mathematics, Novosibirsk State University): "Branched coverings of graphs and related topics" Abstrakt: In this lecture we give a short survey of old and new results about branched coverings of graphs. This notion was introduced independently by many authors. Branched coverings of graphs are also known as harmonic maps or vertically holomorphic maps of graphs. The main idea of the present talk is to create a parallel between classical results on branched coverings of Riemann surfaces and those for graphs. We introduce the notion of a harmonic automorphism for a graph and discuss the Hurwitz upper bound on the number of harmonic automorphisms. Then we define a hyperelliptic graph as a two-fold branched covering of a tree. A few discrete versions of the Farkas and Accola theorems about hyperellipticity of coverings over genus two Riemann surface will be given. ♦ ♦ ♦ 6. decembra 2012 o 9:50 v miestnosti M-213 Barbora Candráková (FMFI UK, Bratislava): "How Many Conjectures Can You Stand? A Survey. (H.J.Broersma, Z.Ryjacek, P.Vrana)" Abstrakt: We survey results and open problems in hamiltonian graph theory centered around two conjectures of the 1980s that are still open: every 4-connected claw-free graph (line graph) is hamiltonian. These conjectures have lead to a wealth of interesting concepts, techniques, results and equivalent conjectures. ♦ ♦ ♦ 29. novembra 2012 o 9:50 v miestnosti M-213 Kristína Kováčiková (FMFI UK, Bratislava): "4-Vertex Condition in Strongly Regular Graphs" Abstrakt: We present a result of M. D. Hestenes and D. G. Higman from the paper "Rank$3$Groups and Strongly Regular Graphs". Let$G$be a strongly regular graph and let$x$and$y$be two arbitrary vertices from$G$. The authors show that for the ordered pair$[x,y]$the number of different types of subgraphs of order$4$that contain$x$and$y$only depends on whether$[x,y]$is an edge or a non-edge. The problem is related to the study of properties of highly symmetric graphs. ♦ ♦ ♦ 22. novembra 2012 o 9:50 v miestnosti M-213 Michal Kotrbčík (FMFI UK Bratislava): "Minimum Genus of Cartesian Products of Triangles" Abstrakt: The minimum genus problem is a classical albeit NP-complete problem in topological graph theory. Minimum genus of cartesian products is closely related to the minimum genus of a group - the minimum among genera of all Cayley graphs of the given group. For abelian groups, the most difficult case arises when the group contains a Z_3 factor in its canonical decomposition. In this talk we focus mainly on the genus of$G_n$, the cartesian product of$n$triangles, which is the Cayley graph of the direct product of$n$copies of$Z_3$. Characteristic features of the problem of determining the genus of$G_n$are a significant level of symmetry of the graphs, very large problem space, and absence of readily available methods. In this talk we discuss several results on both lower and upper bounds on the genus of$G_n$, as well as computational aspects of the problem. Moreover, we introduce several new invariants - (strong) symmetric genus of a Cayley graph, genus range of a group, and (strong) symmetric genus of a group, and consider their relationship with the genus of$G_n$and other known invariants. This is a joint work with T. Pisanski. ♦ ♦ ♦ 15. novembra 2012 o 9:50 v miestnosti M-213 Robert Lukoťka (Trnavská univerzita): "Carsten Thomassen - The weak 3-flow conjecture" Abstrakt: The weak 3-flow conjecture states that there exists a fixed integer k, such that each k-connected graph has a nowhere-zero 3-flow. We demonstrate the basic techniques that C. Thomasen used to prove this conjecture. ♦ ♦ ♦ 8. novembra 2012 o 9:50 v miestnosti M-213 Martin Knor (STU Bratislava): "Efektívna dominancia v kubických vrcholovo-tranzitívnych grafoch" Abstrakt: Hovoríme, že vrchol x dominuje vrchol y ak je x=y alebo ak je xy hrana grafu. Nech je G graf a S je podmnožina jeho vrcholov. Potom S dominuje G efektívne, ak je každý vrchol grafu G dominovaný jediným vrcholom z S. Takáto efektívne dominujúca množina S je vlastne 1-kod. Mobiov pásik$M_n$je kubický graf, ktorý vznikne z kružnice na$2n$vrcholoch pridaním perfektného párovania spájajúceho protiľahlé vrcholy kružnice. Využitím algebraického prístupu, pomocou liftov, sme dokázali, že súvislý kubický graf na 2^m vrcholoch nemá efektívnu dominančnú množinu jedine vtedy, keď je to Mobiov pásik. Prezentované výsledky sú zo spoločnej práce s Primozom Potocnikom (Univ. Ljubljana). ♦ ♦ ♦ 25. októbra 2012 o 9:50 v miestnosti M-213 Edita Rollová (UK Bratislava): "Pokrytia signovaných grafov signovanými kružnicami" Abstrakt: Pokrytie kružnicami resp. cyklami pre daný graf$G$je taká množina kružníc$\mathcal{C}$grafu$G$, že každá hrana$G$je obsiahnutá aspoň v jednej kružnici z$\mathcal{C}$. Signovaný graf je graf, ktorého každá hrana má znamienko + alebo -. Pre signované grafy rozlišujeme dva druhy kružníc balansovanú a nebalansovanú. Balansovaná (nebalansovaná) kružnica je taká, ktorá má párny (nepárny) počet znamienok. Preto je prirodzenou otázkou ako zadefinovať signovanú kružnicu, aby pokrytia signovanými kružnicami pre signované grafy boli nielen zovšeobecnením pokrytí kružnicami pre grafy, ale spĺňali aj ďalšie vlastnosti ako napríklad priamy súvis s nikde-nulovými tokmi. Odpoveď na túto otázku prichádza z Teórie matroidov. Signovaná kružnica je balansovaná kružnica alebo tzv. nebalansovaná dvojkružnica, čo je súvislý signovaný graf pozostávajúci z dvoch dizjunktných nebalansovaných kružníc prepojených cestou. Pokrytie signovaného grafu signovanými kružnicami je potom taká množina signovaných kružníc, že každá hrana signovaného grafu je obsiahnutá aspoň v jednej z nich. V takomto prípade celopozitívny signovaný graf zodpovedá grafu bez znamienok, keďže neobsahuje nebalansovanú kružnicu a teda ani dvojkružnicu. V prednáške okrem iného dokážeme, že ak má signovaný graf pokrytie signovanými kružnicami, potom existuje také pokrytie, že súčet dĺžok všetkých jeho signovaných kružníc je nanajvýš$11|E(G)|$. Navyše z dôkazu tvrdenia vyplýva, že každá hrana signovaného grafu je takýmto pokrytím pokrytá nanajvýš 11-krát. Prezentované výsledky sú spoločnou prácou s E. Máčajovou, A. Raspaudom a M. Škovierom. ♦ ♦ ♦ 18. októbra 2012 o 9:50 v miestnosti M-213 Štefan Gyűrki (STU Bratislava): "Four infinite families of non-Schurian association schemes of order 2p^2" Abstrakt: Association schemes are one of the traditional areas of investigation in algebraic graph theory. Catalogues of all small association schemes are available from the website of Hanaki and Miyamoto. It is known that all association schemes of order up to 14 are Schurian, that is, they are coming from suitable transitive permutation groups in the standard manner. The first examples of non-Schurian association schemes exist on 15, 16, and 18 vertices. In particular, there are only two examples of non-Schurian association schemes of order 18. Starting from a successful computer-free interpretation of these two examples, and using extensive computer algebra experimentation in conjunction with further reasoning, we are able to show the existence of at least four infinite families of non-Schurian association schemes of order 2p^2 (for p prime, p>3). In this lecture I will start from a consideration of the two initial examples on 18 points, and describe some auxiliary coherent configurations. Then the four infinite families of association schemes will be presented. We will discuss some of their properties, as well as their links with certain known objects in extremal graph theory, for example with McKay-Miller-Siran graphs. This is joint work with M. Klin. ♦ ♦ ♦ 11. októbra 2012 o 9:50 v miestnosti M-213 Štefan Gyűrki (STU Bratislava): "An introduction to association schemes" Abstrakt: Association schemes are one of the traditional areas of investigation in algebraic graph theory. In this talk we give a short introduction to the concept of association schemes. These objects could be independently defined in the language of matrices, binary relations, or color graphs. A significant family of association schemes, so-called Schurian association schemes, can be constructed from transitive permutation groups. More interesting association schemes are those which cannot be obtained in this manner. We will also associate three more groups with an association scheme: its combinatorial group of automorphisms, group of color automorphisms, and the group of algebraic automorphisms. ♦ ♦ ♦ 4. októbra 2012 o 9:50 v miestnosti M-213 Martin Škoviera (KI FMFI UK, Bratislava): "Eulerian trails in regular graphs of odd order" Abstrakt: Every vertex$v$in a connected$2d$-regular graph$G$divides any eulerian trail$T$into$d$closed subtrails$T_1,T_2,...,T_d$based at$v$. If$G$has odd order, the number of edges of$G$is$d$times an odd number, so one may ask whether$T$and$v$can be chosen in such a way that all the subtrails$T_i$have odd length. The answer is trivially positive for$d=1$, and is positive also for$d=2$. We show that for$d=3$the answer is again positive, and explain why this case is important for determining the flow number of an arbitrary signed eulerian graph. Our methods extend to proving more general results about decompositions of eulerian graphs into two or three closed trails of odd length based at the same vertex under similar assumptions. This is a joint work with Edita Mačajová. ♦ ♦ ♦ 27. septembra 2012 o 9:50 v miestnosti M-213 Alex Rosa (McMaster University, Hamilton, Kanada): "Ringel a Kotzig po 50 rokoch" Abstrakt: Blíži sa 50-te výročie vôbec prvej skutočne významnej medzinárodnej konferencie z teórie grafov v Smoleniciach. Zborník z tejto konferencie je dodnes významným zdrojom zásadných článkov a problémov z tejto oblasti. V prednáške sa budeme zaoberať dvoma takýmito dodnes otvorenými problémami, ktoré na konferencii sformuloval Gerhard Ringel, respektíve Anton Kotzig. ♦ ♦ ♦ 20. septembra 2012 o 9:50 v miestnosti M-213 Tomáš Kaiser (Západočeská univerzita, Plzeň): "Algebraické souvislosti věty o čtyřech barvách" Abstrakt: Pozoruhodným rysem věty o čtyřech barvách je značný počet jejích ekvivalentních formulací, z nichž některé se na první pohled týkají rovinných grafů nebo barevnosti pouze okrajově. Přednáška bude věnována souvislosti této věty s teorií uzlových invariantů určených Lieovými algebrami. Připomeneme také Penroseův kalkulus tenzorových diagramů, na který zmíněná teorie navazuje. S tématem je úzce spjat Penroseův polynom, o jehož definici a známých vlastnostech se rovněž zmíníme. Přednáška bude pojata jako úvod do této oblasti a nepředpokládá hlubší algebraické znalosti. ♦ ♦ ♦ 17. mája 2012 o 9:50 v miestnosti M-213 Edita Rollová (FMFI UK): "Circuit covers of signed graphs that admit a nowhere-zero$2$-flow" Abstrakt: A circuit cover of a graph$G$is a collection$\mathcal{C}$of circuits such that each edge of$G$belongs to at least one circuit from$\mathcal{C}$. There is a natural analogue of this concept for signed graphs, graphs where each edge is either positive or negative. As suggested by matroid theory, a signed circuit is either a single circuit with an even number of negative edges, or a pair of disjoint circuits with an odd number of negative edges each, joined with a path. It can be shown that a signed graph has a circuit cover if and only if it admits a nowhere-zero integer flow. In the talk we will mention several bounds on the length of a shortest circuit cover in a signed graph$G$, depending on the existence of a nowhere-zero$k$-flow in$G$. In particular we show that a signed graph$G$that admits a nowhere-zero$2$-flow has a circuit cover with total length at most$\frac{4}{3}\cdot |E(G)|$. This bound is tight for infinitely many graphs. This is a joint work with Edita Máčajová, Andre Raspaud a Martin Škoviera. ♦ ♦ ♦ 10. mája 2012 o 9:50 v miestnosti M-213 Lucia Haviarová (FMFI UK): "Vlastnosti intervalového grafu boolovskej funkcie" Abstrakt: Cieľom prezentácie je popísať vzťahy medzi intervalovým grafom boolovskej funkcie, skrátenou disjunktívnou normálnou formou a minimálnou disjunktívnou normálnou formou tejto funkcie. ♦ ♦ ♦ 3. mája 2012 o 9:50 v miestnosti M-213 Gert Sabidussi (Universite de Montreal): "Euclidean unit-distance graphs and pathological selfmaps of euclidean space of low dimension" Abstrakt: A remarkable but widely unknown theorem of Beckman and Quarles (1954) states that if a map f of R^d (d>1) into itself preserves unit distance (i.e. for any x,y in R^d, dist(x,y) = 1 implies dist(f(x),f(y)) = 1), then f is an isometry. Does this property also hold when one considers unit-distance preserving selfmaps of rational euclidean space Q^d? The talk will explore some relations of the Beckman-Quarles theorem with colouring and connectivity problems in metric graph theory. ♦ ♦ ♦ 19. apríla 2012 o 9:50 v miestnosti M-213 Katarína Škrovinová a Kristína Kováčiková: "Rick's Tricky Six Puzzle" (after a paper of A. Fink and R. Guy) Abstrakt: Many people have already encountered the Fifteen Puzzle. The child game with the goal to order fifteen labeled blocks placed in the square of size four times four, where one position is empty. The notoriety of the puzzle derives from the impossibility of being able to swap the positions of 14 and 15. One possible representation of the$n$-Puzzle is a graph on$n+1$vertices (one for every labeled block and one for the empty space). The edges of the graph will present the neighborhood of blocks. Rick Wilson's theorem states that (apart from simple polygons, nonseparable graphs and the graph that is the subject of our talk) the group of permutations of attainable positions is either$S_n$, if the graph contains some odd circuits, or$A_n$in the other case. It is easy to see that the graph of the Fifteen Puzzle is bipartite, so it contains only even circuits. The exception of the theorem above is the graph with seven vertices, one$6$-circuit and two$5$-circuits. What then is the automorphism group of this Tricky Six Puzzle? A paper of A. Fink and R. Guy (Math. Magazine, 2009) gives an answer to this question and shows the relationship of this special case with other mathematical problems. ♦ ♦ ♦ 12. apríla 2012 o 9:50 v miestnosti M-213 Antonio Breda d'Azevedo (University of Aveiro, Portugal): "Maps, hypermaps and abstract polytopes" Abstrakt: While maps are cellular embeddings of connected graphs on connected compact surfaces, hypermaps are cellular embeddings of hypergraphs. Regular oriented maps/hypermaps can be chiral (if the full automorphism group contains no "reflections") or not. Chiral hypermaps can appear with different chirality indices; while low chiral hypermaps are abundant, extreme hight chiral maps/hypermaps (totaly chiral) seems to be very rare. In this talk we speak, among other things, on several forms of regularity and chirality of maps/hypermaps, how restrict regularity can encodes a hypermap (hypermaps are restricted form of maps) and how regular direct abstract polytopes can be encoded on compact surfaces as restrictedly regular hypermaps. ♦ ♦ ♦ 29. marca 2012 o 9:50 v miestnosti M-213 Martin Knor (STU Bratislava): "Triangulácie orientovateľných plôch kompletnými tripartitnými grafmi a kompletnými grafmi" Abstrakt: V doteraz publikovaných prácach sme ukázali, že existuje až n^{an^2} triangulácií plôch grafom K_n (ako orientovateľných tak aj neorientovateľných), kde a je kladná konštanta. Bohužiaľ, trieda radov n bola veľmi "riedka". V súčasnosti sa nám podarilo zostrojiť takéto triangulácie pre podstatne hustejšie triedy n. V prípade neorientovateľných plôch máme dokonca lineárnu triedu a výsledok je založený na bi-vnoreniach Cayleyho tabuliek dihedrálnych grúp. Tieto bi-vnorenia boli zostrojené ad-hoc. V prípade orientovateľných plôch máme "skoro" lineárnu triedu, ktorú sme zostrojili pomocou bi-vnorení Latinských štvorcov, z ktorých jeden je Cayleyho tabuľkou metacyklickej grupy. Tento prístup je oveľa zaujímavejší a práve o ňom bude príspevok. Využívame tu skutočnosť, ze Cayleyho tabuľka metacyklickej grupy má pre isté rády n "veľmi veľa" latinských podštvorcov. ♦ ♦ ♦ 22. marca 2012 o 9:50 v miestnosti M-213 Robert Lukoťka (Trnavská Univerzita): "Maximal 5-colouring sequence in a planar graph" Abstrakt: A (k+1)-colouring sequence of a graph G is an ordering of its vertices into a sequence v_1, v_2, ... , v_n such that every vertex v_i has at most k neighbours which are in front of it in the sequence. This equivalently means that G is k-degenereted and that G has colouring number k+1. Since every planar graph has a vertex of degree 5 or less, every planar graph has a 6-colouring sequence. We will show that every planar graph has a 4-colouring sequence of size at least 8/9.|V(G)|. We conjecture that every planar graph has a 4-colouring sequence of size at least 11/12.|V(G)|. ♦ ♦ ♦ 15. marca 2012 o 9:50 v miestnosti M-213 Martin Škoviera (KI FMFI UK): "Regular maps with nilpotent automorphism groups" Abstrakt: According to a folklore result, every regular map on an orientable surface with abelian automorphism group belongs to one of three infinite families of maps with one or two vertices. Here we deal with regular maps whose automorphism group is nilpotent. We show that each such map decomposes into a direct product of two maps$H\times K$, where Aut$(H)$is a$2$-group and$K$is a map with a single vertex and an odd number of semiedges. Many important properties of nilpotent maps follow from this decomposition. We show, for example, that apart from two well defined classes of maps on at most two vertices and their duals, every nilpotent regular map has both its valency and face-size divisible by$4$. We give a complete classification of nilpotent regular maps of nilpotency class$2$and$3$, and prove that for every integer$c\ge 1$there are only finitely many simple regular maps whose automorphism group is nilpotent of class$c$. ♦ ♦ ♦ 1. marca 2012 o 9:50 v miestnosti M-213 Martin Knor (STU): "Grafy daného stupňa a priemeru na minimálnom počte vrcholov" Abstrakt: Ako opak problému stupňa a priemeru sa zaoberáme minimálnym počtom vrcholov, ktoré môže mať graf daného stupňa a priemeru. Zatiaľ čo pre pravidelné grafy je problém veľmi jednoduchý, pre vrcholovo-tranzitívne je celkom zaujímavý. Napriek tomu dávame takmer vo všetkých prípadoch optimálne riešenie. ♦ ♦ ♦ 23. februára 2012 o 9:50 v miestnosti M-213 Martin Máčaj (FMFI UK): "Wilsonove operátory na mapách" Abstrakt: An oriented map is a connected graph embedded into an oriented surface surface in such a way that the resulting faces are simply connected (homeomorphic to an open disk). The$j$-th hole operator$H_j$creates a new map${\cal M}^{H_j}$from an oriented map${\cal M}$such that the faces of${\cal M}^{H_j}$are the$j$-th holes of${\cal M}$, that is, cyclic sequences of edges, each two consecutive sharing a vertex, so that at each vertex, the adjacent edges subtend$j$faces on the right. The map${\cal M}^{H_j}$is well defined whenever the valency of the map${\cal M}$is coprime to$j$. These were introduced by Steve Wilson in 1979. The operator$H_{-1}$has always been regarded as to produce the mirror image and when restricted to the class of$n$-valent maps,$H_{j}$has been identified with the operator$H_{ j \pmod n}$. But ... is this really the case? ♦ ♦ ♦ 15. decembra 2011 o 9:50 v miestnosti M-213 Robert Jajcay: "Half-regular Cayley maps" Abstrakt: The connection between the existence of a an orbit of a skew-morphism that is closed under inverses and generates the whole group and the existence of a regular Cayley map is by now a firmly established part of the theory of regular Cayley maps. In our talk, we investigate the role of those orbits of skew-morphisms that do not give rise to regular Cayley maps because they are not closed under inverses. We use the term half-regular map to describe an orientable map with an orientation preserving automorphism group that is transitive on vertices and half-transitive on darts. We present a full classification of half-regular Cayley maps and argue that half-regular Cayley maps come in two types: those that arise from two skew-morphism orbits of equal size that are both closed under inverses and those that arise from two equal-sized orbits that do not contain involutions or inverses but one contains the inverses of the other. In addition, half-regular Cayley maps of the first type are shown to be half-edge-transitive, while half-regular Cayley maps of the second type are shown to be necessarily edge-transitive. A connection between half-regular Cayley maps and regular hypermaps is also investigated. The results come from a joint project with Roman Nedela. ♦ ♦ ♦ 1. decembra 2011 o 9:50 v miestnosti M-213 Arthur Hoffmann Ostenhof (TU Wien): "The Strong Five Cycle Double Cover Conjecture" Abstrakt: A cycle double cover of a cubic graph G is a set S of cycles of G such that every edge of G is contained in exactly two cycles of S. There are several variations of the cycle double cover conjecture (CDCC). We introduce a new one which we call the Strong 5-CDCC. We prove several new results which are related to this conjecture. ♦ ♦ ♦ 24. novembra 2011 o 9:50 v miestnosti M-213 Ján Kováč: "Rozširiteľnosť párení v niektorých triedach grafov" Abstrakt: Graf nazveme "equimatchable", ak v ňom každé dve nerozšíriteľné párenia majú rovnakú mohutnosť. V prednáške sa budeme zaoberať vlastnosťami chordálnych equimatchable grafov a equimatchable karteziánskych súčinov grafov. Ukážeme, že pre každý equimatchable chordálny graf$G$existuje graf$H$taký, že$H\# T$je izomorfný s$G$pre každú kostru$T$grafu$H$, kde$H\# T$je prienikový graf fundamentálnych cyklov grafu$H$vzhľadom na kostru$T$. Predstavíme charakterizáciu dvojsúvislých grafov$H$, pre ktoré platí, že$H \# T$je equimatchable pre každú kostru$T$grafu$H$. Pre súvislé karteziánske súčiny grafov ukážeme, že jediný equimatchable netriviálny karteziánsky súčin je$K_2 \square K_2$. V záverečnej časti sa zameriame na zovšeobecnenie pojmu rozšíriteľnosti párení v karteziánskych grafoch a ukážeme niektoré vlastnosti všeobecnejšej rozšíriteľnosti. ♦ ♦ ♦ 10. novembra 2011 o 9:50 v miestnosti M-213 Barbora Candráková: "Construction of 4-regular graphs with circular chromatic index close to 4" Abstrakt: The circular chromatic index of a graph G is the infimum of all rational numbers p/q, for p and q coprime, such that there exists a circular p/q-edge-coloring of the graph G. It is an interesting problem to determine which possible values of the circular chromatic index are attained for d-regular graphs with chromatic index d + 1 (known as d-regular snarks). In this talk we provide a construction of 4-regular snarks which shows that all the values 4 + 2/r for an integer r > 8 are attained as circular chromatic indices. So far, no such class of graphs has been known. ♦ ♦ ♦ 3. novembra 2011 o 9:50 v miestnosti M-213 Ján Karabáš: "Classification of edge-transitive maps" Abstrakt: A map M is edge-transitive if its group of automorphisms, Aut(M), acts transitively on the edges. Let M be an edge-transitive map. Maps M and their medial maps Med(M) are in a one-to-one correspondence, hence we may classify edge-transitive maps on orientable surfaces by employing well-developed techniques of the classification of orientable vertex-transitive maps. Since the orientation-preserving automorphism group of a medial map is of index at most two in the automorphism group of a medial map, we know, that the quotient of the medial map of orientable edge-transitive map has at most two vertices. Orientation-preserving automorphisms of an edge-transitive map are *face colour-preserving*, i.e. they cannot act as a duality in the medial map. The number of possible quotient maps significantly decreases, in particular there are just six quotient maps to consider. In the case of two-vertex quotient,$\bar{M}$, of a medial map,$M$, the automorphism group of the respective (medial) map must contain an automorphism$\phi$, such that$\phi$projects onto an automorphism of the quotient, transposing the two vertices of$\bar{M}$and preserving the face-colouring of$\bar{M}$. These conditions gives to rise to \emph{seven} infinite families of edge-transitive maps, up to duality. Using the technique of voltage assignments we can reconstruct all edge-transitive maps of given genus or with given number of edges. ♦ ♦ ♦ 27. októbra 2011 o 9:50 v miestnosti M-213 Stefan Dobrev (Bratislava): "Algorithmics of Directional Antennae: Strong Connectivity with Multiple Antennae" Abstrakt: We consider the following problem: Given a set of points S in the Euclidean plane (representing e.g. sensors in a sensor network), number of antennae k per point, a transmission range r and a transmission angle phi, set the transmission direction for each antenna in such a way that the resulting directed graph is strongly connected. We provide various upper and lower bounds on r with respect to k and phi and show that for k=2 and transmission angle at most alpha it is NP-hard to approximate the optimal radius to within a factor of x, where x and alpha are the solutions of equations x = 2 sin(alpha) = 1 + 2 cos(2*alpha). ♦ ♦ ♦ 13. októbra 2011 o 9:50 v miestnosti M-213 Roman Nedela (Banská Bystrica): "6-Rozklad snarkov" Abstrakt: A snark is a cubic graph with no$3$-edge-colouring. In 1996, Nedela and Skoviera proved the following theorem: Let$G$be a snark with an$n$-edge-cut,$n\geq 2$, whose removal leaves two$3$-edge-colourable components$M$and$N$. Then both$M$and$N$can be completed to two snarks$\tilde M$and$\tilde N$of order not exceeding that of$G$by adding at most$\kappa(n)$vertices, where the number$\kappa(n)$only depends on$n$. The known values of the function$\kappa(n)$are$\kappa(2)=0$,$\kappa(3)=1$,$\kappa(4)=2$(Goldberg, 1981), and$\kappa(5)=5$(Cameron, Chetwynd, Watkins, 1987). The value$\kappa(6)$is not known and is apparently difficult to calculate. In 1979, Jaeger conjectured that there are no 7-cyclically-connected snarks. If this conjecture holds true, then$\kappa(6)$is the last important value to determine. Our talk is aimed attacking the problem of determining$\kappa(6)$by investigating the structure and colouring properties of potential complements in 6-decompositions of snarks. We find a set of$14$complements which suffice to perform$6$-decompositions of snarks with at most$30$vertices. We show that if this set is not complete to perform$6$-decompositions of all snarks, then$\kappa(6)\geq 20$and there are strong restrictions on the structure of (possibly) missing complements. Part of the proofs are computer assisted. ♦ ♦ ♦ 6. októbra 2011 o 9:50 v miestnosti M-213 Robert Jajcay: "Biregular cages - a detour or a dead end" Abstrakt: A$(k,g)$-cage is a$k$-regular graph of girth$g$and smallest possible order. Although studied for over 50 years now, the problem of finding cages for any given pair of parameters$(k,g)$has only been solved for a very limited set of parameters, and is generally deemed to be very hard. The idea of relaxing the restrictions and allowing for bi-regular graphs - graphs with exactly two different degrees - for any given girth was therefore introduced with the hope of providing further insights and possible breakthroughs. In our talk, we show that the problem of finding bi-regular cages is indeed solvable, and present a construction that produces bi-regular cages for almost all sets of admissible parameters. We will conclude our talk by examining the question of whether our solution constitutes a dead end or a detour from the original hopes for cracking the classical cage problem; hopefully with some help from the audience. The presented results come from our joint work with Prof. Geoff Exoo, and have a significant computational component. ♦ ♦ ♦ 29. septembra 2011 o 9:50 v miestnosti M-213 Zdeněk Ryjáček: "Uzavěrové techniky pro hamiltonovské vlastnosti grafu" Abstrakt: Grafové uzávěry umožňují často podstatným zpusobem zjednodušit strukturu grafu při zachování některé jeho zvolené vlastnosti (zpravidla hamiltonovského typu), a staly se tak zejména v poslední době duležitým nástrojem hamiltonovské teorie grafu. V prednášce ukážeme hlavní myšlenky konstrukce některých grafových uzávěru pro grafy bez K_{1,3} a techniky, jež umožňují po redukci problému na hranové grafy daný problém transformovat do třidy kubických grafu, s aplikací na konkrétní případ uzávěru pro hamiltonovskou souvislost a jejich použití při odvození asymptoticky ostré podmínky Oreho a Diracova typu pro hamiltonovskou souvislost v grafech bez K_{1,3}. ♦ ♦ ♦ 22. septembra 2011 o 9:50 v miestnosti M-213 František Kardos: "Perfect matchings in cubic graphs" Abstrakt: Lovasz and Plummer conjectured in the 1970's that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite graphs by Voorhoeve in 1979, and for planar graphs by Chudnovsky and Seymour in 2008. Then several general lower bounds for the number of perfect matchings in cubic bridgeless graphs appeared, and finally, the conjecture has been settled recently. In this talk, a survey on methods used to attain these results is provided. ♦ ♦ ♦ 12. mája 2011 o 9:50 v miestnosti M-213 Karina Chudá: "S(2,1)-hrátky so zovšeobecnenými Blanušovými snarkami" Abstrakt: r-S(2,1)-ohodnotenie grafu G je zobrazenie z množiny vrcholov V(G) grafu G do cyklickej grupy Zr rádu r, spĺňajúce dve podmienky. Po prvé, každá dvojica vrcholov spojených cestou dĺžky 1 v G (susedov v G) má hodnoty vo vzdialenosti aspoň 2 v Zr. Po druhé, každá dvojica vrcholov spojených cestou dĺžky 2 v G (so spoločným susedom v G) má hodnoty vo vzdialenosti aspoň 1 v Zr (rôzne v Zr). σ-číslo σ(G) grafu G je najmenšie kladné celé číslo r, pre ktoré existuje r-S(2,1)-ohodnotenie G. Zovšeobecnené Blanušove snarky B1m prvého a B2m druhého typu rádu 8m+10 tvoria nekonečné triedy kubických grafov s chromatickým indexom 4 (snarkov). Nultým členom B10 a B20 je Petersenov graf. Prvým členom B11 je prvý Blanušov snark a B21 je druhý Blanušov snark. Určíme σ-číslo zovšeobecnených Blanušových snarkov. ♦ ♦ ♦ 5. mája 2011 o 9:50 v miestnosti M-213 Michal Kotrbčík: "Locally maximal embeddings" Abstrakt: A locally maximal embedding of a graph G is a cellular embedding of G on an orientable surface such that every vertex of G is incident with at most two faces. These are precisely the embeddings whose genus cannot be raised by moving any edge in the local rotation at one of is end-vertices. The locally maximal genus of a graph G is the minimum genus of a locally maximal embedding of G. Among other results we show how to calculate the locally maximal genus of many interesting classes of graphs, for example completegraphs, complete bipartite graphs and hypercubes. We investigate the relationships between locally maximal genus, minimum genus, and maximum genus. In particular, we provide results towards a classification of all graphs with locally maximal genus equal to minimum genus. Joint work with M. Škoviera. ♦ ♦ ♦ 28. apríla 2011 o 9:50 v miestnosti M-213 Michal Kotrbčík: "Matchings, cycle bases, and the maximum genus of a graph" Abstrakt: We study the interplay between the maximum genus of a graph and bases of its cycle space via the corresponding intersection graph. Our main results show that the matching number of the intersection graph is independent of the basis precisely when the graph is upper-embeddable, and completely describe the range of matching numbers if the graph is not upper-embeddable. Particular attention is paid to cycle bases consisting of fundamental cycles with respect to a given spanning tree. For 4-edge-connected graphs, the intersection graph with respect to any spanning tree (and, in fact, with respect to any basis) has either a perfect matching or a matching missing exactly one vertex. We show that if a graph is not 4-edge-connected, different spanning trees may lead to intersection graphs with different matching numbers. We also show that there exist 2-edge-connected graphs for which the set of values of matching numbers of their intersection graphs contains arbitrarily large gaps. ♦ ♦ ♦ 7. apríla 2011 o 9:50 v miestnosti M-213 Martin Knor: "Fulerény na hyperbolických plochách" Abstrakt: Mathematical models of fullerenes are cubic spherical maps of type$(5;6)$, that is, with pentagonal and hexagonal faces only. Any such map necessarily contains exactly 12 pentagons, and it is known that for any integer$\alpha\ge 0$except$\alpha=1$there exists a fullerene with precisely$\alpha$hexagons. In this talk we consider hyperbolic analogues of fullerenes, modelled by cubic maps of face-type$(6; k)$for some$k\ge 7$on orientable surface of genus at least two. The number of$k$-gons in this case depends on the genus but the number of hexagons is again independent of the surface. We focus on the values of$k$that are universal' in the sense that there exist cubic maps of face-type$(6; k)$for all genera$g\ge 2$. By Euler's formula, if k is universal, then$k\in\{7; 8; 9; 10; 12; 18\}$. We show that for any$k\in\{7; 8; 9; 12; 18\}$and any$g\ge 2$there exists a cubic map of face-type$(6; k)$with any prescribed number of hexagons. For$k = 7$and 8 we also prove the existence of polyhedral cubic maps of face-type$(6; k)$on surfaces of any prescribed genus$g\ge 2$and with any number of hexagons$\alpha$, with possible exceptions when$k = 8$and either$g = 2$and$\alpha= 4$, or else$g = 3$and$\alpha= 1; 2$. Joint work with P. Potocnik, J. Siran, and R. Skrekovski. ♦ ♦ ♦ 31. marca 2011 o 9:50 v miestnosti M-213 Arthur Hoffmann Ostenhof (TU Wien): "Solving Cubic Graphs" Abstrakt: We consider the following problem. Let$S$be a set of$2$-connected cubic graphs. Which properties must$S$have so that every$3$-connected cubic graph$G$has a matching$M$such that every component of$G-M$is either an even circuit or a subdivision of a graph of$S$with an even number of subdivision vertices? We present some answers to this question and disprove a conjecture of H\"aggkvist and Markstr\"om which is related to the Cycle Double Cover Conjecture. ♦ ♦ ♦ 24. marca 2011 o 9:50 v miestnosti M-213 Aleksander Malnic (University of Ljubljana): "Crosscovers" Abstrakt: To each unoriented edge$e$of a connected graph$X$we assign an element$\zeta_e$from a given abelian group$\Gamma$. The graph$X(\Gamma,\zeta)$with$V(X) \times \Gamma$as the vertex set, where$(u,g)$and$(v,h)$are adjacent whenever there is an edge$e = uv$in$X$and$g+h = \zeta_e$, is called a crosscover. Crosscovers, an obvious generalization of Cayley sum graphs, are a special kind of covers. Some basic facts like regularity/irregularity, connectedness, and lifting automorphisms will be discussed. (Joint work with Steve Wilson.) ♦ ♦ ♦ 17. marca 2011 o 9:50 v miestnosti M-213 Roman Nedela: "Transformácie regulárnych máp zachovávajúce vrcholovú tranzitivitu" Abstrakt: Opíšeme transformácie regulárnych máp na orientovateľných plochách, ktoré zachovávajú plochu a akciu grupy automorfizmov pôvodnej mapy. Aplikácia týchto transformácií je ekvivalentná (v niektorých) prípadoch dobre známym geometrickým transformáciám máp - trunkácii, mediálu, duálu mapy atď. Definujeme 10 transformácií regulárnym máp, pričom v piatich prípadoch vedie transformácia regulárnej mapy M priamo na vrcholovo tranzitívnu mapu N. V ďalších piatich prípadoch je akcia grupy automorfizmov na výslednej mape N vrcholovo tranzitívna jedine vtedy, ak mala pôvodná (regulárna) mapa M navyše aj ďalšie, vonkajšie symetrie, ktoré dokážeme charakterizovať. V týchto prípadoch aktuje pôvodná grupa automorfizmov G mapy M na vrcholoch mapy N s dvomi orbitmi a grupa G, rozšírená o vonkajší automorfizmus mapy M, má akciu s jedným orbitom na vrcholoch mapy N. Je veľmi dobre známym faktom, že grupa orientáciu zachovávajúcich automorfizmov regulárnej mapy M je kvocientom grupy C * C_2. Ukážeme, že pokiaľ je vrcholovo tranzitívna mapa jednoduchá a pripúšťa akciu kvocientu C * C_2, potom je buď regulárna alebo ju možno transformovať z regulárnej mapy použitím jednej z 10 transformácií. Klasické znalosti a klasifikácie Platónskych a Archimedovských telies je možné rozšíriť použitím transformácií na plochy tých rodov, pre ktoré poznáme zoznam regulárnych máp. ♦ ♦ ♦ 10. marca 2011 o 9:50 v miestnosti M-213 Martin Knor: "Od Heawoodovej hypotézy k$n^{an^2}$trianguláciám kompletných grafov" Abstrakt: V roku 1890 Heawood sformuloval hypotézu, ktorá stanovovala minimálny počet farieb, pomocou ktorých vieme korektne zafarbiť každý graf vnoriteľný do (orientovateľnej) uzavretej a kompaktnej plochy. Táto hypotéza bola dokázaná v roku 1968 Ringelom a Youngsom, ktorí našli pre každé prípustné n jednu trianguláciu grafom Kn. Neskôr sa ukázalo, že takýchto triangulácií je podstatne viac. V prednáške referujeme o metódach, pomocou ktorých sme dokázali, že takýchto triangulácií je$n^{an^2}$a to pre lineárne triedy n (v prípade neorientovateľných vnorení) a pre "skoro-lineárne" triedy (v prípade orientovateľných vnorení). Sústredíme sa práve na orientovateľné vnorenia. ♦ ♦ ♦ 3. marca 2011 o 9:50 v miestnosti M-213 Martin Máčaj: "Ešte o Hoffmanovom-Singletonovom grafe" Abstrakt: Ukážeme viacero možností ako skonštruovat Hoffmanov-Singletonov graf. Ako aplikáciu dokážeme, že jeho grupa automorfizmov obsahuje podgrupu izomorfnú s grupou A_7. ♦ ♦ ♦ 24. februára 2011 o 9:50 v miestnosti M-213 Veronika Bachratá: "The Hoffman-Singleton Graph and its Automorphisms" Abstrakt: The Hoffman-Singleton graph is the biggest known Moore graph. Following the article "The Hoffman-Singleton Graph and its Automorphisms" by Paul R. Hafner we look at the structure of this graph. As the abstract of the article says "We describe the Hoffman-Singleton graph geometrically, showing that it is closely related to the incidence graph of the affine plane over Z_5. This allows us to construct all automorphisms of the graph." ♦ ♦ ♦ 16. decembra 2010 o 9:50 v miestnosti M-213 Edita Máčajová a Edita Rollová: "Nowhere-zero Flows on Bidirected Complete and Complete Bipartite Graphs" Abstrakt: The concept of a nowhere-zero flow on a bidirected graph is a natural generalisation of a nowhere-zero flow on a directed graph. A bidirected graph is a graph where edges are divided into half-edges and each half-edge has an independent orientation. The flow number of a bidirected graph$G$is the smallest integer$k$such that$G$admits a flow with values in the set$\{\pm 1,\pm 2,\ldots,\pm(k-1)\}$. Unlike the directed case, where a graph has a nowhere-zero flow if and only if it is bridgeless, in the bidirected case no such simple condition is available. In this talk we determine the flow number of bidirected complete and complete bipartite graphs. We show that, if one of such graphs admits a nowhere-zero flow, then it admits a nowhere-zero 4-flow and we characterize which of these graphs have the flow number 2 or 3. ♦ ♦ ♦ 2. decembra 2010 o 9:50 v miestnosti M-213 Jana Šiagiová: "Cayley graphs of diameter two close to the Moore bound" Abstrakt: The order of a graph of maximum degree$d$and diameter$2$cannot exceed$d^2+1$, the Moore bound for diameter two. A combination of known results\ guarantees the existence of regular graphs of degree$d$, diameter$2$, and order at least$d^2-2d^{1.525}$for all sufficiently large$d$, asymptotically approaching the Moore bound. The corresponding graphs, however, tend to have a fairly small or trivial automorphism group and the nature of their construction does not appear to allow for modifications that would result in a higher level of symmetry. The best currently available construction of vertex-transitive graphs of diameter$2$and preassigned degree gives order$\frac{8}{9}(d+\frac{1}{2})^2$for all degrees of the form$d=(3q-1)/2$for prime powers$q\equiv 1$mod$4$. We show that for an infinite set of degrees$d$there exist Cayley, and hence vertex-transitive, graphs of degree$d$, diameter$2$, and order$d^2-O(d^{3/2})$. ♦ ♦ ♦ 18. novembra 2010 o 9:50 v miestnosti M-213 Martin Máčaj: "Injektívne podgrafy Hammingových grafov" Abstrakt: The Hamming graph H(d,q) has vertex set the set of ordered d-tuples of elements of {1,2,...,q}, two vertices being adjacent if they differ in precisely one coordinate. We will study the subgraph I(d,q) of the Hamming graph H(d,q) induced by the set of d-tuples with pairwise disjoint coordinates. In particular we completely determine which graphs I(d,q) are Cayley. ♦ ♦ ♦ 4. novembra 2010 o 9:50 v miestnosti M-213 Karina Chudá: "O horných ohraničeniach λ-čísla súčinov grafov s kompletným grafom K2" Abstrakt: r-L(2,1)-ohodnotenie grafu je zobrazenie z vrcholovej množiny grafu do množiny nezáporných celých čísel {0,1, ...,r} také, že dvojicu susedných vrcholov zobrazí na celé čísla s rozdielom aspoň 2 a dvojicu vrcholov so spoločným susedom zobrazí na rôzne celé čísla. λ-číslo grafu je najmenšie r také, že graf má r-L(2,1)-ohodnotenie. Vrcholová množina skúmaných súčinov grafov je karteziánskym súčinom vrcholových množín činiteľov, hranová množina závisí od typu súčinu. Priamy súčin G1 x G2 grafov G1 a G2 má hranu, ak sú hrany v činiteľoch v oboch súradniciach. Karteziánsky súčin G1 G2 grafov G1 a G2 má hranu, ak je hrana v činiteli v jednej zo súradníc a zároveň rovnosť v druhej zo súradníc. Silný súčin grafov G1 a G2 má hranu, ak je hrana v priamom súčine alebo ak je hrana v karteziánskom súčine. Hornými ohraničeniami λ-čísla súčinov grafov s maximálnym stupňom oboch činiteľov aspoň 1 sa zaoberali napríklad Shao a Yeh (2005) pre kareziánsky súčin a Klavžar a Špacapan (2005) a Shao et al. (2007) pre priamy a silný súčin. Autorom sa podarilo dosiahnuť lepšie ohraničenia, ak navyše predpokladali, že maximálny stupeň oboch činiteľov je aspoň 2. Ak mal aspoň jeden z činiteľov maximálny stupeň 1, zostali v platnosti horšie ohraničenia. λ-číslo súčinu s jedným z činiteľov s maximálnym stupňom 1 je rovné λ-číslu súčinu druhého z činiteľov a kompletného grafu K2. To nás motivovalo skúmať ohraničenia λ-čísla súčinov s činiteľom K2. V tejto prednáške uvedieme operácie na grafe G použité na stanovenie horného ohraničenia λ-čísla priameho, karteziánskeho a silného súčinu G a kompletného grafu K2, samotné ohraničenia a ich porovnanie s pôvodnými ohraničeniami. ♦ ♦ ♦ 21. októbra 2010 o 9:50 v miestnosti M-213 Robert Lukoťka: "Real flow number of generalized Blanuša snarks" Abstrakt: A real flow on a graph is a flow with values in$\mathbb{R}$. A real nowhere-zero$r$-flow is a real flow~$\phi$with each edge satisfying the condition$1\leq|\phi (e)|\leq r-1$. The real flow number$\Phi_{\mathbb{R}}(G)$of a graph$G$is the infimum of all reals$r$such that$G$has a real nowhere-zero$r$-flow. In this talk we present methods that can be used to determine real flow numbers of graphs, with focus on cubic graphs. Using these methods we prove that the real flow number of all generalized Blanuša snarks except for the Petersen graph is 4.5. ♦ ♦ ♦ 7. októbra 2010 o 9:50 v miestnosti M-213 Štefan Gyűrki: "On the domination in digraphs and in their reverses" Abstrakt: For a digraph D, the domination number of D is denoted by γ(D), the total domination number of D is denoted by γt(D), and the digraph obtained by reversing all the arcs of D is denoted by D-. We show that the difference$γ(D-)-γ(D) can be arbitrarily large in the class of 2-regular strongly connected digraphs, and similarly, γt(D-)-γt(D) can be arbitrarily large in the class of 3-regular strongly connected digraphs. The similar results for larger valencies were proved by Knor and Niepel. We also show that every 2-regular digraph D satisfies γt(D)=γt(D-).
This completes the solutions of Problems~1 and 2 posed by Knor and Niepel.

♦ ♦ ♦

30. septembra 2010 o 9:50 v miestnosti M-213
Michal Kotrbčík: "Maximum genus - old problem and new results"

Abstrakt:

In this talk we discuss the problem of determining the maximum integer k such that a given graph has an embedding into the orientable surface of genus k. This integer is known as the maximum genus of a graph and can be characterised combinatorially, without referring to surfaces. Using such characterisations, we derive three types of results. First, we present a new simple 2-approximation algorithm for the maximum genus. Second, we show that the maximum genus can provide both lower and upper bound on the maximum number of pairwise vertex-disjoint cycles of a graph. Finally, we show how one can easily obtain lower and upper bounds on the maximum genus of graphs from particular classes, for example, graphs with fixed girth and minimum degree.

♦ ♦ ♦

23. septembra 2010 o 9:50 v miestnosti M-213
Martin Škoviera: "Nowhere-zero flows on signed eulerian graphs"

Abstrakt:

A signed graph is a graph in which every edge is labelled with a sign, + or -. In the talk we introduce flows on signed graphs as a natural analogue of flows on unsigned (that is, all-positive) graphs, based on the use of bidirected rather than directed edges. After giving a brief survey of known results about nowhere-zero flows on signed graphs we concentrate on flows on signed eulerian graphs. We show that every signed eulerian graph that has a nowhere-zero flow has a nowhere-zero 4-flow. This indicates a significant difference from the unsigned case where every eulerian graph is known to have a nowhere-zero 2-flow. We also characterise those signed eulerian graphs whose flow number equals 2, 3, and 4, respectively.
This is a joint work with Edita Macajova.

♦ ♦ ♦

13. mája 2010 o 9:50 v miestnosti M-213
Štefan Gyűrki: "A construction of goal-minimally k-diametric graphs"

Abstrakt:

An undirected graph G with a diameter k is said to be goal-minimally k-diametric (k-GMD for short) if for every edge uv of G the distance dG-uv(x,y) is greater than k if and only if {x,y}={u,v}. We show how to obtain infinitely many 6-GMD and 8-GMD graphs from a construction which is a generalization of Plesník's construction of 6-GMD graphs. This construction is similar to the O'Keefe-Wong construction of cages.
This is a joint work with Beáta Štupáková.

♦ ♦ ♦

6. mája 2010 o 9:50 v miestnosti M-213
Martin Máčaj: "Ako hľadať 'pekné' silne regulárne grafy?"

Abstrakt:

Silne regulárny graf s parametrami v, k, λ a μ, skrátene SRG(v,k,λ,μ) je k-regulárny graf na v vrcholoch taký, že ľubovoľné dva susedné vrcholy majú práve λ spoločných susedov a ľubovoľné dva nesusedné vrcholy majú práve μ spoločných susedov.
V prednáške predstavíme niekoľko problémov, s ktorými sa môžeme stretnúť pri hľadaní silne regulárnych grafov s "rozumne veľkou" grupou automorfizmov.

♦ ♦ ♦

29. apríla 2010 o 9:50 v miestnosti M-213
Karina Chudá: "S(2,1)-farbenie grafov s cirkulárnou štruktúrou"

Abstrakt:

r-S(2,1)-farbenie grafu je vrcholové farbenie prvkami cyklickej grupy Z_r také, že susedné vrcholy sú zafarbené farbami vo vzdialenosti aspoň 2 v Z_r a vrcholy vo vzdialenosti 2 sú zafarbené rôznymi farbami. Vzdialenosti farieb v Z_r meriame prirodzenou cirkulárnou metrikou. Najmenšie r, pre ktoré má graf r-S(2,1)-farbenie, sa nazýva sigma-číslo grafu. V prednáške sa budeme zaoberať S(2,1)-farbením grafov, ktoré vznikajú z určitého počtu izomorfných segmentov cyklicky zoradených tak, aby otočenie o jeden segment bolo automorfizmom výsledného grafu. Základom nášho prístupu k S(2,1)-farbeniu týchto grafov je nájdenie všetkých r-S(2,1)-farbení vhodného podgrafu a ich následné pospájanie do r-S(2,1)-farbenia celého grafu. Hlavným problémom pri tomto postupe sa ukazuje byť veľkosť množiny všetkých r-S(2,1)-farbení podgrafu, čo riešime ich rozdelením do orbít vzhľadom na nejakú grupu automorfizmov, analýzou matice susednosti prechodového grafu farbení alebo použitím vhodného napäťového grafu.

♦ ♦ ♦

15. apríla 2010 o 9:50 v miestnosti M-213
Ján Mazák: "Cyclic orderings of matroids II"

Abstrakt:

We present a general result about weighted matroids which has many interesting corollaries. The first corollary is a special case of a conjecture on cyclic orderings of matroids, the second one proves a conjecture of Goncalves and the third one is a generalization of a result of Nash-Williams on disjoint spanning trees in graphs for matroids. Another corollary is the equality of circular and fractional arboricity of matroids.

The talk is divided into two parts. In the first part we introduce matroids and the basic concepts of matroid theory: independence, basis, rank, and duality of matroids. Then we present certain conjectures on cyclic orderings and arboricity of matroids. The second part is devoted to the proof of the main theorem (the proof is very nice in my opinion).

The talk is based on a recent paper of J. van den Heuvel and S. Thomasse (http://arxiv.org/pdf/0912.2929).

♦ ♦ ♦

8. apríla 2010 o 9:50 v miestnosti M-213
Ján Mazák: "Cyclic orderings of matroids"

Abstrakt:

We present a general result about weighted matroids which has many interesting corollaries. The first corollary is a special case of a conjecture on cyclic orderings of matroids, the second one proves a conjecture of Goncalves and the third one is a generalization of a result of Nash-Williams on disjoint spanning trees in graphs for matroids. Another corollary is the equality of circular and fractional arboricity of matroids.

The talk is divided into two parts. In the first part we introduce matroids and the basic concepts of matroid theory: independence, basis, rank, and duality of matroids. Then we present certain conjectures on cyclic orderings and arboricity of matroids. The second part is devoted to the proof of the main theorem (the proof is very nice in my opinion).

The talk is based on a recent paper of J. van den Heuvel and S. Thomasse (http://arxiv.org/pdf/0912.2929).

♦ ♦ ♦

18. marca 2010 o 9:50 v miestnosti M-213
Martin Knor: "Dominancia v digrafe a v jeho reverze"

Abstrakt:
Nech je D digraf. Označme γ(D) jeho dominančné číslo a označme symbolom D- digraf, ktorý vznikne z D prevrátením orientácie všetkych šípov. V prednáške ukážeme, že pre každé d ≥ 3 a k ≥ 1 existuje jednoduchý silne suvislý d-regulárny digraf Dd,k taký, že γ(Dd,k)-γ(D-d,k)=k. Ináč povedané, rozdiel dominančného čísla digrafu a jeho reverzu môže byť ľubovoľne veľký dokonca aj v triede silne súvislých regulárnych digrafov. Podobný výsledok sme dosiahli pre totálne dominančné číslo, avšak tu potrebujeme aby stupeň spĺňal d ≥ 4. Digraf Dd,k sa zostrojil pomocou zdvihu malého orientovaného grafu (so slučkami a násobnými šípmi) najprv v grupe Z3 a potom v Z2k.

♦ ♦ ♦

11. marca 2010 o 9:50 v miestnosti M-213
Veronika Bachratá a Ján Mazák: "The Weak and Strong Perfect Graph Conjecture II"

Abstrakt:

A graph G is perfect if the chromatic number of any induced subgraph H of G is equal to the size of a largest clique in H. A graph G is a Berge graph if it does not contain an odd cycle or a complement of an odd cycle as an induced subgraph. The famous Strong perfect graph conjecture (SPGC) states that a graph is perfect if and only if it is a Berge graph. The Weak perfect graph conjecture (WPGC) states that the complement of a perfect graph is also perfect. We continue our talk from 4. 3. 20101 by sketching the proof of the SPGT.

Our talk is based on the papers
F. Roussel, I. Rusu, H. Thullier: "The Strong Perfect Graph Conjecture: 40 years of attempts, and its resolution" doi: 10.1016/j.disc.2009.05.024
and
P. Seymour: "How the proof of the strong perfect graph conjecture was found" http://www.math.princeton.edu/~pds/papers/howtheperfect/howtheperfect.ps.

♦ ♦ ♦

4. marca 2010 o 9:50 v miestnosti M-213
Veronika Bachratá a Ján Mazák: "The Weak and Strong Perfect Graph Conjecture"

Abstrakt:

A graph G is perfect if the chromatic number of any induced subgraph H of G is equal to the size of a largest clique in H. A graph G is a Berge graph if it does not contain an odd cycle or a complement of an odd cycle as an induced subgraph. The famous Strong perfect graph conjecture (SPGC) states that a graph is perfect if and only if it is a Berge graph. The Weak perfect graph conjecture (WPGC) states that the complement of a perfect graph is also perfect.

Our talk is devoted to the methods that lead to the proofs of WPGC and SPGC. In the first part (4. 3. 2010) we introduce perfect graphs and describe the so-called primitive classes of perfect graphs. The perfectness of a graph can be stated in terms of linear programming; using this approach we sketch one of the first proofs of the WPGC following Fulkerson and Lovasz. We will continue 11. 3. 2010 by sketching the proof of the SPGT.

Our talk is based on the papers
F. Roussel, I. Rusu, H. Thullier: "The Strong Perfect Graph Conjecture: 40 years of attempts, and its resolution" doi: 10.1016/j.disc.2009.05.024
and
P. Seymour: "How the proof of the strong perfect graph conjecture was found" http://www.math.princeton.edu/~pds/papers/howtheperfect/howtheperfect.ps.

Abstrakty starších prednášok budú doplňované priebežne.