Computer Aided Constructions in Graph Theory 2022 (CGT2022)

The aim of the workshop is to bring together young researchers in Graph Theory whose work includes a significant computational component. Participants are generally expected to prepare a short article about the specifics of the use of computers in their respective research fields and to present a 20 minute talk based on this article. On site collaboration and exchange of ideas, techniques, tricks or hints is particularly encouraged. Doctoral students presenting preliminary reports on their work, wishing to learn more about the use of computers in other areas of Graph Theory, or simply looking for inspiration, are specifically encouraged to apply.

All topics involving the use of computers in Graph Theory (or even broadly, in Combinatorics) will be considered. Each submitted contribution will be reviewed by two members of the Programme Committee and evaluated with regard to the relevance of the topic, the originality of the use of the computing techniques, and the contribution’s potential in becoming a topic of shared interest among the participants of the workshop.

The workshop is part of the ITAT conference, which takes place in hotel Tatrawest, Zuberec, Západné Tatry, Slovakia, from September 23rd to September 27th, 2022.

The expected length of submissions should be about 4-10 pages of two-columns A4 format (including references), written in English, using LaTeX (LaTeX class), and submissions must be submitted using the EasyChair system. The accepted papers will be published in ITAT proceedings available through the CEUR Workshop Proceedings publication service (CEUR-WS.org), indexed in DBLP and Scopus.

The registration fee for the ITAT conference covers not only participation, but also 4 nights lodging and 4 days full catering at the conference hotel: 340 € regular, 290 € for students.

Invited talk

• Jan Goedgebeur (KU Leuven, Belgium): An introduction to computational graph theory and generation algorithms Read more...

Program committee

• Marien Abreu, Universita degli Studi della Basilicata, Italy
• Grahame Erskine, Open University, UK
• Geoffrey Exoo, Indiana State University, USA
• Slobodan Filipovski, University of Primorska, Slovenia
• Štefan Gyurki, Slovak Technikal University, Slovakia
• Tatiana Jajcayová Comenius University, Slovakia co-chair
• Robert Jajcay, Comenius University, Slovakia co-chair
• Jan Karabáš, Matej Bell University, Slovakia
• Petr Kovář, Technical University of Ostrava, Czech Republic
• Tereza Kovářová, Technical University of Ostrava, Czech Republic
• Rastislav Kráľovič, Comenius University, Slovakia
• Robert Lukoťka, Comenius University, Slovakia
• Martin Mačaj, Comenius University, Slovakia co-chair
• Ján Mazák, Comenius University, Slovakia
• Primož Šparl, University of Ljubljana, Slovenia
• James Tuite, Open University, UK

Session with presentations without papers (Saturday 24, 14:00 - 17:00)

14:00-14:30 Ján Karabáš: On Improvements to the Recursive Edge-Coloring Algorithm
Abstract
(join work Jakub Strmeň KI FPV UMB, Ján Karabáš MÚ SAV BB)
The recursive edge colouring algorithm is well-known to be exponential, even for cubic graphs - the simplest case of non-trivial (undirected) graphs. Although one can get impression that program implementing a recusive colouring may not be useful in most instances of the problem, the opposite is often true. We will show that such a program, implementing several small improvements, can be handy in research of chromatic and structural properties of reasonably big snarks. We will also discuss the implementantion of this algorithm (with improvements) using modern programming languages, and we will compare the standard implementations in C++ and in Rust. We will shortly sketch other algorithms and briefly discuss pros and cons of their use in particular tasks.

14:30-15:00 Fatemeh Koorepazan Moftakhar: Constructions of Small Regular Graphs of Given Degree and Girth Using Voltage Lift Graphs and Computer Searches
Abstract
A k-regular graph of girth g and minimal order is called a (k, g)-cage. The orders of cages are determined for only a few sets of parameter pairs (k, g), and the general problem of determining these orders and constructing at least one (k, g)-cage for each pair of parameters is called the Cage Problem. The voltage lift construction is among the most widely used constructions of small (k, g)-graphs, with the orders of the constructed graphs depending on the choice of a base graph, a voltage group, and a specific voltage assignment. In this paper, an algorithm for finding all non-reversing closed walks of a given length is presented. An algorithm for finding a lower bound for the girth of a voltage lift is also proposed and a discussion of the best ways of choosing the voltage assignment is included.

15:00-15:30 Tatiana Jajcayova: Generalizing the Concept of Cayley Graphs to k-Uniform Hypergraphs
Abstract
Cayley graphs constitute one of the most important subclasses of the class of vertex-transitive graphs, and serve as a rich source of examples in various areas of graph theory. It is therefore natural to try to generalize the concept of Cayley graphs to more general combinatorial structures. In our talk, we shall focus on the generalization of Cayley graphs to highly symmetric k-uniform graphs, i.e., incidence structure with all blocks of the same size k. An additional motivation for our research comes from a recent breakthrough in the Cage Problem, where Grahame and Erskine used 3-uniform hypergraphs to construct new record cages. This result suggests that detailed investigation of k-uniform hypergraphs may even lead to advancements in extremal graph theory and related areas.

15:30-16:00 coffee break

16:00-16:30 Marien Abreu: Constructing Goedgebeur's Pseudo 2-factor isomorphic cubic bipartite graph and dissecting its automorphism group
Abstract
A graph G admiting a 2-factor is pseudo 2-factor isomorphic if the parity of the number of cycles in all its 2-factors is the same. In [1] some of the authors of this note gave a partial characterisation of pseudo 2-factor isomorphic bipartite cubic graphs and conjectured that K_{3,3}, the Heawood graph and the Pappus graph are the only essentially 4-edge-connected ones. In [2] Jan Goedgebeur computationally found a graph $\mathscr{G}$ on 30 vertices which is pseudo 2-factor isomorphic cubic and bipartite, essentially 4-edge-connected and cyclically 6-edge-connected, thus refuting the above conjecture. A description will be presented in this talk of how such a graph can be constructed from the Heawood graph and the generalised Petersen graph GP(8,3), which are the Levi graphs of the Fano 7_3 configuration and the Möbius-Kantor 8_3 configuration, respectively. Such a description of $\mathscr{G}$ allows to understand its automorphism group, which has order 144, using both a geometrical and a graph theoretical approach simultaneously. Moreover, some aspects under which this graph is unique will be illustrated.

References:
[1] M. Abreu, A.A. Diwan, B. Jackson, D. Labbate and J. Sheehan. Pseudo 2-factor isomorphic regular bipartite graphs. Journal of Combinatorial Theory, Series B, 98(2) (2008), 432--444.
[2] J. Goedgebeur. A counterexample to the pseudo 2-factor isomorphic graph conjecture. Discr. Applied Math., 193 (2015), 57--60.

16:30-17:00 Robert Jajcay: Prospective Research Directions in Cage Problem
Abstract
In our presentation we shall review the basics of the Cage Problem, the problem of finding a smallest k-regular graph of girth g, and based on the Dynamic Cage Survey published in the Electronic Journal of Combinatorics we will outline the most promising (in our view) directions of research in this area; focusing specifically on methods that take advantage of extensive use of computers.