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 K 2 , 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 K 2 , 3 as an induced minor, which revolves around the idea of detecting the induced subgraphs whose presence is forced when the input graph contains K 2 , 3 as an induced minor. It turns out that all these induced subgraphs are Truemper configurations.

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 satisfes γ { 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 general 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.

A graph is Ok-free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We show that MAXIMUM INDEPENDENT SET and 3-COLORING in Ok-free graphs can be solved in quasi-polynomial time. As a main technical result, we establish that “sparse” (here, not containing large complete bipartite graphs as subgraphs) Ok-free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is proven sharp as there is an infinite family of O2-free graphs without K3,3-subgraph and whose treewidth is (at least) logarithmic. Other consequences include that most of the central NP-complete problems (such as MAXIMUM INDEPENDENT SET, MINIMUM VERTEX COVER, MINIMUM DOMINATING SET, MINIMUM COLORING) can be solved in polynomial time in sparse Ok-free graphs, and that deciding the Ok-freeness of sparse graphs is polynomial time solvable. * This work was supported by the ANR projects DISTANCIA (ANR-17-CE40-0015), DIGRAPHS (ANR-19-CE48-0013-01), and TWIN-WIDTH (ANR-21-CE48-0014-01), by the LabEx PERSYVAL-lab (ANR-11-LABX-0025), and by the Vanier Canada Graduate Scholarships program. † The full version of the paper can be accessed at https://arxiv.org/abs/2206.00594