Results 11 to 20 of about 2,730 (147)
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),
Gągol, Adam +3 more
core +5 more sources
On the pathwidth of almost semicomplete digraphs [PDF]
, 2015 We call a digraph {\em $h$-semicomplete} if each vertex of the digraph has at most $h$ non-neighbors, where a non-neighbor of a vertex $v$ is a vertex $u \neq v$ such that there is no edge between $u$ and $v$ in either direction.
A. Fradkin +9 more
core +4 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 connected.
Bodlaender, Hans L. +1 more
arxiv +9 more sources
Crossing Number for Graphs With Bounded Pathwidth [PDF]
arXiv, 2016 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
arxiv +9 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 +6 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.
Hatanaka, Tatsuhiko +2 more
arxiv +3 more sources
Improved approximation for 3-dimensional matching via bounded pathwidth local search
, 2013 One of the most natural optimization problems is the k-Set Packing problem, where given a family of sets of size at most k one should select a maximum size subfamily of pairwise disjoint sets.
Cygan, Marek
core +3 more sources
Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs
Discrete Mathematics, 2002 AbstractIn this paper, it is shown that the maximum pagenumber of the graphs with pathwidth k is k and that the maximum pagenumber of the graphs with strong pathwidth k is in between ⌈3(k−1)/2⌉ and 3⌈k/2⌉.
Mitsunori Togasaki, Koichi Yamazaki
openalex +3 more sources
Pathwidth of Circular-Arc Graphs [PDF]
, 2007 The pathwidth of a graph G is the minimum clique number of H minus one, over all interval supergraphs H of G. Although pathwidth is a well-known and well-studied graph parameter, there are extremely few graph classes for which pathwidh is known to be tractable in polynomial time.
Karol Suchan, Ioan Todinca
openalex +3 more sources
Treewidth and Pathwidth of Permutation Graphs [PDF]
SIAM Journal on Discrete Mathematics, 1995 In this paper we show that the treewidth and pathwidth of a permutation graph can be computed in polynomial time. In fact we show that, for permutation graphs, the treewidth and pathwidth are equal. These results make permutation graphs one of the few non-trivial graph classes for which at the moment, treewidth is known to be computable in polynomial ...
Hans L. Bodlaender +2 more
+8 more sources