The parameterised complexity of list problems on graphs of bounded treewidth
From MaRDI portal
Publication:342709
DOI10.1016/J.IC.2016.08.001zbMATH Open1353.68134arXiv1110.4077OpenAlexW2963715762MaRDI QIDQ342709FDOQ342709
Authors: Kitty Meeks, Alex Scott 
Publication date: 18 November 2016
Published in: Information and Computation (Search for Journal in Brave)
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).
Full work available at URL: https://arxiv.org/abs/1110.4077
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
- Fundamentals of parameterized complexity
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- List edge and list total colourings of multigraphs
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The NP-Completeness of Edge-Coloring
- Some upper bounds on the total and list chromatic numbers of multigraphs
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Lower bounds based on the exponential time hypothesis
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Title not available (Why is that?)
- The list chromatic index of a bipartite multigraph
- On the parameterized complexity of multiple-interval graph problems
- List-colourings of graphs
- Asymptotics of the chromatic index for multigraphs
- List edge-coloring and total coloring in graphs of low treewidth
- Title not available (Why is that?)
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- NP completeness of finding the chromatic index of regular graphs
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Total colouring regular bipartite graphs is NP-hard
- Title not available (Why is that?)
- Generalized coloring for tree-like graphs
- List total colorings of series-parallel graphs
- Total colorings of degenerate graphs
- Tight lower bounds for certain parameterized NP-hard problems
- Edge-Coloring Partialk-Trees
- NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
- On the complexity of some colorful problems parameterized by treewidth
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
- Grundy distinguishes treewidth from pathwidth
- Title not available (Why is that?)
- On the Complexity of Some Colorful 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
- Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth
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)
