scientific article; zbMATH DE number 2151253

MaRDI QIDQ4660723zbMATH OpenFDO

Authors J. Nešetřil, Pavol Hell

Publication date 4 April 2005

zbMATH Keywords

bi-arc graphgraph homomorphismlist colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Minimum cost and list homomorphisms to semicomplete digraphs
• On list coloring and list homomorphism of permutation and interval graphs
• List homomorphisms of graphs with bounded degrees
• scientific article; zbMATH DE number 1953111
• scientific article; zbMATH DE number 1996252
• Extension problems with degree bounds
• Correspondence homomorphisms to reflexive graphs
• Complexity of correspondence \(H\)-colourings
• New plain-exponential time classes for graph homomorphism
• Bi‐arc graphs and the complexity of list homomorphisms

Cited in

(25)

• Extension problems with degree bounds
• The restrictive \(H\)-coloring problem
• Complexity issues on bounded restrictive H-coloring
• Graph partitions with prescribed patterns
• The complexity of the list homomorphism problem for graphs
• Counting 4 4 matrix partitions of graphs
• Testing list H-homomorphisms
• The Maximum Solution Problem on Graphs
• The complexity of generalized domino tilings
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• Colouring, constraint satisfaction, and complexity
• The complexity of counting surjective homomorphisms and compactions
• Bi‐arc graphs and the complexity of list homomorphisms
• scientific article; zbMATH DE number 1445311 (Why is no real title available?)
• The complexity of counting surjective homomorphisms and compactions
• Bounded Tree-Width and CSP-Related Problems
• How many F's are there in G?
• Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
• The complexity of the list homomorphism problem for graphs
• Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
• List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
• \(H\)-coloring degree-bounded (acyclic) digraphs
• List homomorphisms of graphs with bounded degrees
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Efficient algorithms for counting parameterized list H-colorings

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4660723)