Iskanje po repozitoriju

Treewidth versus clique number. v. further connections with tree‐independence number
Claire Hilaire, Martin Milanič, Ðorđe Vasić, 2026, izvirni znanstveni članek

Opis: We continue the study of (tw, ω)‐bounded graph classes, that is, hereditary graph classes in which large treewidth is witnessed by the presence of a large clique, and the relation of this property to boundedness of the tree‐independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milanič, and Štorgel in 2024. Dallard et al. showed that bounded tree‐independence number is sufficient for (tw, ω)‐boundedness, and conjectured that the converse holds. While this conjecture has been recently disproved, it is still interesting to determine classes where the conjecture holds; for example, the conjecture is still open for graph classes excluding an induced star, as well as for finitely many forbidden induced subgraphs. In this paper, we identify further families of graph classes where (tw, ω)‐boundedness is equivalent to bounded tree‐independence number. We settle a number of cases of finitely many forbidden induced subgraphs, obtain several equivalent characterizations of (tw, ω)-boundedness in subclasses of the class of complements of line graphs, and give a short proof of a recent result of Ahn, Gollin, Huynh, and Kwon [SODA 2025] establishing bounded tree-independence number for graphs excluding a fixed induced star and a fixed number of independent cycles.
Ključne besede: clique number, hereditary graph class, line graph, tree‐independence number, treewidth
Objavljeno v RUP: 09.04.2026; Ogledov: 329; Prenosov: 9
Celotno besedilo (1,87 MB)
Gradivo ima več datotek! Več...

Excluding an induced wheel minor in graphs without large induced stars
Mujin 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: 364; Prenosov: 2
Povezava na datoteko
Gradivo ima več datotek! Več...

On {k}-Roman graphs
Kenny Bešter Štorgel, Nina Chiarelli, Lara Fernández, J. Pascal Gollin, Claire Hilaire, Valeria Alejandra Leoni, Martin Milanič, 2025, objavljeni znanstveni prispevek na konferenci

Opis: For a positive integer k, a {k}-Roman dominating function of a graph G = (V, E) is a function f : V → {0, 1, . . . , k} satisfying f (N(v)) ≥ k for each vertex v ∈ V with f (v) = 0. Every graph G satisfies γ{Rk}(G) ≤ kγ(G), where γ{Rk}(G) denotes the minimum weight of a {k}-Roman dominating function of G and γ(G) is the domination number of G. In this work we study graphs for which the equality is reached, called {k}-Roman graphs. This extends the concept of {k}-Roman trees studied by Wang et al. in 2021 to gen- eral graphs. We prove that for every k ≥ 3, the problem of recognizing {k}-Roman graphs is NP-hard, even when restricted to split graphs. We provide partial answers to the question of which split graphs are {2}-Roman: we characterize {2}-Roman split graphs that can be decomposed with respect to the split join operation into two smaller split graphs and classify the {k}-Roman property within two specific families of split graphs that are prime with respect to the split join operation: suns and their complements.
Ključne besede: graph domination, {k}-Roman domination, {k}-Roman graph, split graph, split join, NP-completeness
Objavljeno v RUP: 16.12.2025; Ogledov: 530; Prenosov: 3
Celotno besedilo (395,09 KB)
Gradivo ima več datotek! Več...

On the proper interval completion problem within some chordal subclasses
François Dross, Claire Hilaire, Ivo Koch, Valeria Alejandra Leoni, Nina Pardal, María Inés Lopez Pujato, Vinicius Fernandes dos Santos, 2025, izvirni znanstveni članek

Opis: Given a property (graph class) Π, a graph G, and an integer k, the Π-completion problem consists of deciding whether we can turn G into a graph with the property Π by adding at most k edges to G. The Π-completion problem is known to be NP-hard for general graphs when Π is the property of being a proper interval graph (PIG). In this work, we study the PIG-completion problem within different subclasses of chordal graphs. We show that the problem remains NP-complete even when restricted to split graphs. We then turn our attention to positive results and present polynomial time algorithms to solve the PIG-completion problem when the input is restricted to caterpillar and threshold graphs. We also present an efficient algorithm for the minimum co-bipartite-completion for quasi-threshold graphs, which provides a lower bound for the PIG-completion problem within this graph class.
Ključne besede: proper interval completion, split graph, threshold graph, quasi-threshold graph, caterpillar
Objavljeno v RUP: 06.08.2025; Ogledov: 721; Prenosov: 10
Celotno besedilo (824,75 KB)
Gradivo ima več datotek! Več...