[ Home ]   [ Current ]   [ Archive ]



Seminar za Logiku, Algebru, DIskretnu Matematiku i teorijsko računarstvo
Logic, Algebra, DIscrete Mathematics and Theoretical Computer Science Seminars

Školska 2026/27. / Academic year 2026/27

26/11/2026

(Dani matematike u Novom Sadu 2026)

Zoltán Blázsik (University of Szeged, Hungary): Total coalitions in claw-free, cubic graphs

A set S of vertices in an isolate-free graph G is a total dominating set if every vertex in G is adjacent to some other vertex in S. A total coalition in G consists of two disjoint sets of vertices X and Y of G, neither of which is a total dominating set but whose union X \cup Y is a total dominating set of G. Such sets X and Y are said to form a total coalition. This notion was introduced in 2024, by Alikhani, Bakhshesh and Golmohammadi.

A total coalition partition in G is a vertex partition \Psi ={ V_1,V_2,...,V_k } such that for all i \in [k], the set V_i forms a total coalition with another set V_j for some j, where j \in [k] \setminus { i }. The total coalition number C_t(G) in G is the maximum cardinality of a total coalition partition in G. Barát and Blázsik gave sharp upper and lower bounds on the total coalition number with respect to the maximum and minimum degree of G, that yields 4 <= C_t(G) <= 6 if G is a cubic graph.

In this talk, I would like to survey the recent results of Blázsik, Henning and Jogan, who study total coalition partitions in connected, claw-free, cubic graphs.

22/09/2026

Kristina Asimi (Durham Univeristy, UK): Promise model checking problems

The fixed-template constraint satisfaction problem (CSP) can be seen as the problem of deciding whether a given primitive positive first-order sentence is true in a fixed structure (also called model). 

In this talk, I will present joint work in which we study a class of problems that generalises the CSP simultaneously in two directions: we fix a set L of quantifiers and Boolean connectives, and we specify two versions of each constraint, one strong and one weak. Given a sentence which only uses symbols from L, the task is to distinguish whether the sentence is true in the strong sense, or it is false even in the weak sense. We call such a problem a Promise Model Checking Problem. We classify the computational complexity of these problems for the existential positive equality-free fragment of first-order logic, i.e., L = { \exists,\land,\lor }, and we prove some upper and lower bounds for the positive equality-free fragment, L = { \exists,\forall,\land,\lor }.

In the final part of the talk, I will introduce recent work on Model Checking Problem over the positive equality-free fragment, which also provides the complexity of a specific Promise Model Checking Problem not covered in our paper.

[ Home ]   [ Current ]   [ Archive ]