Bi‐arc graphs and the complexity of list homomorphisms
From MaRDI portal
Publication:4798127
DOI10.1002/jgt.10073zbMath1057.05033OpenAlexW4247305611MaRDI QIDQ4798127
Jing Huang, Tomás Feder, Pavol Hell
Publication date: 19 March 2003
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.10073
complexityNP-completenesspolynomial-time algorithmscircular arc graphslist coloringsbi-arc graphsinternal graphsedge asteroids sheet width
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (62)
Dichotomies for classes of homomorphism problems involving unary functions ⋮ Complexity issues on bounded restrictive \(H\)-coloring ⋮ The complexity of signed graph and edge-coloured graph homomorphisms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ Testing list \(H\)-homomorphisms ⋮ List homomorphisms of graphs with bounded degrees ⋮ The structure of bi-arc trees ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ A complexity dichotomy for signed \(\mathbf{H}\)-colouring ⋮ Counting List Matrix Partitions of Graphs ⋮ Correspondence homomorphisms to reflexive graphs ⋮ List-homomorphism problems on graphs and arc consistency ⋮ Complexity of correspondence \(H\)-colourings ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Clique versus independent set ⋮ List homomorphisms to separable signed graphs ⋮ Conservative constraint satisfaction re-revisited ⋮ Min orderings and list homomorphism dichotomies for signed and unsigned graphs ⋮ Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms ⋮ Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs ⋮ Majority constraints have bounded pathwidth duality ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ The complexity of the matroid homomorphism problem ⋮ List homomorphism: beyond the known boundaries ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Unnamed Item ⋮ Min-Orderable Digraphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Unnamed Item ⋮ Bounded Tree-Width and CSP-Related Problems ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Counting Constraint Satisfaction Problems. ⋮ Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees ⋮ The monotonicity property of \(M\)-partition problems ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ List H-coloring a graph by removing few vertices ⋮ The complexity of the list homomorphism problem for graphs ⋮ The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops ⋮ The restrictive \(H\)-coloring problem ⋮ Surjective \(H\)-colouring: new hardness results ⋮ The complexity of tropical graph homomorphisms ⋮ Recognizing frozen variables in constraint satisfaction problems ⋮ Computing vertex-surjective homomorphisms to partially reflexive trees ⋮ Representation characterizations of chordal bipartite graphs ⋮ Unnamed Item ⋮ Dichotomy for tree-structured trigraph list homomorphism problems ⋮ Building blocks for the variety of absolute retracts ⋮ Unnamed Item ⋮ Graph partitions with prescribed patterns ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ Minimum Cost Homomorphisms with Constrained Costs ⋮ Extension problems with degree bounds ⋮ Adjusted Interval Digraphs ⋮ A generalization of the theorem of Lekkerkerker and Boland ⋮ Dualities for Constraint Satisfaction Problems ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs ⋮ List homomorphism problems for signed trees ⋮ List matrix partitions of chordal graphs
Cites Work
This page was built for publication: Bi‐arc graphs and the complexity of list homomorphisms
