Neprihlásený používateľ
Cesta: Menu > Semináre > Bratislavský seminár z teórie grafov
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 (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.


Kontakt Hlavná stránka © 2012