Results 81 to 90 of about 278 (179)

Chordal Graphs, Even‐Hole‐Free Graphs and Sparse Obstructions to Bounded Treewidth

Journal of Graph Theory, Volume 110, Issue 3, Page 351-365, November 2025.
ABSTRACT Even‐hole‐free graphs pose a central challenge in identifying hereditary classes of bounded treewidth. We investigate this matter by presenting and studying the following conjecture: for an integer t ≥ 4 and a graph H, every even‐hole‐free graph of large enough treewidth has an induced subgraph isomorphic to either K t or H, if (and only if) H
Sepehr Hajebi
wiley   +1 more source

On Endomorphism Universality of Sparse Graph Classes

Journal of Graph Theory, Volume 110, Issue 2, Page 223-244, October 2025.
ABSTRACT We show that every commutative idempotent monoid (a.k.a. lattice) is the endomorphism monoid of a subcubic graph. This solves a problem of Babai and Pultr and the degree bound is best‐possible. On the other hand, we show that no class excluding a minor can have all commutative idempotent monoids among its endomorphism monoids. As a by‐product,
Kolja Knauer, Gil Puig i Surroca
wiley   +1 more source

Tight Distance Query Reconstruction for Trees and Graphs Without Long Induced Cycles

Random Structures &Algorithms, Volume 66, Issue 4, July 2025.
ABSTRACT Given access to the vertex set V$$ V $$ of a connected graph G=(V,E)$$ G=\left(V,E\right) $$ and an oracle that given two vertices u,v∈V$$ u,v\in V $$, returns the shortest path distance between u$$ u $$ and v$$ v $$, how many queries are needed to reconstruct E$$ E $$?
Paul Bastide, Carla Groenland
wiley   +1 more source

Treewidth 2 in the Planar Graph Product Structure Theorem [PDF]

Discrete Mathematics & Theoretical Computer Science
We prove that every planar graph is contained in $H_1\boxtimes H_2\boxtimes K_2$ for some graphs $H_1$ and $H_2$ both with treewidth 2. This resolves a question of Liu, Norin and Wood [arXiv:2410.20333]. We also show this result is best possible: for any
Marc Distel, Kevin Hendrey, Nikolai Karol, David R. Wood, Jung Hon Yip   +4 more
doaj   +1 more source

Structural properties of graph products

Journal of Graph Theory, Volume 109, Issue 2, Page 107-136, June 2025.
Abstract Dujmovć, Joret, Micek, Morin, Ueckerdt, and Wood established that every planar graph is a subgraph of the strong product of a graph with bounded treewidth and a path. Motivated by this result, this paper systematically studies various structural properties of cartesian, direct and strong products.
Robert Hickingbotham, David R. Wood
wiley   +1 more source

Augmenting Naïve Bayes Classifiers with k-Tree Topology

Mathematics
The Bayesian network is a directed, acyclic graphical model that can offer a structured description for probabilistic dependencies among random variables.
Fereshteh R. Dastjerdi, Liming Cai
doaj   +1 more source

On Constrained Minimum Weight Edge Covers With Applications to Emergency Planning

Networks, Volume 85, Issue 3, Page 261-271, April 2025.
ABSTRACT In this paper we present a new covering problem, called Min Cost q$$ q $$‐Single Location Cover, where we are given a fixed positive integer q$$ q $$, a finite ground set J$$ J $$, an integral positive demand dj$$ {d}_j $$ for each element j∈J$$ j\in J $$, a collection 𝒥 of subsets of J$$ J $$, an integral positive cost cS$$ {c}_S $$ and an ...
Shai Dimant, Sven O. Krumke
wiley   +1 more source

The complexity of the perfect matching‐cut problem

Journal of Graph Theory, Volume 108, Issue 3, Page 432-462, March 2025.
Abstract PERFECT MATCHING‐CUT is the problem of deciding whether a graph has a perfect matching that contains an edge‐cut. We show that this problem is NP‐complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five‐regular graphs, for graphs of diameter three, and for bipartite graphs of diameter four.
Valentin Bouquet, Christophe Picouleau
wiley   +1 more source

On the treewidth of toroidal grids

Discrete Applied Mathematics, 2016
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Masashi Kiyomi, Yoshio Okamoto, Yota Otachi   +2 more
openaire   +2 more sources

Contraction obstructions for treewidth

Journal of Combinatorial Theory, Series B, 2011
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos   +2 more
openaire   +3 more sources