List homomorphisms to reflexive graphs

DOI10.1006/jctb.1997.1812zbMath0904.05078OpenAlexW2132911512MaRDI QIDQ1127870

Tomás Feder, Pavol Hell

Publication date: 10 August 1998

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jctb.1997.1812

zbMATH Keywords

polynomial time algorithmgraph homomorphismchordal graphNP-completeinterval graphlist colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (74)

Coloring problems on bipartite graphs of small diameter ⋮ Dichotomies for classes of homomorphism problems involving unary functions ⋮ Complexity issues on bounded restrictive \(H\)-coloring ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Testing list \(H\)-homomorphisms ⋮ List homomorphisms of graphs with bounded degrees ⋮ The structure of bi-arc trees ⋮ Computational complexity of compaction to irreflexive cycles ⋮ Algorithms for partition of some class of graphs under compaction and vertex-compaction ⋮ Complexity of tree homomorphisms ⋮ Counting List Matrix Partitions of Graphs ⋮ Correspondence homomorphisms to reflexive graphs ⋮ Complexity of correspondence \(H\)-colourings ⋮ Disconnected cuts in claw-free graphs ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Unnamed Item ⋮ 2K2 vertex-set partition into nonempty parts ⋮ List homomorphisms to separable signed graphs ⋮ Conservative constraint satisfaction re-revisited ⋮ Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy. ⋮ Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms ⋮ The complexity of the matroid homomorphism problem ⋮ List homomorphism: beyond the known boundaries ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Extended formulation for CSP that is compact for instances of bounded treewidth ⋮ Extended skew partition problem ⋮ Unnamed Item ⋮ NU Polymorphisms on Reflexive Digraphs ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Unnamed Item ⋮ Semilattice polymorphisms and chordal graphs ⋮ Min-Orderable Digraphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Unnamed Item ⋮ Dismantlability, connectedness, and mixing in relational structures ⋮ Bounded Tree-Width and CSP-Related Problems ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Efficient algorithms for counting parameterized list \(H\)-colorings ⋮ Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees ⋮ The monotonicity property of \(M\)-partition problems ⋮ List H-coloring a graph by removing few vertices ⋮ \(2K_{2}\) vertex-set partition into nonempty parts ⋮ The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops ⋮ The restrictive \(H\)-coloring problem ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ Unnamed Item ⋮ The complexity of tropical graph homomorphisms ⋮ Fanout limitations on constraint systems ⋮ Computing vertex-surjective homomorphisms to partially reflexive trees ⋮ FindingH-partitions efficiently ⋮ Unnamed Item ⋮ On disconnected cuts and separators ⋮ On the extension of vertex maps to graph homomorphisms ⋮ Constraint Satisfaction with Counting Quantifiers ⋮ Building blocks for the variety of absolute retracts ⋮ Computational complexity relationship between compaction, vertex-compaction, and retraction ⋮ Graph partitions with prescribed patterns ⋮ The complexity of list edge-partitions for simple graphs ⋮ Minimum Cost Homomorphisms with Constrained Costs ⋮ Guarding a subgraph as a tool in pursuit-evasion games ⋮ Retracting Graphs to Cycles ⋮ Extension problems with degree bounds ⋮ The Complexity of Counting Surjective Homomorphisms and Compactions ⋮ Adjusted Interval Digraphs ⋮ Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon ⋮ A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs ⋮ Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2 ⋮ Complexity of homomorphisms to direct products of graphs ⋮ Counting \(H-\)colorings of partial \(k-\)trees ⋮ List homomorphism problems for signed trees ⋮ Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Absolute reflexive retracts and absolute bipartite retracts
• List colourings of planar graphs
• List homomorphisms of graphs with bounded degrees
• The effect of two cycles on the complexity of colourings by directed graphs
• On the complexity of H-coloring
• Polynomial graph-colorings
• Some results concerning the complexity of restricted colorings of graphs
• Colorings and orientations of graphs
• A solution to a colouring problem of P. Erdős
• Every planar map is four colorable. II: Reducibility
• Every planar graph is 5-choosable
• Absolute retracts of bipartite graphs
• List homomorphisms and circular arc graphs
• Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability
• Absolute Retracts and Varieties of Reflexive Graphs
• The Complexity of Colouring by Semicomplete Digraphs
• Fixed-edge theorem for graphs with loops
• Duality and Polynomial Testing of Tree Homomorphisms
• Monotone monadic SNP and constraint satisfaction
• Products of absolute retracts

This page was built for publication: List homomorphisms to reflexive graphs