1. Graph classes closed under self-intersectionKonrad K. Dabrowski, Vadim V. Lozin, Martin Milanič, Andrea Munaro, Daniël Paulusma, Viktor Zamaraev, 2026, objavljeni znanstveni prispevek na konferenci Opis: A graph class is monotone if it is closed under taking subgraphs. A monotone class defined by finitely many obstructions has bounded treewidth if and only if one of the obstructions is a tripod, i.e. a disjoint union of subdivided claws and paths. This dichotomy also characterizes exactly those monotone graph classes for which many NP-hard graph problems admit polynomial-time algorithms. These dichotomies do not extend to the universe of all hereditary classes. This leads to the question of whether we can extend known dichotomies for monotone classes to larger families of hereditary classes. We answer this question affirmatively by considering the family of hereditary graph classes closed under self-intersection. This family is known to be located strictly between the monotone and hereditary classes. We prove a new structural characterization of graphs in self-intersection-closed classes excluding a tripod. In contrast to monotone classes excluding a tripod, these classes do not necessarily have bounded treewidth; in fact, they do not even need to be sparse. We use our characterization to give a complete dichotomy for Maximum Independent Set, and its weighted variant, on self-intersection-closed classes defined by finitely many obstructions: these problems are in P if the class excludes a tripod and NP-hard otherwise. Our dichotomy generalizes several known results on Maximum Independent Set in the literature. We also apply our characterization to obtain a dichotomy for Maximum Induced Matching on self-intersection-closed classes of bipartite graphs defined by finitely many obstructions, and for Satisfiability and Counting Satisfiability on self-intersection-closed classes of (bipartite) incidence graphs defined by finitely many obstructions. Finally, we use our characterization to obtain a dichotomy for boundedness of clique-width for self-intersection-closed classes of bipartite graphs defined by finitely many obstructions.
Ključne besede: graph classes, self-intersection closed, dichotomy, independent set, clique-width, treewidth
Objavljeno v RUP: 15.07.2026; Ogledov: 211; Prenosov: 6
 Celotno besedilo (805,02 KB)
Gradivo ima več datotek! Več... |
2. Excluding an induced wheel minor in graphs without large induced starsMujin Choi, Claire Hilaire, Martin Milanič, Sebastian Wiederrecht, 2026, objavljeni znanstveni prispevek na konferenci Opis: We study a conjecture due to Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht stating that for any positive integer d and any planar graph H, the class of all K_{1,d}-free graphs without H as an induced minor has bounded tree-independence number. A k-wheel is the graph obtained from a cycle of length k by adding a vertex adjacent to all vertices of the cycle. We show that the conjecture of Dallard et al. is true when H is a k-wheel for any k at least 3. Our proof uses a generalization of the concept of brambles to tree-independence number. As a consequence of our main result, several important NP-hard problems such as Maximum Independent Set are tractable on K_{1,d}-free graphs without large induced wheel minors. Moreover, for fixed d and k, we provide a polynomial-time algorithm that, given a K_{1,d}-free graph G as input, finds an induced minor model of a k-wheel in G if one exists.
Ključne besede: induced minor, wheel, tree-independence number, Maximum Independent Set
Objavljeno v RUP: 25.03.2026; Ogledov: 650; Prenosov: 2
 Povezava na datoteko
