Results 61 to 70 of about 609 (128)
Tournament pathwidth and topological containment
Journal of Combinatorial Theory, Series B, 2013 We prove that if a tournament has pathwidth >=4@q^2+7@q then it has @q vertices that are pairwise @q-connected. As a consequence of this and previous results, we obtain that for every set S of tournaments the following are equivalent:*there exists k such that every member of S has pathwidth at most k, *there is a digraph H such that no subdivision of H
Paul Seymour, Alexandra Fradkin
openaire +2 more sources
A linear fixed parameter tractable algorithm for connected pathwidth [PDF]
arXiv, 2020 The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search where we are given a system of tunnels that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher ...
arxiv
A 3-approximation for the pathwidth of Halin graphs
Journal of Discrete Algorithms, 2004 AbstractWe prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.
Dimitrios M. Thilikos, Fedor V. Fomin
openaire +3 more sources
TREEWIDTH and PATHWIDTH parameterized by vertex cover [PDF]
arXiv, 2013 After the number of vertices, Vertex Cover is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover.
arxiv
Anagram-Free Chromatic Number is not Pathwidth-Bounded [PDF]
arXiv, 2018 The anagram-free chromatic number is a new graph parameter introduced independently Kam\v{c}ev, {\L}uczak, and Sudakov (2017) and Wilson and Wood (2017). In this note, we show that there are planar graphs of pathwidth 3 with arbitrarily large anagram-free chromatic number.
arxiv
Pathwidth of outerplanar graphs
, 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 +4 more sources
The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs [PDF]
, 2014 We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex. This problem is known to be PSPACE-complete for bipartite planar graphs.
arxiv +1 more source
Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings [PDF]
arXiv, 2012 The notions of cutwidth and pathwidth of digraphs play a central role in the containment theory for tournaments, or more generally semi-complete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, Scott, and Seymour [2, 3, 4, 8, 9, 11]. In this work we introduce a new approach to computing these width measures on semi-complete
arxiv
On the complexity of freezing automata networks of bounded pathwidth [PDF]
, 2023 Eric Goles +3 more
openalex +1 more source