INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS

DOI10.1142/S0218196706002846zbMath1098.20044MaRDI QIDQ5470161

Marcel Jackson, Ralph McKenzie

Publication date: 29 May 2006

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

zbMATH Keywords

computational complexity; finite semigroups; semigroup varieties; membership problem; finite basis problem; finite simple graphs; graph colorings; universal Horn classes; semigroup quasivarieties

Mathematics Subject Classification ID

20M07: Varieties and pseudovarieties of semigroups

20M05: Free semigroups, generators and relations, word problems

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

08C15: Quasivarieties

Related Items

Flat algebras and the translation of universal Horn logic to equational logic, Complexity of the identity checking problem for finite semigroups., A finite set of functions with an EXPTIME-complete composition problem, Bases of identities for semigroups of bounded rank transformations of a set., COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS, The Algebra of Adjacency Patterns: Rees Matrix Semigroups with Reversion, EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM

Cites Work

• Unnamed Item
• On the quasivarieties generated by finite semigroups
• On classes of relations and graphs determined by subobjects and factorobjects
• Finite semigroups whose varieties have uncountably many subvarieties
• Checking quasi-identities in a finite semigroup may be computationally hard.
• Finitely axiomatizable quasivarieties of graphs
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• Graph Theory and Probability
• INHERENTLY NONFINITELY BASED FINITE SEMIGROUPS
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• On chromatic number of finite set-systems