The parameterised complexity of list problems on graphs of bounded treewidth
From MaRDI portal
Publication:342709
DOI10.1016/j.ic.2016.08.001zbMath1353.68134arXiv1110.4077OpenAlexW2963715762MaRDI QIDQ342709
Kitty Meeks, Alexander D. Scott
Publication date: 18 November 2016
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.4077
Related Items
Grundy Distinguishes Treewidth from Pathwidth ⋮ Total colorings-a survey ⋮ Unnamed Item ⋮ On the linear arboricity of graphs with treewidth at most four ⋮ Neighbor sum distinguishing total coloring of graphs with bounded treewidth ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- On the complexity of some colorful problems parameterized by treewidth
- On the parameterized complexity of multiple-interval graph problems
- List-colourings of graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Asymptotics of the chromatic index for multigraphs
- 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
- Generalized coloring for tree-like graphs
- List edge and list total colourings of multigraphs
- List total colorings of series-parallel graphs
- The list chromatic index of a bipartite multigraph
- Total colorings of degenerate graphs
- Parametrized complexity theory.
- Tight lower bounds for certain parameterized NP-hard problems
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- List Edge-Coloring and Total Coloring in Graphs of Low Treewidth
- Edge-Coloring Partialk-Trees
- 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
- 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
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
