Results 11 to 20 of about 2,587 (156)
Cycle decompositions of pathwidth‐6 graphs [PDF]
Journal of Graph Theory, Volume 94, Issue 2, Page 224-251, June 2020., 2020 Abstract Hajós' conjecture asserts that a simple Eulerian graph on n vertices can be decomposed into at most ⌊ ( n − 1 ) / 2 ⌋ cycles. The conjecture is only proved for graph classes in which every element contains vertices of degree 2 or 4. We develop new techniques to construct cycle decompositions.
Elke Fuchs +2 more
wiley +5 more sources
From Pathwidth to Connected Pathwidth [PDF]
SIAM Journal on Discrete Mathematics, 2011 It is proven that the connected pathwidth of any graph $G$ is at most $2\cdot\pw(G)+1$, where $\pw(G)$ is the pathwidth of $G$. The method is constructive, i.e.
Dereniowski, Dariusz
core +10 more sources
On Exploring Temporal Graphs of Small Pathwidth [PDF]
arXiv, 2018 We show that the Temporal Graph Exploration Problem is NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is ...
Bodlaender, Hans L. +1 more
core +6 more sources
2-Layer Graph Drawings with Bounded Pathwidth
Journal of Graph Algorithms and Applications, 2023 This paper determines which properties of 2-layer drawings characterise bipartite graphs of bounded pathwidth.
David R. Wood
openalex +3 more sources
Outerplanar obstructions for matroid pathwidth
Electronic Notes in Discrete Mathematics, 2013 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Athanassios Koutsonas +2 more
openalex +5 more sources
Graph Homomorphism, Monotone Classes and Bounded Pathwidth [PDF]
In recent work by Johnson et al. (2022), a framework was described for the study of graph problems over classes specified by omitting each of a finite set of graphs as subgraphs. If a problem falls into the framework then its computational complexity can be described for all such graph classes, giving a dichotomy between those classes for which the ...
Tala Eagling-Vose +3 more
openalex +3 more sources
Grundy Distinguishes Treewidth from Pathwidth
SIAM Journal on Discrete Mathematics, 2022 Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the "price of generality" of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status ...
Rémy Belmonte +4 more
openaire +4 more sources
Crossing Number for Graphs with Bounded Pathwidth [PDF]
Algorithmica, 2020 The crossing number is the smallest number of pairwise edge-crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios.
Thérèse Biedl +3 more
openalex +6 more sources
The pathwidth and treewidth of cographs [PDF]
SIAM Journal on Discrete Mathematics, 1990 Summary: It is shown that the pathwidth of a cograph equals its treewidth, and a linear time algorithm to determine the pathwidth of a cograph and build a corresponding path-decomposition is given.
Bodlaender, Hans, Möhring, Rolf H.
openaire +4 more sources
Pathwidth of outerplanar graphs [PDF]
Journal of Graph Theory, 2006 We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant $c ...
Coudert, David +2 more
openaire +5 more sources