INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS

DOI10.1142/S0218196706002846zbMath1098.20044OpenAlexW1976933099MaRDI QIDQ5470161

Marcel Jackson, Ralph McKenzie

Publication date: 29 May 2006

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

Full work available at URL: https://doi.org/10.1142/s0218196706002846

zbMATH Keywords

computational complexityfinite semigroupssemigroup varietiesmembership problemfinite basis problemfinite simple graphsgraph coloringsuniversal Horn classessemigroup quasivarieties

Mathematics Subject Classification ID

Varieties and pseudovarieties of semigroups (20M07) Free semigroups, generators and relations, word problems (20M05) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quasivarieties (08C15)

Related Items

Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$ ⋮ Complexity of the identity checking problem for finite semigroups. ⋮ Axiomatisability and hardness for universal Horn classes of hypergraphs ⋮ The computational complexity of deciding whether a finite algebra generates a minimal variety ⋮ COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS ⋮ Identities of the Kauffman monoid K3 ⋮ The finite basis problem for Kiselman monoids. ⋮ Representations and identities of Baxter monoids with involution ⋮ Representations and identities of hypoplactic monoids with involution ⋮ Varieties generated by unstable involution semigroups with continuum many subvarieties ⋮ Semigroups embeddable in hyperplane face monoids. ⋮ Flat algebras and the translation of universal Horn logic to equational logic ⋮ Monoid varieties with extreme properties ⋮ A finite set of functions with an EXPTIME-complete composition problem ⋮ A minimal nonfinitely based semigroup whose variety is polynomially recognizable. ⋮ Bases of identities for semigroups of bounded rank transformations of a set. ⋮ The Algebra of Adjacency Patterns: Rees Matrix Semigroups with Reversion ⋮ EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM ⋮ From \(A\) to \(B\) to \(Z\) ⋮ The complexity of homomorphism factorization ⋮ Non-finitely based monoids. ⋮ Low Growth Equational Complexity

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