The parameterised complexity of list problems on graphs of bounded treewidth
From MaRDI portal
Abstract: We consider the parameterised complexity of several list problems on graphs, with parameter treewidth or pathwidth. In particular, we show that List Edge Chromatic Number and List Total Chromatic Number are fixed parameter tractable, parameterised by treewidth, whereas List Hamilton Path is W[1]-hard, even parameterised by pathwidth. These results resolve two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen (2011).
Recommendations
- scientific article; zbMATH DE number 7651213
- Parametric Problems on Graphs of Bounded Tree-Width
- Parametric problems on graphs of bounded tree-width
- The Complexity of the List Partition Problem for Graphs
- The complexity of the list homomorphism problem for graphs
- The complexity of the list homomorphism problem for graphs
- scientific article; zbMATH DE number 7228418
- Bounded Tree-Width and CSP-Related Problems
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
Cites work
- scientific article; zbMATH DE number 446487 (Why is no real title available?)
- scientific article; zbMATH DE number 3917707 (Why is no real title available?)
- scientific article; zbMATH DE number 3284071 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Asymptotics of the chromatic index for multigraphs
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Edge-Coloring Partialk-Trees
- Fundamentals of parameterized complexity
- Generalized coloring for tree-like graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- List edge and list total colourings of multigraphs
- List edge-coloring and total coloring in graphs of low treewidth
- List total colorings of series-parallel graphs
- List-colourings of graphs
- Lower bounds based on the exponential time hypothesis
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- NP completeness of finding the chromatic index of regular graphs
- NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
- On the complexity of some colorful problems parameterized by treewidth
- On the parameterized complexity of multiple-interval graph problems
- Parametrized complexity theory.
- Some upper bounds on the total and list chromatic numbers of multigraphs
- The NP-Completeness of Edge-Coloring
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The list chromatic index of a bipartite multigraph
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Tight lower bounds for certain parameterized NP-hard problems
- Total colorings of degenerate graphs
- Total colouring regular bipartite graphs is NP-hard
Cited in
(11)- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Grundy Distinguishes Treewidth from Pathwidth
- On the linear arboricity of graphs with treewidth at most four
- Total colorings-a survey
- Neighbor sum distinguishing total coloring of graphs with bounded treewidth
- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- Grundy distinguishes treewidth from pathwidth
- On the Complexity of Some Colorful Problems Parameterized by Treewidth
- Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Exploring the gap between treedepth and vertex cover through vertex integrity
This page was built for publication: The parameterised complexity of list problems on graphs of bounded treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q342709)
