CS Paper Radar

Non-induced inherent graphs

Vladimir Gurvich, Matjaž Krnc, Martin Milanič, Mikhail Vyalyi

cs.DM math.CO ·submitted 2026-11-04 15:18 UTC · v1

Abstract

Concepts of avoidable paths and inherent two-rooted graphs were recently introduced for the case of induced subgraphs. In this paper, we translate this framework to the setting of not necessarily induced (NNI) subgraphs, where the structural constraints, as well as conclusions, are significantly relaxed. We develop a new sufficient condition for inherence, and use it to provide complete characterizations of inherent two-rooted paths and forks. We show that for these families, the obvious necessary condition for inherence from the induced case is sufficient in the NNI setting. To complement these results, we introduce two general methods for proving non-inherence and apply them to demonstrate the non-inherence of several classes of two-rooted trees. Keywords: subgraph, two-rooted graph, two-rooted tree, avoidable two-rooted graph, inherent two-rooted graph

Closest papers

Nearest neighbours by meaning across the whole index.

Constrained intersection representations and forbidden patterns

cs.DM math.CO ·2026-11-12 ·Laurent Feuilloley, Michel Habib, Amalia Sorondo
similarity 0.63
Abstract

We study the interplay between two types of graph classes: the ones defined by intersections of geometric objects and the ones defined by the absence of a substructure. More precisely, we study intersection graphs that are grounded, that is, the objects lie above a horizontal line that they touch, and ordered graphs with forbidden patterns, that is, ordered graphs that avoid a set of ordered induced subgraphs. These two approaches are fundamentally different, but it is known that several interesting graph classes have both types of characterizations, and we aim to understand whether this is a general phenomenon. Our contributions are the following. First, we identify a family of patterns on four vertices and a natural hierarchy of intersection graphs of strings whose classes are nicely interleaved. This raises hopes to prove connections between the two perspectives. Second, we dampen these hopes by proving that a class of (ordered) intersection graphs that we study cannot be characterized by a finite set of forbidden patterns. Third, we show a dual impossibility result: there exists a pattern-defined class of our hierarchy that admits no intersection representation, if we require this representation to be closed under natural operations such as translation and scaling. However, it turns out that if we allow slightly more exotic intersection representations, then we can find one for this pattern-defined class.

0.30

Global Trace Condition for Injective Transition Graphs

cs.LO ·2026-11-03 ·Stefano Berardi, Ugo de'Liguoro, Daniel Osorio-Valencia
theoryhot direction similarity 0.60
Abstract

We formulate the global trace condition, GTC, for cyclic proofs as a particular case of the size-change termination condition, or SCT. We express cyclic proofs through a variant of size-change graphs, called transition graphs, whose edges are labelled by (finite) bipartite relations. We show that injective transition graphs suffice to encode cyclic pre-proofs for a variant of Brotherston and Simpson's sequent calculus with inductive definitions. The injectivity of transition graphs corresponds to restricting SCT to fan-in-free graphs. Then we prove that an essentially weaker condition implies SCT in this case, and hence GTC.

0.33

The Non-Cancelling-Intersections Conjecture Fails for Left-Linear Trees

cs.DM math.CO ·2026-08-19 ·Hermann Wilhelm
theory similarity 0.58
Abstract

First formulated by Amarilli, Monet, and Suciu (arXiv:2401.16210, 2024), the Non-Cancelling Intersections (NCI) conjecture is an open problem in combinatorics stating that any set union can be constructively built from its algebraically non-cancelling intersections using only disjoint unions and subset complements. In the same paper, two orthogonal possible strengthenings are proposed: using only left-linear trees, and using non-trivial intersections only positively or only negatively depending on the sign of their Möbius value. Here we show that using only left-linear trees, the conjecture is false (independent of the other strengthening). Our argument is non-constructive. We prove the existence of a counterexample, though it is of immense size.

0.40

EPPA for Reducts of the Random Graph

cs.DM math.COmath.LO ·2026-10-29 ·Sofia Brenner, Jan Hubička, Matěj Konečný
theory similarity 0.58
Abstract

We prove that finite two-graphs have coherent EPPA and that neither graphs modulo global complementation nor two-graphs modulo global complementation have EPPA. This completes the classification of EPPA and coherent EPPA for the reducts of the random graph, answering a question and confirming a conjecture of Evans, Hubička, Konečný and Nešetřil.

0.57

Potatoes and Onions

cs.DM math.CO ·2026-10-14 ·Marcin Briański, Meike Hatzel, Karolina Okrasa, Michał Pilipczuk
top venuetheory similarity 0.58
Abstract · This work has been accepted for presentation at SODA 2027

The first major step in the theory of graph minors of Robertson and Seymour was the grid theorem, a fundamental duality result describing that any graph of sufficiently high treewidth must contain a large grid as a minor. Since this pioneering work, multiple grid theorems have been established in structural graph theory, linking various width parameters of combinatorial objects with the non-existence of grid-like obstructions. In particular, Kawarabayashi and Kreutzer [STOC'15] proved a variant of the grid theorem for directed graphs that links directed treewidth with the non-existence of topological minors of large cylindrical walls. On the other hand, to study immersions of undirected graphs $-$ another containment relation that focuses on edge-disjointness, rather than vertex-disjointness $-$ Wollan [JCTB'15] introduced a parameter, tree-cutwidth, and proved that it is dual to immersions of large walls. In this work, we present a version of Wollan's parameter for directed graphs, the directed tree-cutwidth. The main result is a grid theorem for directed tree-cutwidth, establishing that it is dual to directed immersions of large cylindrical walls.

