INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
From MaRDI portal
Publication:5470161
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)
computational complexity; finite semigroups; semigroup varieties; membership problem; finite basis problem; finite simple graphs; graph colorings; universal Horn classes; semigroup quasivarieties
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, Semigroups embeddable in hyperplane face monoids., Non-finitely based monoids., Complexity of the identity checking problem for finite semigroups., The finite basis problem for Kiselman monoids., A finite set of functions with an EXPTIME-complete composition problem, Bases of identities for semigroups of bounded rank transformations of a set., A minimal nonfinitely based semigroup whose variety is polynomially recognizable., 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