Head of the laboratory: Dr. Zsolt Tuza, professor
Members of the laboratory:
Dr. Csilla Bujtás, associate professor (CV)
Dr. György Dósa, professor (CV)
Dr. Zsolt Tuza, professor (CV)
Activities of the research laboratory
The research laboratory makes theoretical research in various directions. In addition to the structural and extremal analysis of discrete mathematical models, especially graphs (networks) and hypergraphs, the algorithmic (time) complexity of combinatorial problems, the approximability of discrete optimization problems (such as various bin packing problems), and the competitiveness of off-line and on-line scheduling algorithms are studied.
Research results
In addition to research on classical variants of graph coloring and list coloring, they also study versions where the number of colors is limited from above by some local condition. In addition to results regarding structural properties, complexity, and the number of usable colors, a close relationship with vertex- and edge-cuts of graphs has been demonstrated (co-authors: E. Sampathkumar and his research group).
They introduced a general model of hypergraph colorings and partitions of set systems; the details of the related theory are published in a series of articles. Meanwhile, for a special subclass (C-coloring), they solved several problems that were open for a long time. The oldest of these issues is the minimum size of a system of k-element transversals that covers all k-class partitions of an n-element set, for which an asymptotically tight solution has been found and a previous conjecture related to it has been refuted.
They studied the partitioning of graphs in several approaches. An edge-connectivity condition has been investigated for K_{1,3}-decompositions and its close relationship with control issues and network flows has been explored (co-author: C. Thomassen). Furthermore, complexity results for the existence of vertex partitions under degree conditions have been obtained (co-authors: C. Bazgan and D. Vanderpooten).
As a generalization of Thue’s notable non-repetitive sequences, they began to study the non-repetitive coloring of graphs. It has been shown that graphs with bounded tree-width can be colored with a finite number of colors in this sense (co-author: P. Varjú).
As a solution to a problem open for two decades, the structure of those graphs (networks) has been characterized in which each connected induced subgraph has a dominating subgraph with a prescribed property exists (i.e. a part from which all other elements of the subgraph can be directly accessed). Assuming a given minimum degree, upper bounds on the domination number of graphs as a function of the number of vertices have been proved. These are the currently known best upper bounds for a minimum degree between 5 and 50, and the proof also provides an algorithmic procedure for constructing dominating sets of size not exceeding the bounds (co-authors: S. Klavžar, M. Henning). Similar results were obtained for 2-domination (co-author: Sz. Jaskó).
On-line scheduling algorithms have been constructed with better competitive ratio than previously known, and it has been demonstrated that suitably defined semi-on-line algorithms (that use some kind of partial information) are guaranteed to be more efficient for many problems; comparing to the case when an algorithm works in the pure online scenario. To close problems open for four decades, the exact absolute approximation ratio of the “First Fit Decreasing” and “First Fit” algorithms were determined. New scheduling and bin packing models were introduced and their approximation properties were shown (co-authors: L. Epstein, X. Han, H. Kellerer, J. Sgall, and M. G. Speranza).
The current best lower and current (2020) best upper bounds were determined for the online bin packing problem (co-authors: J. Balogh, J. Békési, L. Epstein, A. Levin).
A “combinatorial batch code” is a set systems that can be used to model the storage and retrieval of a given amount of information on a given number of servers. The constraints concern the maximum amount of data to be decoded at a time and the encryption related to data protection. The minimum total size of sets in a system meeting the conditions was determined in different ranges of the parameters, and new results were obtained for related classical problems of combinatorics (Hall condition, Turán problem).
Problems we have recently solved
Publications
In recent years the members of the research group have published nearly 100 papers with impact factors, according to the DBLP database.
- Gyula Abraham, György Dósa, Lars Magnus Hvattum, Tomas Olaj, Zsolt Tuza: The board packing problem. Eur. J. Oper. Res. 308(3): 1056-1073 (2023)
- József Balogh, Gyula O.H. Katona, Zsolt Tuza, William Linz: The domination number of the graph defined by two levels of the n-cube, II. European J. Combin. 91: 103201 (2021)
- János Balogh, József Békési, György Dósa, Leah Epstein, Asaf Levin: A new and improved algorithm for online bin packing. ESA 2018: 5:1-5:14
- József Békési, György Dósa, Gábor Galambos: A First Fit type algorithm for the coupled task scheduling problem with unit execution time and two exact delays. Eur. J. Oper. Res. 297(3): 844-852 (2022)
- Csilla Bujtás: Domination number of graphs with minimum degree five. Discuss. Math. Graph Theory 41: 763-777 (2021)
- Csilla Bujtás, Mario Gionfriddo, Elena Guardo, Lorenzo Milazzo, Salvatore Milici, Zsolt Tuza: Complex uniformly resolvable decompositions of Kv. Ars Math. Contemp. 21(1): #P1.02 (2021)
- Csilla Bujtás, Günter Rote, Zsolt Tuza: Optimal strategies in fractional games: vertex cover and domination. Ars Math. Contemp. (2024)
- Sylwia Cichacz, Zsolt Tuza: Realization of digraphs in Abelian groups and its consequences. J. Graph Theory 100(2): 331-345 (2022)
- Anita Keszler, Zsolt Tuza: Spectrum of 3-uniform 6-and 9-cycle systems over Kv(3)−I. Discrete Math. 347: 113782 (2024)
- Balázs Patkós, Zsolt Tuza Máté Vizer: Vector sum-intersection theorems. Discrete Math. 346: 113506 (2023)
Projects
The members of the research group have won various research grants in the recent years (eg. Slovenian-Hungarian OTKA) and participated in various projects (TÁMOP, EFOP, etc. applications) and organized several successful conferences (Veszprém Discrete Mathematics and Applications Conference, 2018, Veszprém Optimization Workshop 2019).
Two members of the research team at work
