List homomorphisms and circular arc graphs
From MaRDI portal
Publication:1977431
DOI10.1007/s004939970003zbMath0985.05048OpenAlexW2033470072MaRDI QIDQ1977431
Huang Jing, Tomás Feder, Pavol Hell
Publication date: 14 May 2000
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s004939970003
Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (83)
Coloring problems on bipartite graphs of small diameter ⋮ 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 ⋮ Minimum cost homomorphism dichotomy for oriented cycles ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Ferrers dimension of grid intersection graphs ⋮ 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 ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Computational complexity of compaction to irreflexive cycles ⋮ On orthogonal ray graphs ⋮ Algorithms for partition of some class of graphs under compaction and vertex-compaction ⋮ List homomorphisms to reflexive graphs ⋮ Counting List Matrix Partitions of Graphs ⋮ Correspondence homomorphisms to reflexive graphs ⋮ Complexity of correspondence \(H\)-colourings ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Unnamed Item ⋮ Graph covers: where topology meets computer science, and simple means difficult ⋮ List homomorphisms to separable signed graphs ⋮ Conservative constraint satisfaction re-revisited ⋮ Min orderings and list homomorphism dichotomies for signed and unsigned graphs ⋮ List covering of regular multigraphs with semi-edges ⋮ Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy. ⋮ Forbidden substructure for interval digraphs/bigraphs ⋮ Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ List homomorphism: beyond the known boundaries ⋮ Unnamed Item ⋮ Minimum Cost Homomorphism Dichotomy for Oriented Cycles ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices ⋮ Extended skew partition problem ⋮ On orthogonal ray trees ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Unnamed Item ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs ⋮ Min-Orderable Digraphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Co-TT graphs and a characterization of split co-TT graphs ⋮ Bounded Tree-Width and CSP-Related Problems ⋮ Efficient algorithms for counting parameterized list \(H\)-colorings ⋮ Two remarks on circular arc graphs ⋮ On retracts, absolute retracts, and foldings in cographs ⋮ 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 ⋮ Unnamed Item ⋮ The complexity of tropical graph homomorphisms ⋮ Recognizing frozen variables in constraint satisfaction problems ⋮ Level of repair analysis and minimum cost homomorphisms of graphs ⋮ Minimum cost and list homomorphisms to semicomplete digraphs ⋮ Representation characterizations of chordal bipartite graphs ⋮ Constraint Satisfaction with Counting Quantifiers ⋮ Computational complexity relationship between compaction, vertex-compaction, and retraction ⋮ On forbidden induced subgraphs for unit disk graphs ⋮ Graph partitions with prescribed patterns ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ Minimum Cost Homomorphisms with Constrained Costs ⋮ 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 ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ A generalization of the theorem of Lekkerkerker and Boland ⋮ Lexicographic Orientation Algorithms ⋮ Introduction to the Maximum Solution Problem ⋮ 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 \(H-\)colorings of partial \(k-\)trees ⋮ List homomorphism problems for signed trees ⋮ Partial Characterizations of 1‐Perfectly Orientable Graphs ⋮ Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem ⋮ Graphs and digraphs represented by intervals and circular arcs ⋮ List matrix partitions of chordal graphs
This page was built for publication: List homomorphisms and circular arc graphs
