Tomáš Masařík

Gaspard Charvy, Tomáš Masařík

We investigate a very recent concept for visualizing various aspects of a graph in the plane using a collection of drawings introduced by Hliněný and Masařík [GD 2023]. Formally, given a graph $G$, we aim to find an uncrossed collection containing drawings of $G$ in the plane such that each edge of $G$ is not crossed in at least one drawing in the collection. The uncrossed number of $G$ ($unc(G)$) is the smallest integer $k$ such that an uncrossed collection for $G$ of size $k$ exists. The uncrossed number is lower-bounded by the well-known thickness, which is an edge-decomposition of $G$ into planar graphs. This connection gives a trivial lower-bound $\lceil\frac{|E(G)|}{3|V(G)|-6}\rceil \le unc(G)$. In a recent paper, Balko, Hliněný, Masařík, Orthaber, Vogtenhuber, and Wagner [GD 2024] presented the first non-trivial and general lower-bound on the uncrossed number. We summarize it in terms of dense graphs (where $|E(G)|=ε(|V(G)|)^2$ for some $ε>0$): $\lceil\frac{|E(G)|}{c_ε|V(G)|}\rceil \le unc(G)$, where $c_ε\ge 2.82$ is a constant depending on $ε$. We improve the lower-bound to state that $\lceil\frac{|E(G)|}{3|V(G)|-6-\sqrt{2|E(G)|}+\sqrt{6(|V(G)|-2)}}\rceil \le unc(G)$. Translated to dense graphs regime, the bound yields a multiplicative constant $c'_ε=3-\sqrt{(2-ε)}$ in the expression $\lceil\frac{|E(G)|}{c'_ε|V(G)|+o(|V(G)|)}\rceil \le unc(G)$. Hence, it is tight (up to low-order terms) for $ε\approx \frac{1}{2}$ as warranted by complete graphs. In fact, we formulate our result in the language of the maximum uncrossed subgraph number, that is, the maximum number of edges of $G$ that are not crossed in a drawing of $G$ in the plane. In that case, we also provide a construction certifying that our bound is asymptotically tight (up to lower-order terms) on dense graphs for all $ε>0$.

Tomáš Masařík, Jędrzej Olkowski, Anna Zych-Pawlewicz

In this paper we study fair variants of MSO$_1$ definable problems parameterized by cluster vertex deletion number, i.e., the smallest number of vertices required to be removed from the graph such that what remains is a collection of cliques. While typical graph problems seek the smallest set of vertices satisfying some property, their fair variants seek such a set that does not contain too many vertices in any neighborhood of any vertex. Formally, the task is to find a set $X\subseteq V(G)$ satisfying some MSO$_1$ definable property, whose fair cost is at most $k$, i.e., such that for all $v\in V(G)$ it holds that $|X\cap N(v)|\le k$. Recently, Knop, Masařík, and Toufar [MFCS 2019] showed that all fair MSO$_1$ definable problems can be solved in FPT time parameterized by the twin cover of a graph. They asked whether such a statement can be achieved for a more general parameterization by cluster vertex deletion number. In this paper, we prove that in full generality this is not possible by demonstrating W[1]-hardness. On the other hand, we give a sufficient condition under which a fair MSO$_1$ definable problem admits an FPT algorithm parameterized by the cluster vertex deletion number. Our algorithm is general enough to capture the fair variant of many natural graph problems such as the Fair Feedback Vertex Set problem, the Fair Vertex Cover problem, the Fair Dominating Set problem, the Fair Odd Cycle Transversal problem, as well as connected variants thereof. Moreover, we solve the Fair $[σ,ρ]$-Domination problem for $σ$ finite, or when both $σ$ and $ρ$ are cofinite. That is, given finite or cofinite $ρ,σ\subseteq \mathbb{N}$, the task is to find set of vertices $X\subseteq V(G)$ of fair cost at most $k$ such that for all $v\in X$, $|N(v)\cap X| \inσ$ and for all $v\in V(G)\setminus X$, $|N(v)\cap X|\inρ$.

Václav Blažej, J. Pascal Gollin, Tomáš Hons et al.

The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bounded tree-independence number have strong structural and algorithmic properties, but the parameter can be unbounded even in quite restricted classes. In particular, the presence of an induced biclique $K_{\ell,\ell}$ forces tree-independence number at least $\ell$. This leads to the question whether large induced bicliques are the only obstruction to bounded tree-independence number in natural hereditary classes. A conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht states that for all positive integers $t$ and $\ell$, every $\{P_t,K_{\ell,\ell}\}$-free graph has bounded tree-independence number. We prove this conjecture for $t=5$ by showing that every $\{P_5,K_{\ell,\ell}\}$-free graph has tree-independence number at most $4\ell$. We also obtain related bounds for the weaker parameter of $α$-degeneracy.