Results 11 to 20 of about 2,549 (154)
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
Circumference and Pathwidth of Highly Connected Graphs [PDF]
Journal of Graph Theory, 2014 Birmele [J. Graph Theory, 2003] proved that every graph with circumference t has treewidth at most t-1. Under the additional assumption of 2-connectivity, such graphs have bounded pathwidth, which is a qualitatively stronger result. Birmele's theorem was
Marshall, Emily A., Wood, David R.
core +4 more sources
The treewidth and pathwidth of graph unions [PDF]
SIAM Journal on Discrete Mathematics, 2022 Given two $n$-vertex graphs $G_1$ and $G_2$ of bounded treewidth, is there an $n$-vertex graph $G$ of bounded treewidth having subgraphs isomorphic to $G_1$ and $G_2$? Our main result is a negative answer to this question, in a strong sense: we show that the answer is no even if $G_1$ is a binary tree and $G_2$ is a ternary tree.
Bogdan Alecu +5 more
openalex +4 more sources
On Approximating Cutwidth and Pathwidth [PDF]
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), 2023 We study graph ordering problems with a min-max objective. A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized. We give a $ \log^{1+o(1)}(n)$ approximation for the problem, substantially improving upon the previous poly-logarithmic guarantees based
Nikhil Bansal +2 more
openalex +3 more sources
Grundy Distinguishes Treewidth from Pathwidth [PDF]
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
openalex +5 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
Pathwidth and Nonrepetitive List Coloring
The Electronic Journal of Combinatorics, 2016 A vertex coloring of a graph is nonrepetitive if there is no path in the graph whose first half receives the same sequence of colors as the second half. While every tree can be nonrepetitively colored with a bounded number of colors (4 colors is enough), Fiorenzi, Ochem, Ossona de Mendez, and Zhu recently showed that this does not extend to the list ...
Adam Gągol +3 more
openalex +5 more sources
Seymour’s Conjecture on 2-Connected Graphs of Large Pathwidth [PDF]
Combinatorica, 2020 We prove the conjecture of Seymour (1993) that for every apex-forest $H_1$ and outerplanar graph $H_2$ there is an integer $p$ such that every 2-connected graph of pathwidth at least $p$ contains $H_1$ or $H_2$ as a minor. An independent proof was recently obtained by Dang and Thomas.
Tony Huynh +7 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