Št. zadetkov: 7
Magistrsko delo
Oznake:
treewidth;clique number;tree-independence number;induced minor;hered itary graph class;bipartite chain graph;
Leto:
2025
Vir:
Fakulteta za matematiko, naravoslovje in informacijske tehnologije Koper (UP FAMNIT)
Izvirni znanstveni članek
Oznake:
clique number;hereditary graph class;line graph;tree‐independence number;treewidth;
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 ...
Leto:
2026
Vir:
Repozitorij Univerze na Primorskem (RUP)
Objavljeni znanstveni prispevek na konferenci
Oznake:
induced minor;wheel;tree-independence number;Maximum Independent Set;
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 ...
Leto:
2026
Vir:
Fakulteta za matematiko, naravoslovje in informacijske tehnologije Koper (UP FAMNIT)
Izvirni znanstveni članek
Oznake:
linear coloring;central coloring;treedepth;
Motivated by algorithmic applications, Kun, O’Brien, Pilipczuk, and Sullivan introduced the parameter linear chromatic number as a relaxation of treedepth and proved that the two parameters are polynomially related. They conjectured that treedepth could be bounded from above by twice the linear chro ...
Leto:
2026
Vir:
Fakulteta za matematiko, naravoslovje in informacijske tehnologije Koper (UP FAMNIT)
Izvirni znanstveni članek
Oznake:
induced minor;treewidth;chromatic number;tree-independence number;Truemper configuration;
A graph H is an induced minor of G if there exists an induced minor model of H in G, that is, a collection of pairwise disjoint subsets of vertices of G labeled by the vertices of H, each inducing a connected subgraph in G, such that two vertices of H are adjacent if and only if there is an edge in ...
Leto:
2026
Vir:
Fakulteta za matematiko, naravoslovje in informacijske tehnologije Koper (UP FAMNIT)
Objavljeni znanstveni prispevek na konferenci
Oznake:
graph domination;{k}-Roman domination;{k}-Roman graph;split graph;split join;NP-completeness;
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 ...
Leto:
2025
Vir:
Fakulteta za matematiko, naravoslovje in informacijske tehnologije Koper (UP FAMNIT)
Izvirni znanstveni članek
Oznake:
proper interval completion;split graph;threshold graph;quasi-threshold graph;caterpillar;
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 pro ...
Leto:
2025
Vir:
Fakulteta za matematiko, naravoslovje in informacijske tehnologije Koper (UP FAMNIT)