Results 1 to 10 of about 3,161 (171)
Pathwidth Versus Cocircumference [PDF]
SIAM Journal on Discrete Mathematics, 2023 The {\em circumference} of a graph $G$ with at least one cycle is the length of a longest cycle in $G$. A classic result of Birmel\'e (2003) states that the treewidth of $G$ is at most its circumference minus $1$. In case $G$ is $2$-connected, this upper
Marcin Brianski, G. Joret, M. Seweryn
semanticscholar +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 +15 more sources
Pathwidth and Nonrepetitive List Coloring [PDF]
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),
Adam Gagol +3 more
semanticscholar +6 more sources
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 +8 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
Bogdan Alecu +5 more
semanticscholar +5 more sources
Approximating Pathwidth for Graphs of Small Treewidth [PDF]
ACM Transactions on Algorithms, 2020 We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of \(O(t\sqrt {\log t})\) . This is the first algorithm to achieve an f(t)-approximation for some function f.
Carla Groenland +3 more
semanticscholar +12 more sources
The Primal Pathwidth SETH [PDF]
arXiv.orgMotivated by the importance of dynamic programming (DP) in parameterized complexity, we consider several fine-grained questions, such as the following examples: (i) can Dominating Set be solved in time $(3-\epsilon)^{pw}n^{O(1)}$?
M. Lampis
semanticscholar +5 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.
Nikhil Bansal +2 more
semanticscholar +3 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
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