List H-coloring a graph by removing few vertices
DOI10.1007/s00453-016-0139-6zbMath1361.05085arXiv1308.1068OpenAlexW1836455089MaRDI QIDQ527415
Rajesh Chitnis, László Egri, Dániel Marx
Publication date: 11 May 2017
Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1308.1068
graph homomorphismfixed-parameter tractabilityiterative compressiontreewidth reductionshadow removal
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Transversal (matching) theory (05D15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (13)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- The complexity of the list homomorphism problem for graphs
- Finding odd cycle transversals.
- Parameterized graph separation problems
- List homomorphisms of graphs with bounded degrees
- Almost 2-SAT is fixed-parameter tractable
- Circular-arc graphs with clique cover number two
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- Clustering with local restrictions
- List homomorphisms and circular arc graphs
- Parametrized complexity theory.
- Minimum cost and list homomorphisms to semicomplete digraphs
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Parameterized Tractability of Multiway Cut with Parity Constraints
- Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
- On Multiway Cut Parameterized above Lower Bounds
- Finding small separators in linear time via treewidth reduction
- Query evaluation via tree-decompositions
- On Parameterized Approximability
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy
- Bi‐arc graphs and the complexity of list homomorphisms
- Faster Parameterized Algorithms Using Linear Programming
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
This page was built for publication: List H-coloring a graph by removing few vertices