Results 91 to 100 of about 11,104 (228)
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 parameterized complexity of computing tree-partitions [PDF]
Discrete Mathematics & Theoretical Computer ScienceWe study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree.
Hans L. Bodlaender +2 more
doaj +1 more source
Parameterized Compilation Lower Bounds for Restricted CNF-formulas
, 2016 We show unconditional parameterized lower bounds in the area of knowledge compilation, more specifically on the size of circuits in decomposable negation normal form (DNNF) that encode CNF-formulas restricted by several graph width measures.
A Darwiche +12 more
core +1 more source
Super stable tensegrities and the Colin de Verdière number ν
Journal of Graph Theory, Volume 108, Issue 3, Page 401-431, March 2025.Abstract A super stable tensegrity introduced by Connelly in 1982 is a globally rigid discrete structure made from stiff bars and struts connected by cables with tension. We introduce the super stability number of a multigraph as the maximum dimension that a multigraph can be realized as a super stable tensegrity, and show that it equals the Colin de ...
Ryoshun Oba, Shin‐ichi Tanigawa
wiley +1 more source
Composing dynamic programming tree-decomposition-based algorithms
, 2019 Given two integers $\ell$ and $p$ as well as $\ell$ graph classes $\mathcal{H}_1,\ldots,\mathcal{H}_\ell$, the problems $\mathsf{GraphPart}(\mathcal{H}_1, \ldots, \mathcal{H}_\ell,p)$, $\mathsf{VertPart}(\mathcal{H}_1, \ldots, \mathcal{H}_\ell)$, and ...
Baste, Julien
core +2 more sources
Size‐Ramsey numbers of graphs with maximum degree three
Journal of the London Mathematical Society, Volume 111, Issue 3, March 2025.Abstract The size‐Ramsey number r̂(H)$\hat{r}(H)$ of a graph H$H$ is the smallest number of edges a (host) graph G$G$ can have, such that for any red/blue colouring of G$G$, there is a monochromatic copy of H$H$ in G$G$. Recently, Conlon, Nenadov and Trujić showed that if H$H$ is a graph on n$n$ vertices and maximum degree three, then r̂(H)=O(n8/5 ...
Nemanja Draganić, Kalina Petrova
wiley +1 more source
Hyperbolic intersection graphs and (quasi)-polynomial time
, 2019 We study unit ball graphs (and, more generally, so-called noisy uniform ball graphs) in $d$-dimensional hyperbolic space, which we denote by $\mathbb{H}^d$.
Kisfaludi-Bak, Sándor
core +1 more source
Treewidth of Chordal Bipartite Graphs [PDF]
Journal of Algorithms, 1993 Summary: Chordal bipartite graphs are exactly those bipartite graphs in which every cycle of length at least six has a chord. The treewidth of a graph \(G\) is the smallest maximum cliquesize among all chordal supergraphs of \(G\) decreased by one.
Kloks, A.J.J., Kratsch, D.
openaire +5 more sources
Journal of Graph Theory, Volume 106, Issue 4, Page 816-842, August 2024.Abstract A minimal separator of a graph G is a set S ⊆ V ( G ) such that there exist vertices a , b ∈ V ( G ) ⧹ S with the property that S separates a from b in G, but no proper subset of S does. For an integer k ≥ 0, we say that a minimal separator is k‐simplicial if it can be covered by k cliques and denote by G k the class of all graphs in which ...
Martin Milanič +3 more
wiley +1 more source
The complexity of detecting taut angle structures on triangulations
, 2012 There are many fundamental algorithmic problems on triangulated 3-manifolds whose complexities are unknown. Here we study the problem of finding a taut angle structure on a 3-manifold triangulation, whose existence has implications for both the geometry ...
Burton, Benjamin A., Spreer, Jonathan
core +1 more source