On the complexity of some colorful problems parameterized by treewidth

DOI10.1016/j.ic.2010.11.026zbMath1223.05070OpenAlexW1995561296WikidataQ56926595 ScholiaQ56926595MaRDI QIDQ627124

Michael R. Fellows, Saket Saurabh, Daniel Lokshtanov, Fedor V. Fomin, Carsten Thomassen, Stefan Szeider, Frances A. Rosamond

Publication date: 21 February 2011

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://backend.orbit.dtu.dk/ws/files/5275033/195.Fellows%20et%20al.pdf

zbMATH Keywords

graph coloring parameterized complexity bounded treewidth

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

Iterated Type Partitions ⋮ Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics ⋮ Structural Parameterizations of the Mixed Chinese Postman Problem ⋮ An analysis of the parameterized complexity of periodic timetabling ⋮ Unnamed Item ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ The parameterised complexity of list problems on graphs of bounded treewidth ⋮ Parameterized complexity of fair deletion problems ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Data reduction for graph coloring problems ⋮ Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ On the complexity of coloring ‐graphs ⋮ Parameterized complexity of envy-free resource allocation in social networks ⋮ Parameterized (Approximate) Defective Coloring ⋮ Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization ⋮ Fair division with minimal withheld information in social networks ⋮ Fair division with minimal withheld information in social networks ⋮ On the complexity of restoring corrupted colorings ⋮ Parameterized complexity for iterated type partitions and modular-width ⋮ Unnamed Item ⋮ Extended MSO model checking via small vertex integrity ⋮ An FPT 2-approximation for tree-cut decomposition ⋮ Unnamed Item ⋮ The P3 infection time is W[1-hard parameterized by the treewidth] ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ Confronting intractability via parameters ⋮ Counting linear extensions: parameterizations by treewidth ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model ⋮ Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms ⋮ Computations by fly-automata beyond monadic second-order logic ⋮ Fixed-parameter tractability of \((n-k)\) list coloring ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Tree-coloring problems of bounded treewidth graphs ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Structural parameterizations of budgeted graph coloring ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Structural parameterizations of budgeted graph coloring ⋮ Data Reduction for Graph Coloring Problems ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Algorithmic Applications of Tree-Cut Width ⋮ On some FPT problems without polynomial Turing compressions ⋮ The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth ⋮ Unnamed Item ⋮ Pure Nash equilibria in graphical games and treewidth ⋮ Capacitated domination: problem complexity and approximation algorithms ⋮ All subgraphs of a wheel are 5-coupled-choosable

Cites Work