1. Linear bounds on treewidth in terms of excluded planar minorsJ. Pascal Gollin, Kevin Hendrey, Sang-il Oum, Bruce Reed, 2025, izvirni znanstveni članek Opis: One of the fundamental results in graph minor theory is that for every planar graph $H$, there is a minimum integer $f(H)$ such that graphs with no minor isomorphic to $H$ have treewidth at most $f(H)$. A lower bound for $f(H)$ can be obtained by considering the maximum integer $k$ such that $H$ contains $k$ vertex-disjoint cycles. There exists a graph of treewidth $\Omega(k\log k)$ which does not contain $k$ vertex-disjoint cycles, from which it follows that $f(H) = \Omega(k\log k)$. In particular, if $f(H)$ is linear in $\lvert V(H) \rvert$ for graphs $H$ from a subclass of planar graphs, it is necessary that $n$-vertex graphs from the class contain at most $\lvert V(H) \rvert$ vertex-disjoint cycles. We ask whether this is also a sufficient condition, and demonstrate that this is true for classes of planar graphs with bounded component size. For an $n$-vertex graph $H$ which is a disjoint union of $r$ cycles, we show that ${f(H) \leq 3n/2 + O(r^2 \log r)}$, and improve this to $f(H)$≤$n$+O(√$n$) when $r$=2. In particular this bound is linear when $r$=O(√$n$/logn). We present a linear bound for $f(H)$ when $H$ is a subdivision of an $r$-edge planar graph for any constant~$r$. We also improve the best known bounds for $f(H)$ when $H$ is the wheel graph or the 4×4 grid, obtaining a bound of 160 for the latter.
Ključne besede: graph minor, treewidth, cycle packing
Objavljeno v RUP: 05.01.2026; Ogledov: 281; Prenosov: 2
 Celotno besedilo (613,98 KB)
Gradivo ima več datotek! Več... |
2. Induced minor models : Structural properties and algorithmic consequencesNicolas Bousquet, Clément Jean Dallard, Maël Dumas, Claire Hilaire, Martin Milanič, Anthony Perez, Nicolas Trotignon, 2026, izvirni znanstveni članek Opis: 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 G between the corresponding subsets. In this paper, we investigate structural properties of induced minor models, including bounds on treewidth and chromatic number of the subgraphs induced by minimal induced minor models. As algorithmic applications of our structural results, we make use of recent developments regarding tree-independence number to show that if H is the 4-wheel, the 5-vertex complete graph minus an edge, or a complete bipartite graph K2,q , then there is a polynomial-time algorithm to find in a given graph G an induced minor model of H in G, if there is one. We also develop an alternative polynomial-time algorithm for recognizing graphs that do not contain K2,3 as an induced minor, which revolves around the idea of detecting the induced subgraphs whose presence is forced when the input graph contains K2,3 as an induced minor. It turns out that all these induced subgraphs are Truemper configurations.
Ključne besede: induced minor, treewidth, chromatic number, tree-independence number, Truemper configuration
Objavljeno v RUP: 16.12.2025; Ogledov: 201; Prenosov: 3
Celotno besedilo (1,44 MB)
Gradivo ima več datotek! Več... |
3. On relationships between treewidth, clique number, tree-independence number, and induced minors : master’s thesisÐorđe Vasić, 2025, magistrsko delo Ključne besede: treewidth, clique number, tree-independence number, induced minor, hered itary graph class, bipartite chain graph
Objavljeno v RUP: 11.09.2025; Ogledov: 614; Prenosov: 8
Celotno besedilo (839,36 KB) |
4. |
5. |
6. |
7. Nove karakterizacije v strukturni teoriji grafov : 1-popolno usmerljivi grafi, produktni grafi in cena povezanostiTatiana Romina Hartinger, 2017, doktorska disertacija Ključne besede: 1-perfectly orientable graph, structural characterization of families of graphs, chordal graph, interval graph, circular arc graph, cograph, block-cactus graph, cobipartite graph, K4-minor-free graph, outerplanar graph, graph product, Cartesian product, lexicographic product, direct product, strong product, price of connectivity, cycle transversal, path transversal
Objavljeno v RUP: 09.11.2017; Ogledov: 5599; Prenosov: 44
 Povezava na celotno besedilo |
8. National report : SloveniaMateja Sedmak, Tjaša Žakelj, Blaž Lenarčič, Zorana Medarić, 2015, končno poročilo o rezultatih raziskav Ključne besede: migrations, unaccompanied minor migrants, best interest of a child, rights of a child, national legislation, Slovenia, migracije, mladoletni migranti brez spremstva, otrokove pravice, nacionalna zakonodaja, Slovenija
Objavljeno v RUP: 08.08.2016; Ogledov: 5361; Prenosov: 95
Povezava na celotno besedilo |
9. Comparative report on fieldwork with experts and unaccompanied minors : an overview of the reception, protection and asylum procedures for unaccompanied minors in Austria, France, Slovenia and the United Kingdom with the focus on the concept of the best interest of the child and the formal processes of the best interest determinationMateja Sedmak, Tjaša Žakelj, Zorana Medarić, Blaž Lenarčič, 2015, končno poročilo o rezultatih raziskav Ključne besede: migrations, unaccompanied minor migrants, best interest of a child, rights of a child, fieldwork, Europe, migracije, mladoletni migranti brez spremstva, otrokove pravice, terenske raziskave, Evropa
Objavljeno v RUP: 08.08.2016; Ogledov: 4950; Prenosov: 174
Povezava na celotno besedilo |
10. Comparative analysis of the national reports on the state of the artMateja Sedmak, Tjaša Žakelj, Blaž Lenarčič, Zorana Medarić, Ana Kralj, 2015, končno poročilo o rezultatih raziskav Ključne besede: migrations, unaccompanied minor migrants, best interest of a child, rights of a child, national legislation, Europe, migracije, mladoletni migranti brez spremstva, otrokove pravice, nacionalne zakonodaje, Evropa
Objavljeno v RUP: 08.08.2016; Ogledov: 4860; Prenosov: 95
Povezava na celotno besedilo |