Gradivo ima več datotek! Več... |
3. The independence polynomial of trees is not always log-concave starting from order 26Ohr Kadrawi, Vadim Levit, 2025, izvirni znanstveni članek Opis: An independent set in a graph is a collection of vertices that are not adjacent to each other. The cardinality of the largest independent set in G is represented by α(G). The independence polynomial of a graph G = (V, E) was introduced by Gutman and Harary in 1983 and is defined as
I(G; x) = Σ_{k = 0}^α(G) s_k x^k = s₀ + s₁x + s₂x² + ... + s_α(G)x^α(G), where sk represents the number of independent sets in G of size k.
The problem raised by Alavi, Malde, Schwenk, and Erdös in 1987 stated that the independence polynomials of trees are unimodal, and many researchers believed that this problem could be strengthened up to its corresponding log-concave version. However, in 2023, this conjecture was shown to be false by Kadrawi, Levit, Yosef, and Mizrachi. In this paper, we provide further evidence against this conjecture by presenting infinite families of trees with independence polynomials that are not log-concave.
Ključne besede: tree, independent set, independence polynomial, unimodality, log-concavity
Objavljeno v RUP: 22.10.2025; Ogledov: 1621; Prenosov: 6
Celotno besedilo (352,77 KB) |
4. On balanceable and simply balanceable regular graphsMilad Ahanjideh, Martin Milanič, Mary Agnes Milanič, 2025, izvirni znanstveni članek Opis: We continue the study of balanceable graphs, defined by Caro, Hansberg, and Montejano in 2021 as graphs G such that any 2-coloring of the edges of a sufficiently large complete graph containing sufficiently many edges of each color contains a balanced copy of G (that is, a copy with half the edges of each color). While the problem of recognizing balanceable graphs was conjectured to be NP-complete by Dailly, Hansberg, and Ventura in 2021, balanceable graphs admit an elegant combinatorial characterization: a graph is balanceable if and only there exist two vertex subsets, one containing half of all the graph’s edges and another one such that the corresponding cut contains half of all the graph’s edges. We consider a special case of this property, namely when one of the two sets is a vertex cover, and call the corresponding graphs simply balanceable. We prove a number of results on balanceable and simply balanceable regular graphs. First, we characterize simply balanceable regular graphs via a condition involving the independence number of the graph. Second, we address a question of Dailly, Hansberg, and Ventura from 2021 and show that every cubic graph is balanceable. Third, using Brooks’ theorem, we show that every 4-regular graph with order divisible by 4 is balanceable. Finally, we show that it is NP-complete to determine if a 9-regular graph is simply balanceable.
Ključne besede: balanceable graph, simply balanceable graph, cubic graph, 4-regular graph, regular graph, independent set
Objavljeno v RUP: 06.08.2025; Ogledov: 1199; Prenosov: 15
Celotno besedilo (530,38 KB)
Gradivo ima več datotek! Več... |
5. Splittable and unsplittable graphs and configurationsNino Bašić, Jan Grošelj, Branko Grünbaum, Tomaž Pisanski, 2019, izvirni znanstveni članek Opis: We prove that there exist infinitely many splittable and also infinitely many unsplittable cyclic ▫$(n_3)$▫ configurations. We also present a complete study of trivalent cyclic Haar graphs on at most 60 vertices with respect to splittability. Finally, we show that all cyclic flag-transitive configurations with the exception of the Fano plane and the Möbius-Kantor configuration are splittable.
Ključne besede: configuration of points and lines, unsplittable configuration, unsplittable graph, independent set, Levi graph, Grünbaum graph, splitting type, cyclic Haar graph
Objavljeno v RUP: 03.01.2022; Ogledov: 3065; Prenosov: 31
Celotno besedilo (355,79 KB) |
6. On girth and the parameterized complexity of token sliding and token jumpingValentin Bartier, Nicolas Bousquet, Clément Jean Dallard, Kyle Lomer, Amer E. Mouawad, 2021, izvirni znanstveni članek Ključne besede: combinatorial reconfiguration, independent set, token jumping, token sliding, parameterized complexity
Objavljeno v RUP: 16.07.2021; Ogledov: 2896; Prenosov: 32
Povezava na celotno besedilo |
7. On girth and the parameterized complexity of token sliding and token jumpingValentin Bartier, Nicolas Bousquet, Clément Jean Dallard, Kyle Lomer, Amer E. Mouawad, 2020, objavljeni znanstveni prispevek na konferenci Ključne besede: combinatorial reconfiguration, independent set, token jumping, token sliding, parameterized complexity
Objavljeno v RUP: 17.12.2020; Ogledov: 3107; Prenosov: 38
Povezava na celotno besedilo |
8. Mind the independence gapTinaz Ekim, Didem Gozüpek, Ademir Hujdurović, Martin Milanič, 2020, izvirni znanstveni članek Ključne besede: maximal independent set, independent dominating set, well-covered graph, hereditary independence gap, polynomial-time algorithm, NP-hard problem
Objavljeno v RUP: 19.05.2020; Ogledov: 5162; Prenosov: 64
Povezava na celotno besedilo |
9. |
10. |