0.50

Pairwise Compatibility Graphs of Unweighted Caterpillars

cs.DM math.CO ·2026-10-10 ·Cyriac Antony, Manuel Lafond, Angelo Monti, Blerina Sinaimeri
similarity 0.57
Abstract

In this paper we study pairwise compatibility graphs whose witness tree is required to be an unweighted caterpillar. This is a natural restriction of PCGs, in the same line of research as the study of star witnesses, which led to the class of double-threshold graphs. In the caterpillar case, we show that this restriction is equivalent to a one-dimensional difference-labelling problem: a graph admits such a representation if and only if its vertices can be assigned integer labels so that adjacency is determined exactly by whether the absolute difference of two labels belongs to a given interval. Using this characterization, we derive structural properties of the class, including bounded twin-width, and study its relation with familiar graph families. We show that the class contains cycles and two-dimensional grids, while it excludes natural obstructions such as the subdivided star $S_{2,2,2,2,2}$, the cube graph $Q_3$, the wheel $W_6$, and the complement of the $3$-sunlet. We also consider restricted representations, including centipede witnesses and representations with a given interval and we give a polynomial-time recognition algorithm when the interval is fixed.

0.31

Fair Division of Graphs: Beyond Traceability

cs.GT cs.DMmath.CO ·2026-08-30 ·Nicolas Bousquet, Frank Connor, Agnès Totschnig, Sébastien Zeitoun
similarity 0.57
Abstract

In this paper, we study fair division problems in which resources are structured as graphs and agents must receive connected bundles. This connectivity requirement fundamentally alters the problem, making it significantly more challenging than its classical counterpart. We focus on the fairness notion of $\mathrm{EF1}_{\mathrm{outer}}$, where envy can be eliminated by removing at most one vertex whose deletion does not disconnect the bundle -- a critical constraint for applications such as land division and network allocation. Our first result extends prior work by establishing the existence of $\mathrm{EF1}_{\mathrm{outer}}$ allocations for an infinite family of non-traceable graphs (that is, graphs that do not admit a Hamiltonian path), answering a central open question and generalizing Bilò et al.'s result for traceable graphs. We then make progress on a conjecture concerning the $\mathrm{EF1}_{\mathrm{outer}}$ spectrum of trees due to Chen and Zwicker. Finally, we complement our structural results with algorithmic insights, showing that deciding the existence of an $\mathrm{EF1}_{\mathrm{outer}}$ allocation is NP-complete even for binary additive valuations, thereby resolving an open complexity question. Taken together, our results deepen the connection between graph theory and fair division, and offer new tools for studying fairness in structured resource environments.

0.06

A Logic for Minor-Free Graph Classes: Model Checking, Dependence, and Combinatorial Reconfiguration

cs.LO cs.DMmath.LO ·2026-10-04 ·Nikolas Mählmann, Patrice {Ossona de Mendez}, Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis +2 more
similarity 0.57
Abstract

We introduce \emph{sub-connectivity logic}, denoted by $\textsf{FOscon}$, an extension of first-order logic for graphs with a specified set $Z$ of admissible edges. Its additional atom $\textsf{scon}(x,y;\bar z)$ asserts that $x$ and $y$ are connected by a path using only edges of $Z$ and avoiding the vertices in $\bar z$. Our main structural result states that, for every weakly sparse graph class $\mathscr C$, the class of all expansions of graphs in $\mathscr C$ by rooted spanning forest orders has bounded twin-width if and only if $\mathscr C$ excludes a fixed minor. When $\mathscr C$ excludes a fixed minor, we can also compute an additional linear order that preserves bounded twin-width in polynomial time. We translate $\textsf{FOscon}$ into first-order logic over an expansion by a depth-first spanning forest order of the admissible-edge graph. Combining this translation with our structural result, we obtain a model checking algorithm for $\textsf{FOscon}$ with running time $f(|φ|,h(G))\cdot |G|^c$, where $f$ is computable, $c$ is an absolute constant, and $h(G)$ is the Hadwiger number of $G$. The translation and model-checking algorithm extend to binary relational structures, with the Hadwiger number measured on the Gaifman graph. For a graph class $\mathscr C$ let $\mathscr C_Z:=\{(G,Z):G\in\mathscr C,\ Z\subseteq E(G)\}$. We show that for every weakly sparse graph class $\mathscr C$, the class $\mathscr C_Z$ is monadically dependent for $\textsf{FOscon}$ if and only if $\mathscr C$ excludes a fixed minor. For monotone classes that admit efficient minor encodings, a corresponding hardness result makes this frontier computationally tight. We give applications to combinatorial reconfiguration and solution discovery problems, and study a guarded extension of $\textsf{FOscon}$ motivated by database queries.

0.16