scientific article; zbMATH DE number 68352

zbMATH Open0769.05038MaRDI QIDQ4014307FDOQ4014307

Authors: Lucien Haddad, Vojtěch Rödl 

Publication date: 6 October 1992

Title of this publication is not available (Why is that?)

Recommendations

• On the complexity of coloring areflexive \(h\)-ary relations with given permutation group
• scientific article; zbMATH DE number 5263063
• The complexity of colouring symmetric relational systems
• On the complexity of H-coloring
• \(H\)-coloring dichotomy revisited

zbMATH Keywords

complexitycompleteness criterionfinite algebras\(NP\)-complete\(H\)-coloring problemcoloring areflexive relationsregular transitive subgroup

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Other classical set theory (including functions, relations, and set algebra) (03E20)

Cited In (5)

• Maximal partial clones determined by the areflexive relations
• Deciding Relaxed Two-Colourability: A Hardness Jump
• On the complexity of coloring areflexive \(h\)-ary relations with given permutation group
• On the general coloring problem
• Completeness theory for finite partial algebras

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 Q4014307)