The parameterised complexity of list problems on graphs of bounded treewidth

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

zbMATH Keywords

graph colouringHamilton pathbounded treewidthparameterised complexitylist colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

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