The workshop will take place on June 2nd, 2021. All times are in CEST. An overview of the programme can be found here.
8:45 : Morning coffee and solving IT issues
Connect and enjoy a coffee together with us. In case you have any troubles connection, please try to contact the organisers by mail.
9:15 : Invited talk
Fractional vertex-arboricity of planar graphs
by František Kardoš (LaBRI, University of Bordeaux, France & Comenius University, Bratislava)
Abstract: …We initiate a systematic study of the fractional vertex-arboricity of planar graphs and demonstrate connections to open problems concerning both fractional coloring and the size of the largest induced forest in planar graphs. In particular, the following three long-standing conjectures concern the size of a largest induced forest in a planar graph, and we conjecture that each of these can be generalized to the setting of fractional vertex-arboricity. In 1979, Albertson and Berman conjectured that every planar graph has an induced forest on at least half of its vertices, in 1987, Akiyama and Watanabe conjectured that every bipartite planar graph has an induced forest on at least five-eighths of its vertices, and in 2010, Kowalik, Lužar, and Škrekovski conjectured that every planar graph of girth at least five has an induced forest on at least seven-tenths of its vertices. We make progress toward the fractional generalization of the latter of these, by proving that every planar graph of girth at least five has fractional vertex-arboricity at most \(2-1/324\).
This is a joint work with Marthe Bonamy, Tom Kelly and Luke Postle.
then : Coffee break
Grab a coffee and discuss with your collegues …
10:30 : Talks about ongoing research
Unique maximum and minimum coloring and unique double maximum coloring of plane graphs
by Simona Rindošová📧 (Pavol Jozef Šafarik University in Košice)
Abstract: …Unique maximum and minimum (unique double maximum) coloring of a plane graph \(G\) is a proper UM coloring of \(G\) in which for each face there is by the lowest (second highest) color of that face colored exactly one element (vertices/edges).
Two adjacent edges of a plane graph are facially adjacent if they are consecutive in a cyclic order around their common end vertex. A coloring is proper if adjacent vertices (facially adjacent edges) are colored differently.
In this talk, we present upper bounds on the chromatic numbers for these four types of UM coloring. For unique maximum and minimum coloring we proved that each plane graph is 7-vertex-colorable and 7-edge-colorable and similarly for unique double maximum coloring that each plane graph is 9-vertex-colorable and 7-edge-colorable.
Path decompositions of random directed graphs
by Alberto Espuny Díaz📧🔗 (Technische Universität Ilmenau)
Abstract: …After the recent resolution of a conjecture of Alspach, Mason and Pullman about path decompositions of tournaments, we have started to consider extensions of this conjecture to general directed graphs. In recent work, we have proved that most directed graphs also satisfy the conjecture, by means of studying random digraphs. In this talk, I will present the problem, our new result, and some of the techniques which we have used.
This is joint work with Viresh Patel and Fabian Stroh.
Types of edges in embedded graphs with minimum degree 2
by Katarína Čekanová (Pavol Jozef Šafarik University in Košice)
Abstract: …The weight of an edge is the degree-sum of its end-vertices. An edge \(e = uv\) is of type \((i, j)\) if \(deg(u) \leq i\) and \(deg(v) \leq j\). Kotzig proved that every 3-connected plane graph contains an edge of weight at most 13. Ivančo described bounds for weights of edges in the class of graphs embeddable on the orientable surfaces with higher genus. Jendroľ and Tuhársky investigated the weight of edges in the class of graphs embeddable on the nonorientable surfaces with higher genus. Later Jendroľ, Tuhársky and Voss described exact types of edges in large embedded maps with minimum degree 3.
In this talk we describe types of edges in connected embedded graphs with minimum degree at least 2, minimum face size at least 3 and sufficiently large number of vertices. We will also discuss the quality of our results.
Counting hamiltonian cycles in regular graphs
by Carol T. Zamfirescu (Ghent University)
Abstract: …We discuss two recent conjectures of Haythorpe on the minimum number of hamiltonian cycles that occur in hamiltonian regular graphs. Special attention will be given to the planar case. We also present some related open problems and conjectures.
then : Lunch break
We are honest: you are responsible for your lunch. We cannot provide any advices.
13:30 : Joint dessert and after-lunch-coffee
We are happy to see you reconnecting after your lunch. Let’s have a chat …
14:00 : Talks about ongoing research
Interval vertex coloring of trees
by Zuzana Šárošiová (Pavol Jozef Šafarik University in Košice)
Abstract: …A vertex \(k\)-coloring is an open (closed) interval \(k\)-coloring if for every vertex \(v\) the set of colors used on the open (closed) neighborhood of \(v\) forms an interval of integers. The largest \(k\) for which there exists an open (closed) interval \(k\)-coloring of \(G\) is called open (closed) interval chromatic number of \(G\). There was a lot of attention given to the edge version of such a coloring (the existence of interval edge coloring of given graph and the value of the corresponding chromatic index), but the vertex interval coloring was (as far as we know) not investigated. In the talk we present some results and algorithms for finding the precise value of open and closed chromatic numbers for trees.
Abstract: …The uniform Turán density of a hypergraph \(H\) is the infimum of all \(d\) such that every sufficiently large hypergraph \(H_0\) such that every linear size induced subhypergraph of \(H_0\) has density at least \(d\) contains \(H\) as a subhypergraph. In addition to the classification of 3-uniform hypergraph with uniform Turán density equal to zero by Reiher, Rödl and Schacht [J. London Math. Soc. 97 (2018), 77–97], the only additional 3-uniform hypergraphs whose uniform Turán density is known are \(K_4^-\) and a specific family of hypergraphs with uniform Turán density equal to \(1/27\). We determined the uniform Turán density of the tight 3-uniform cycle \(C_\ell^{(3)}, \ell\geq 5\).
On \(M_f\)-edge colorings of graphs
by Alfréd Onderko (Pavol Jozef Šafarik University in Košice)
Abstract: …For a graph \(G\) and a function \(f\) which assigns positive integers to vertices of \(G\), an \(M_f\)-edge coloring is an edge coloring of \(G\) in which the number of colors used on edges incident to each vertex \(v\) is at most \(f(v)\). The maximum number of colors of an \(M_f\)-edge coloring of \(G\) is denoted by \(K_f(G)\). We present some bounds on latex]K_f(G)[/latex] and exact values of latex]K_f(G)[/latex] for special classes of graphs.
then : Coffee break
It will be definitely time for another coffee …
15:30 : Talks about ongoing research
Structure of 2-planar graphs
by Mária Maceková (Pavol Jozef Šafarik University in Košice)
Abstract: …A \(k\)-planar graph is a graph that can be drawn in the plane such that each edge is crossed at most \(k\) times. In the talk we consider 2-planar graphs and we will discuss some structural properties of 2-planar graphs compared to 1-planar and planar graphs (mainly the maximal number of edges and hamiltonicity of some subclasses of 2-planar graphs).
Special talk: On spanning trees of subdivisions of polyhedral graphs
by Jochen Harant (Technische Universität Ilmenau)
Abstract: …In 1966, D. W. Barnette proved that a polyhedral graph (3-connected and planar) has a spanning tree of maximum degree at most 3. We consider the problem to determine the smallest integer \(k\) such that a subdivision of a polyhedral graph has a spanning tree of maximum degree at most \(k\) and show \(6~\le ~k~\le ~ 8\).
This is joint work with C. Brause, TU BA Freiberg, and S. Mohr, MU Brno.
16:15 : A special event about the history of IlKe
It is time to reflect the long history of Košice-Ilmenau relations, collaborations, and workshops.
16:30 : Evening programme
We like to invite everybody to stay a little bit longer connected. There is plenty of time for private talks about anything and everything. Moreover, we might suggest some online board games and controversial topics. We hope you haven’t forgotten to cool your beer/drink.
